跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+0已有论文修订
+93新增 AI 导读

arXiv 最近完成扫描:2026-11-16 01:34 · 全站最近入库:2026-11-14 15:09各信源进度 →

统计口径与数据新鲜度

统计 2026-11-15 09:57 — 2026-11-16 09:57(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-16 01:34最近发现新增版本:2026-11-14 15:09库内论文最新更新时间:2026-11-13 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

23,348 已收录论文19,580 AI 相关6,729 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 251 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-16 01:33(北京时间)
版本更新 · v3arXiv:2610.01421

Robust and leakage-resilient device-independent oblivious transfer in MiniQCrypt

Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang

原文摘要

Assuming post-quantum one-way functions, we construct device-independent oblivious transfer and bit commitment that tolerate independent honest faults at a constant rate and adaptive, bidirectional quantum leakage between the laboratories at a constant rate. Honest parties use trusted classical computation to operate untrusted quantum devices, which may share arbitrary entanglement and perform joint measurements without assumptions of independence or identical distribution. Security is simulation-based against quantum polynomial-time adversaries and composes sequentially with efficient simulators. For security parameter $λ$ and a prescribed total leakage budget $\ell$, one complete one-bit oblivious transfer uses $Θ(\ell+\log^2λ)$ device coordinates in at most three single-use device windows, including preprocessing, and polynomial classical computation and communication. The leakage budget is shared across these windows. The commitment has efficient simulators against both parties and yields device-independent coin tossing with abort; each uses one window. Completeness of oblivious transfer gives device-independent secure computation with abort for every efficiently computable classical functionality on a fixed number of parties, against static corruption of any proper subset, provided each reached call to oblivious transfer satisfies the device and budget conditions. The construction combines short selectors with code-based choice masking, a global audit, and error correction across field symbols. The commitment extractor changes a classical code coset while leaving the device execution and its leakage unchanged. Sender security uses a global Fourier analysis and a selector-aware Magic Square repetition bound derived from the two-round threshold theorem of Kundu and Tan (2023).

quant-ph · cs.CR

版本更新 · v3arXiv:2609.03628

Random Garbage Creates Exponential Quantum Query Separations

Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray

原文摘要

We prove an exponential separation between standard (XOR) quantum queries and forward-erasing queries for a Boolean property of injective functions, answering a question of Aaronson~\cite{Aaronson2021Open}. We also obtain an exponential separation for a Boolean promise problem on permutations, where forward in-place queries are unitary but inverse queries are not supplied. Our construction follows Aaronson's suggestion of appending fixed random garbage to a Simon function. Let $X=\{0,1\}^n$ and $N=2^n$. We use the injection $f_{h,r}(x)=(h(x),x,r_x)$, where $h:X\to X$ is promised to be either a permutation or a Simon function, and $r:X\to X$ is an arbitrary tag table that is reused on every query. The resulting problem is solvable with at most $n+2$ standard queries, but requires $Θ(\sqrt N)$ forward-erasing queries, matching classical collision sampling. Embedding these instances into permutations, with the copy of $x$ replaced by a single bit that keeps the embedding injective, gives a promise problem on permutations of $L=4N^2$ elements that requires $O(\log L)$ standard queries versus $Θ(L^{1/4})$ forward in-place queries. The lower bounds use the recording method. We replace each query by a nearby contraction that records cells of a purified tag table. After $T$ queries, tracing out the purified tag table yields a sum of positive-semidefinite contributions, each depending on $h$ at no more than $T$ addresses. A query-by-query hybrid bounds the trace-norm difference between the actual and auxiliary final operators by $O(T/\sqrt N)$. Random permutations and random Simon functions have the same restriction distribution on such a set unless it contains a hidden Simon pair, an event of probability $O(T^2/N)$. Consequently, the actual final states in the two cases remain close unless $T=Ω(\sqrt N)$, giving the required lower bounds.

cs.CC · quant-ph

版本更新 · v2arXiv:2607.28610

Learning Arbitrary Lindbladians from Time Evolution

Zhili Chen, Zhan Yu

原文摘要

We study the problem of learning arbitrary $n$-qubit Lindbladians, the generators of Markovian open-system dynamics, from their time evolution. We give the first known efficient algorithm that learns arbitrary Lindbladians without any structural assumptions. For an $n$-qubit Lindbladian of dynamical strength at most $Λ$, the algorithm estimates every coefficient to error $\varepsilon$ using $\widetilde O(Λ^2/\varepsilon^2)$ experiments and $\widetilde O(Λ/\varepsilon^2)$ total evolution time, with classical running time polynomial in $n$ and $Λ/\varepsilon$. Both experimental costs match known lower bounds up to polylogarithmic factors. The algorithm identifies candidate labels through product Pauli experiments and estimates their coefficients using random stabilizer preparations and Clifford measurements. It requires no ancillas or control during the unknown evolution. For constant $k$, our algorithm learns generic $k$-local Lindbladians of local dynamical strength at most $Λ_{\mathrm{loc}}$ using $\widetilde O(n^2Λ_{\mathrm{loc}}^2/\varepsilon^2)$ experiments and $\widetilde O(nΛ_{\mathrm{loc}}/\varepsilon^2)$ total evolution time, improving the upper bounds of prior works in terms of the dependence on $n$. We further improve the lower bounds of Arad, Chen, Guo, Rebentrost, and Yu (SODA 2027) using a family of $3$-local Lindbladians. They already hold when the support is known, and only one Hamiltonian coefficient is requested, even for adaptive protocols with arbitrary ancillas and quantum memory. These lower bounds establish that our algorithm is optimal up to polylogarithmic factors in both experiment count and total evolution time for every fixed $k \geq 3$.

quant-ph · cs.DS

新论文 · v1arXiv:2611.04818

Sleep-Disordered Breathing Detection with Quantum Recurrent Neural Networks

Alejandro Mayorga-Redondo, José Daniel Viqueira, Diego Alvarez-Estevez, Eduardo Mosqueira-Rey, Andrés Gómez

原文摘要

This work investigates the application of Quantum Recurrent Neural Networks to the binary classification of sleep-disordered breathing events in time-series data, aiming to distinguish between apneic and normal breathing episodes. A variational classical--quantum architecture is proposed and evaluated against classical Recurrent Neural Network models. Experiments were conducted on multiple real-world datasets with varying levels of complexity to assess the strengths and limitations of the quantum approach. In the comparative analysis, both classical and quantum models showed comparable performance. The quantum model achieved superior performance on the smallest dataset, while yielding slightly weaker results in the most complex setting. However, the quantum approach exhibited notable strengths, such as competitive performance despite a drastically reduced parameter count and low-qubit regime, as well as good generalization capabilities. These results suggest that, despite current hardware and algorithmic limitations, variational quantum recurrent models represent a promising alternative for time-series classification as Quantum Computing technologies continue to mature.

cs.LG · quant-ph

新论文 · v1arXiv:2611.04574

Spectral Quantum Memory for Implicit Neural Representations

Daniel A. Moroz-Broitman, Eliya Nachmani

原文摘要

Implicit neural representations (INRs) model signals as continuous functions from coordinates to values, but their performance depends strongly on how spectral capacity is allocated. Yet most Quantum INR (QINR) architectures treat spectral components as independent outputs of separate quantum blocks. We introduce the Spectral Quantum Memory Model (SQMM), a memory coupled quantum INR in which sequential hybrid data reuploading layers (bands) communicate through a shared coherent quantum memory register. Each band reads the memory, computes on its own coordinate upload, and writes part of its state back, so later bands can build on the computation of earlier ones. When memory read and write layers are input independent, we prove that the memory state forms an operator valued Fourier series whose support is contained in the Minkowski sum of the initial memory spectrum and the local band spectra. Downstream bands then condition their Fourier coefficients on the spectral content stored by earlier bands, and the memory coupling creates no new primitive frequencies. This theory motivates a spectral memory alignment loss that encourages memory to encode the spectrum expressed by the deployed prefix of the model. Across audio and image reconstruction benchmarks, SQMM improves over compact QINR and INR baselines.

quant-ph · cs.AI · cs.LG

版本更新 · v3arXiv:2609.38044

A Tale of Two Walks: From Kac to KMP and Back

Qian Chen, Jingcheng Liu, Minglong Qin, Leonard J. Schulman, Fang Song, Penghui Yao, Mingnan Zhao

原文摘要

We reveal an unexpected connection between two interacting particle systems: Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. We first establish a mixing-time analogue of Aldous's conjecture for the KMP process on general graphs: the mixing time of the $t$-particle process on any connected $d$-vertex graph is at most $O(\log d)$ times the corresponding single-particle mixing time, uniformly in $t$. As an application, we improve the mixing-time bound for coordinate hit-and-run on the $n$-dimensional standard simplex from $\widetilde{O}(n^3)$ [KV26] to $O(n\log n)$, while removing the dependence on the initial distribution. We then show that the twirling channel induced by the parallel Kac's walk on the symmetric subspace can be exactly encoded by a Markov chain on partitions, which naturally lifts to a parallel KMP chain on the complete graph. We prove that $O(\log d+\log(1/\varepsilon))$ repetitions of the parallel Kac's walk suffice to approximate Haar twirling on the symmetric subspace of $(\mathbb{C}^d)^{\otimes t}$ to error $\varepsilon$, uniformly in all $t$. Our main technical contribution is a new structural property of KMP-type dynamics: conditional product structure, which holds for both the standard KMP processes on general graphs and the parallel KMP processes on complete graphs. Conditioned on suitable auxiliary randomness, the evolution of the labeled KMP process factorizes into independent single-particle updates. Combining this structure with an exact coupling, we remove the dependence on the number of particles from the mixing bounds for both unlabeled KMP models. This bypasses the $\log(π_{\min}^{-1})$ dependency from spectral-gap arguments, which is often prohibitively large for many-particle systems. Using this framework, we prove mixing bounds that are sharp up to logarithmic factors for both unlabeled KMP models.

quant-ph · cs.DS · math.PR

版本更新 · v5arXiv:2509.26494

A parity obstruction to degree-optimal syndrome extraction in bivariate bicycle codes

Guangyi Li, Yu Gan, Zeguan Wu, Xueyue Zhang, Zheshen Zhang, Junyu Liu

原文摘要

Syndrome extraction for a CSS code has depth at least the Tanner-graph degree $Δ$, attained by edge colouring if gate order is ignored; correctness adds a parity constraint. We prove three general obstructions to depth-$Δ$ extraction and show that, for every two-block group-algebra code with weight-three polynomials whose checks overlap in at most two qubits, no correct single-round circuit with one ancilla per check and one CNOT per Tanner edge has depth six: the minimum is seven, so the seven-layer cycle of Bravyi \emph{et al.} is optimal for their seven bivariate bicycle codes. This is the first analytic, family-wide impossibility result, extending prior instance-specific solver-based infeasibility results. The hypothesis cannot be dropped: a single orbit of four-qubit overlaps with a collision element of even order and $2$-height at most eight makes depth six attainable, and a $[[72,8,6]]$ code of this kind has a verified six-layer circuit. The refutations carry DRAT certificates. As a further application of the same scheduling scheme, we construct Stab-QRAM, a quantum random access memory for affine Boolean data that uses only CNOT and $X$ gates and has the minimum depth possible for this gate set.

quant-ph · cs.AR

新论文 · v1arXiv:2611.04442

Hybrid Quantum--Classical Pauli-Correlator Architecture for Image Reconstruction

Sparsho Chakraborty, Siddhartha Patra

原文摘要

We introduce the Pauli-Correlator Autoencoder (PCAE), a hybrid quantum--classical architecture for image reconstruction. PCAE splits an image into patches and compresses each patch as a matrix product state (MPS). A small quantum circuit turns each compressed patch into a few measured numbers, and a classical neural network rebuilds the patch from these numbers and the patch position. A learnable energy term, taken from physics, is added to training and tracked as training proceeds. Two versions place the six qubits on a line (PCAE1D) or on a grid (PCAE2D). An averaging step makes the PCAE2D features follow rotations and reflections of the image exactly. Trained on one image at a time, PCAE2D rebuilds images from six public datasets with a peak signal-to-noise ratio of 25.8 to 41.6 decibels. On CIFAR-10 images not used in training, a formula-based stand-in for the PCAE2D features performs within 1 decibel of several simpler classical methods. Five trained models also run on real IBM quantum computers without retraining, and rebuild images at 25.90 to 31.52 decibels. A short argument and a synthetic test show that, with a linear final layer, measuring qubits in pairs is needed for targets built from products of inputs. These results show that PCAE works as a hybrid model that rebuilds varied images and runs on today's quantum hardware at the six-qubit scale.

quant-ph · cs.CV

版本更新 · v2arXiv:2608.15173

Time-Deterministic and Instruction-Dynamic Execution: A field-programmable gate array quantum-control processor

Xiaoqin Luo, Jiayun Song, Xiaolu Su

原文摘要

Long-running quantum computations, including error-corrected workloads, demand instruction availability, measurement-dependent control, and calibration updates. We present Time-Deterministic and Instruction-Dynamic Execution, an FPGA quantum-control processor supporting runtime revision at both instruction and parameter levels. Dynamic Instruction Parameter Update supplies one-shot, next-match patches before parameter capture, while Dynamic Instruction Stream Overwrite provides guarded replacement, logical deletion, and out-of-line insertion in eligible future regions of a resident program. A moving fetch-visibility guard coordinates instruction updates with execution, and event commitment isolates complete descriptors for independent hardware-timed dispatch. Revision applicability depends on update timing and execution progress; deterministic service applies to committed events under the stated scheduling conditions. The Xilinx ZCU102 implementation uses a 250-MHz control core and a 425-MHz timing/update domain. FPGA-resident measurements at the registered digital interfaces confirmed programmed-cycle dispatch for all tested descriptors committed at least one timing-domain cycle before their timestamps, with downstream ready and the stated FIFO ordering conditions. Separate tests confirmed post-commit timestamp and payload invariance. The minimum all-success mapped DIPU margin was four control-domain cycles, and a replacement of L instruction words completed in L+5 update-domain cycles under continuous payload delivery. Within the tested guard-distance range, rejected DISO requests reported an error and preserved the resident path, whereas all admitted revisions tested here executed complete revised sequences. These results provide a hardware execution basis for incorporating runtime-generated sequences and parameter corrections into precisely timed quantum computations with feedback.

quant-ph · cs.AR

新论文 · v1arXiv:2611.04381

On the Hardness of Approximate Quantum Circuit Membership and Optimization

Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis

原文摘要

Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries $S$, decide whether a given circuit $C$ is within distance $\varepsilon$ of a unitary in $S$ under some metric $m$. Membership is a special case of optimization, where $S$ is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case $S=\{I\}$ (approximate identity) is QMA-complete when $C$ is promised to be either close to the identity or far from it. We generalize this setting in three directions: (i) promise-free inputs, (ii) besides $S=\{I\}$, sets $S$ containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of $\varepsilon$, provided $C$'s gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If $S=\{I\}$, or if $S$ contains only generalized permutation matrices, $I\in S$, and $m$ is a trace-based distance, PP-hardness holds for all non-trivial $\varepsilon$. If $S=\{I\}$ and $m$ is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets. Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.

quant-ph · cs.CC

新论文 · v1arXiv:2611.04363

A Conditional Quantum Kac-Bernstein Theorem

Hesam Hosseini, Jinpei Zhao, Masahito Hayashi

原文摘要

We establish a conditional quantum Kac-Bernstein theorem for mixing of two independent, finite-mode bosonic inputs with quantum memories. We characterize exactly when the outputs are conditionally independent given both memories. Each input then decomposes into orthogonal memory sectors sharing a common Gaussian state on the physical system and a bosonic memory factor, up to sector-dependent physical displacements. In particular, triviality of the common bosonic factor implies separability of the inputs, as occurs whenever either memory has finite-dimensional support.

quant-ph · cs.IT · math-ph

版本更新 · v2arXiv:2610.05953

Fast mixing of the SYK model at high temperatures

Yiyi Cai, Yongtao Zhan, Alexander Zlokapa

原文摘要

The Sachdev-Ye-Kitaev (SYK) model is a strongly interacting fermionic system. Its dynamics are difficult to analyze with Lieb-Robinson bounds and cluster expansions due to its all-to-all disordered interactions. We prove that, with high probability over the disorder, the SYK model admits a quantum Gibbs sampler with a system-size-independent spectral gap at sufficiently high constant temperatures. This yields polynomial-time preparation of SYK Gibbs states on a quantum computer. While prior non-rigorous computations that suggested SYK thermalization were limited to studying local correlators, we emphasize that our result holds up to arbitrary inverse polynomial trace distance. Our proof introduces the pseudo-Lindbladian approach to fermions then applies two key new ideas: a Bochner inequality for quantum dynamics, and an especially simple SYK analysis based on a comparison to classical dynamics.

quant-ph · cond-mat.dis-nn · cs.DS · math-ph

新论文 · v1arXiv:2611.04274

Reasoning about Shared-Qubit Concurrency in Quantum Computing

Mingsheng Ying

原文摘要

In this paper, we develop a semantic model for the parallel execution of quantum circuits, providing a formal foundation for studying shared-qubit concurrency in quantum computing. As in classical shared-memory concurrency, parallel quantum circuits may interfere with one another through operations on shared qubits. However, quantum entanglement and the noncommutativity of quantum operations introduce additional challenges for reasoning about their correctness. To address these challenges, we generalise the classical Owicki-Gries method to quantum computing at the level of quantum circuits. Our approach enables compositional reasoning about parallel quantum circuits by separating the verification of individual components from the analysis of interference between them. We formulate proof rules for establishing the correctness of parallel quantum circuits and prove their soundness with respect to the proposed semantic model.

quant-ph · cs.DC · cs.LO · cs.PL

版本更新 · v2arXiv:2602.08363

Roadmap to Quantum Aesthetics

Ivan C. H. Liu, Hsiao-Yuan Chen

原文摘要

Quantum mechanics occupies a central position in contemporary science while remaining largely inaccessible to direct sensory experience. This paper proposes a roadmap to quantum aesthetics that examines how quantum concepts become aesthetic phenomena through artistic mediation rather than direct representation. Two complementary and orthogonal approaches are articulated. The first, a pioneering top-down approach, employs text-prompt-based generative AI to probe quantum aesthetics as a collective cultural construct embedded in large-scale training data. By systematically modulating the linguistic weight of the term "quantum," generative models are used as experimental environments to reveal how quantum imaginaries circulate within contemporary visual culture. The second, a bottom-up approach, derives aesthetic form directly from quantum-mechanical structures through the visualization of quantum-generated data, exemplified here by hydrogen atomic orbitals calculated from the Schrödinger equation. These approaches are framed not as competing methods but as intersecting paths within a navigable field of artistic research. They position quantum aesthetics as an emergent field of artistic research shaped by cultural imagination, computational mediation, and physical law, opening new directions for artistic practice and pedagogy at the intersection of art, data, artificial intelligence and quantum science.

physics.pop-ph · cs.AI · quant-ph

新论文 · v1arXiv:2611.04179

Hardware-Efficient Reinforcement-Learned Scheduling for Quantum LDPC Decoders

Mohsen Moradi, Vahid Nourozi, Wei Tang, David Mitchell

原文摘要

Quantum low-density parity-check (QLDPC) codes are promising for fault-tolerant quantum computing, but their decoding algorithms present significant hardware implementation challenges. Reinforcement-learned sequential belief propagation (RL-S) improves the error-correction performance of conventional belief propagation (BP) through adaptive variable-node scheduling. However, its heap-based priority management introduces substantial hardware overhead. This paper presents hardware implementations of BP, RL-S, and bucket-based reinforcement-learned BP (BRL-S) for the [[288,12,18]] bivariate bicycle QLDPC code. The BRL-S architectures employ quantized priorities and first-in, first-out (FIFO) buckets to simplify scheduling. Three configurations with two, four, and eight priority levels are evaluated. FPGA synthesis results demonstrate that BRL-S reduces lookup-table utilization by approximately 68--72% compared with RL-S. ASIC synthesis further shows reductions of 63--67% in area and 64--69% in estimated power consumption. These results demonstrate that bucket-based scheduling substantially improves the hardware efficiency of reinforcement-learned QLDPC decoders.

cs.IT · quant-ph

版本更新 · v3arXiv:2605.08332

Optimal FALQON for Quantum Approximate Optimization via Layer-wise Parameter Tuning

Michael Mancini, Shabnam Sodagari

原文摘要

Feedback-based adaptive quantum optimization (FALQON) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum devices, but prior studies report that standard fixed-parameter schedules can require relatively deep circuits to reach strong solution quality. We study Optimal FALQON, a layer-wise formulation that treats the time-step $δ_k$ and scaling parameter $w_k$ as classical decision variables optimized per layer. The benchmark uses all 94 non-isomorphic 3-regular graphs with 12 vertices under 8192-shot simulation and compares standard FALQON, Optimal FALQON, and QAOA/QAOA-MA Powell runs warm-started from FALQON-derived schedules. Across approximation ratio, success probability, evaluation-normalized efficiency, and layer-normalized efficiency, Optimal FALQON substantially improves on standard FALQON, and Optimal-FALQON warm starts substantially improve on standard-FALQON warm starts.

quant-ph · cs.AI

新论文 · v1arXiv:2611.04128

Entanglement Allocation for Quantum Integrated Sensing and Communication

Shiva Kazemi Taskooh, Mehdi Monemi, Ekram Hossain, Georges Kaddoum, Mehdi Rasti

原文摘要

Jointly supporting communication and distributed sensing over a shared, limited pool of entanglement resources is an attractive prospect for future quantum networks. We develop a network-level quantum integrated sensing and communication (Q-ISAC) framework in which a quantum base station dynamically allocates elementary Bell pairs between communication users and distributed sensing. Sensing resources are adaptively partitioned among multiple GHZ probes with dynamically selected sizes and sensing-node assignments. We derive an effective quantum Fisher information model accounting for probabilistic fusion, transmission loss, and memory decoherence, and formulate a finite-horizon allocation problem subject to communication QoS, expected sensing-information, sensing-reliability, and hardware constraints. A hierarchical constrained proximal policy optimization (HC-PPO) framework combines learned discrete sensing allocation with analytical continuous communication allocation. Numerical results show that GHZ probing requires approximately $27$--30% fewer sensing qubits than separable probing under modest probe-size caps and 65-67% fewer at the highest considered target under the same sensing requirements. Adaptive multi-GHZ partitioning provides greater robustness than single-GHZ sensing, while adaptive communication--sensing sharing outperforms the evaluated fixed splits. The proposed HC-PPO framework satisfies the joint requirements in at least 99.9% of test instances across the considered sensing targets and fusion probabilities. Monte Carlo evaluation separately shows that realized terminal information reached its target in 96-98% of realizations, distinguishing expected-information satisfaction from realized sensing performance.

quant-ph · cs.NI

版本更新 · v2arXiv:2610.12357

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection

Yihang Sun, Mary Wootters

原文摘要

We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI), over a prime field $\mathbb{F}_p$. For a polynomial $Q(X)$ of degree less than $k$, LLR for Shamir secret sharing asks what a few leaked bits from each of the $n$ shares $Q(α_1), \ldots, Q(α_n)$ reveal about $Q(0)$. Given (worst-case) input lists $S_1, \ldots, S_n \subset \mathbb{F}_p$, OPI seeks a polynomial $Q(X)$ so that $Q(α_i) \in S_i$ for as many $i$ as possible. Leveraging recent connections between these two problems due to (Sun, Wootters 2026), we improve the state-of-the-art for both problems. For LLR, we show that there is some constant $δ> 0$ so that Shamir secret-sharing is one-bit LLR (only a negligible amount about $Q(0)$ is learned) whenever $R := k/n \geq 1/2 - δ$. This is the first result to break the so-called ``one-half barrier'' for LLR, and improves over the previous best known result, requiring $R \geq 0.668$ (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial $Q(X)$ that agrees with at least a $\mathsf{SCL}_ρ(R)-\varepsilon$ fraction of the lists, for every fixed $\varepsilon>0$, where $\mathsf{SCL}_ρ$ is the \emph{semicircle law} of (Jordan et al., 2025). This improves previous algorithmic (and existential) results of (Jo, 2026) and (Horinaga, Yamakawa, 2026). We also give further improved existential results for all OPI instances; and when the evaluation points $α_i$ are chosen at random, for every rate $R > 0$ we show that, with high probability, for worst-case $S_i$ there exists \emph{perfect} solution. Finally, we adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.

quant-ph · cs.CR · cs.DM · cs.IT

版本更新 · v2arXiv:2610.03645

Exponential quantum space advantage in random data streams

Adam Bouland, Matthew Ding, Siddhartha Jain

原文摘要

We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa-Zhandry Code Intersection problem admits exponential quantum advantage in the streaming model when its inputs are streamed in random order. This means quantum computers exhibit exponential space advantage even when simply receiving $(x,f(x))$ pairs for a uniformly random function $f$ in a uniformly random order. Notably, our classical space lower bound does not follow from a communication lower bound. Instead, we utilize density-restoring partitions from communication complexity directly with potential-function analysis in the style used to prove memory-sample tradeoffs for learning. The resulting argument is distinct from both lines of work. Second, we use our framework to show quantum space advantage for the Optimal Polynomial Intersection (OPI) problem in certain regimes via a streaming version of the Decoded Quantum Interferometry algorithm. In particular, we show that for degree $d$ and $n$ evaluation points, attaining $1/2 + Ω(\sqrt{d/n})$ fraction of satisfied OPI constraints via streaming requires $Ω(n)$ classical bits of memory but only $O(d\log n)$ qubits. This yields provable quantum advantage in a "low-rate" regime when the number of evaluation points is much larger than the degree, with a space advantage that can be as large as exponential in certain parameter settings.

quant-ph · cs.CC

新论文 · v1arXiv:2611.03891

Hardware-Aware Design and Layout Selection in Quantum Reservoir Computing for Insurance Claims Forecasting

Renáta Rusnáková, Eugen Šlapak, Gaurav K. Pandey, Juraj Gazda

原文摘要

Quantum reservoir computing (QRC) processes temporal information through quantum dynamics, but it remains unclear whether small QRC models can forecast real data competitively with classical models and whether their predictions survive the transfer from ideal simulation to noisy hardware. We address both questions for a six-qubit gate-based reservoir that forecasts next-day motor-insurance claim counts. Five reservoir candidates were selected and frozen using hardware-native interaction graphs, Trotterized Ising dynamics, memory and measurement-robustness criteria, circuit cost, and calibrated-noise screening. On 232 held-out test days, the ideal candidates reached root-mean-square errors (RMSEs) of 5.66-6.12 claims/day, compared with 5.36 for ridge regression. For four of the five, the difference from ridge was not significant under a 95% block bootstrap, and their accuracy was comparable with classical recurrent and reservoir baselines. On the 156-qubit IBM Kingston processor, we ran 63 evaluations in 21 paired rounds, comparing hardware-aware, random-native, and Qiskit optimization level 1 layouts. Hardware-aware placement gave lower RMSE than Qiskit in every round, with a maximum transfer distortion of 7.59 claims/day (11.84 for Qiskit), and avoided the severe transfer failures seen for some random layouts. Most of the hardware distortion appeared as a systematic forecast shift, which a short hardware probe on training inputs detected before the test runs. Longer replay windows raised circuit cost without a consistent gain in forecasting accuracy or hardware transfer. Small QRC models can thus reach competitive accuracy on this task, and hardware-aware layout selection makes their transfer to IBM Kingston more consistent.

quant-ph · cs.LG · q-fin.ST

新论文 · v1arXiv:2611.03639

Quantum channel tomography: optimal bounds in the near-boundary regime

Kean Chen, Aadil Oufkir

原文摘要

Quantum channel tomography (also known as quantum process tomography) is a fundamental task in quantum information and quantum computing, aiming to learn the full description of an unknown quantum channel from black-box queries. For channels with input dimension $d_1$, output dimension $d_2$, and Kraus rank at most $r$, [CGO+26] identifies the dilation rate $τ=rd_2/d_1\geq 1$ as a key parameter governing a Heisenberg-to-classical transition in query complexity. While the optimal bounds in the boundary regime ($τ=1$) and the away-from-boundary regime ($τ\geq 1+Ω(1)$) are now known, the precise behavior in the near-boundary regime ($1<τ<1+o(1)$) has remained unresolved. In this paper, we close this gap, thereby fully settling the query complexity of quantum channel tomography. Specifically, we show that the query complexity is - $Ω(rd_1d_2/\varepsilon^2)$ for diamond norm error $\varepsilon$, matching the upper bound by [MB26, CGO+26], - $Θ(d_1^2/\varepsilon+\min\{(τ-1)d_1^2,(τ-1)^2d_1^2d_2^2\}/\varepsilon^2)$ for Choi trace norm error $\varepsilon$. Our results reveal two qualitatively different forms of the Heisenberg-to-classical transition. For diamond norm tomography, the Heisenberg scaling disappears suddenly as soon as $τ$ leaves the boundary regime. In contrast, Choi trace norm tomography exhibits a gradual transition from Heisenberg to classical scaling as $τ$ moves from the boundary regime to the away-from-boundary regime.

quant-ph · cs.IT

新论文 · v1arXiv:2611.03596

Spacetime Emergence in the Memory of a Learning Agent

Philip A. LeMaitre, T. Rick Perche

原文摘要

We show that the causal structure of spacetime can emerge within the memory of a learning agent performing a quantum information task. We train a model-based reinforcement-learning agent to maximize the quantum mutual information between localized quantum probes interacting with a quantum field in Minkowski spacetime, without directly providing it with information regarding the spacetime metric or causal structure. In learning to accomplish this task, the reinforcement-learning agent constructs an internal predictive model whose planner develops the characteristic null structure of spacetime, allowing us to reconstruct the causal structure of the Minkowski metric with high accuracy. Within this task, spacetime geometry is obtained from an agent's successful predictions and actions, providing a first step toward showing that spacetime concepts emerge from operational quantum experience.

quant-ph · cs.AI · cs.LG · gr-qc

新论文 · v1arXiv:2611.03558

Quantum Private Information Retrieval on Forests

Mohamed Nomeir, Sennur Ulukus

原文摘要

We consider the problem of graph private information retrieval (PIR) in the quantum setting. We focus on a specific type of graphs, namely the forest graphs. A forest graph is a union of disjoint trees. We consider the quantum setting where all the servers share an entangled state. Each server is allowed to send only one qudit per retrieval round. We design a scheme for the forest graphs that achieves the rate of $\frac{3}{N}$. The scheme uses a GHZ state as the initial entangled state between the servers prior to the scheme initiation. We compare our scheme with the only work done in the literature that considered the quantum setting of graph PIR. We show that our scheme is more efficient in this setting. We derive the quantum capacity for the case of $G=3K_2$, which is equal to $4/6$. $G=3K_2$ is a special case of the forest graph. We design a scheme that is specialized for this graph, achieving a rate equal to $4/6$ and provide the corresponding matching upper bound, establishing it as the capacity.

cs.IT · cs.CR · cs.NI · eess.SP · quant-ph

新论文 · v1arXiv:2611.03484

On the Failure Probability of Quantum Leftover Hashing with Bad Seeds

Asker Friis Bach, Isabel Moreno Babuglia, Jonatan Bohr Brask

原文摘要

We study hashing against quantum adversaries, as used in cryptographic applications, and provide bounds on the probability of failure in practical settings where seeds might be reused and might be non-ideal. Randomness extraction and privacy amplification are key components of quantum cryptographic protocols, such as quantum randomness generation or key distribution, that allow the compression of partially secure raw data into shorter output with high security. To ensure the security of any cryptographic construction that integrates them, it is desirable to establish composable security. This can be done by using methods based on universal hashing and leveraging the general leftover hash lemma, which allows extraction of near-uniform random numbers from an imperfect entropy source by sampling from an almost two-universal family of hash functions using a seed. This approach is taken in many practical implementations, commonly using Toeplitz hashing. The lemma provides an upper bound $\varepsilon$ on the distance of the output to uniform randomness, which holds on average over the choice of seeds. It makes no claim that any particular seed yields near-uniform random numbers. This poses a problem for practical applications where a seed is sampled once and reused for many rounds (blockwise hashing). Here, we study the subset of \textit{bad} seeds yielding far-from-uniform outputs. We show that randomness extraction against quantum side information is guaranteed to produce $δ$-close-to-uniform random numbers except with failure probability $\left(\frac{\varepsilon}δ\right)^2$. This result is generalised to blockwise hashing providing a guarantee of the security of $k$ rounds except with failure probability $\big(\frac{(2k-1)\varepsilon}δ\big)^2$. Moreover, we extend the general leftover hash lemma to blockwise hashing and relax the assumption of almost two-universality.

quant-ph · cs.IT

版本更新 · v2arXiv:2605.23138

Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning

Gino Kwun, Dhanvi Bharadwaj, Gokul Subramanian Ravi

原文摘要

Variational Quantum Algorithms (VQAs) potentially offer a pathway to practical quantum advantage, but their optimization is heavily hindered by barren plateaus and numerous local minima. While classically simulable Clifford circuits can warm-start VQAs to accelerate convergence, existing heuristic-based initialization methods struggle to scale within vast combinatorial search spaces. We address this bottleneck with CRiSP (a Clifford Reinforcement Learning agent for State Preparation), which casts Clifford prefix selection as a sequential decision-making problem. CRiSP utilizes Neural-Guided Monte Carlo Tree Search, driven by a Transformer-based policy trained via self-play, to insert learned Clifford gates before fixed parameterized rotations. This enables the construction of high-quality initial states entirely through polynomial-time classical stabilizer simulation. By integrating a curriculum learning strategy that progressively expands the search horizon, the agent efficiently scales to deep circuits. Evaluated on QAOA benchmarks of up to $22$ qubits and $1{,}370$ parameters, CRiSP outperforms state-of-the-art Clifford initialization methods by a mean of $3.19\times$ (max $45.02\times$) in average energy accuracy and $2.41\times$ (max $16.01\times$) in best-achieved energy accuracy. Assessments on VQE tasks further demonstrate the framework's robustness and generalizability.

quant-ph · cs.AI · cs.ET · cs.LG

版本更新 · v2arXiv:2610.02166

Beyond light cones: State preparation complexity in quantum spin glasses

Omar Al-Ghattas, David Gamarnik, Bobak T Kiani

原文摘要

We introduce a technique for studying state preparation complexity in the quantum $p$-spin model on $n$ qubits, a disordered quantum spin system with random interactions on every set of $p$ qubits. We reduce the task of proving state preparation lower bounds to bounding the local profile complexity of the class, a quantity derived from the metric entropy of the set of vectors recording each state's expectation values against all weight-$p$ Pauli strings. We show that, for sufficiently large fixed $p$, any class with local profile complexity $O(n^2)$ remains separated from the ground-state energy by $Ω(\sqrt n)$, a gap on the leading energy scale. When the profile complexity is $o(n^2)$, we prove the stronger conclusion that the class cannot outperform a benchmark class of simpler states at leading order. Product states always provide such a benchmark. Our framework strengthens known bounds and covers classes beyond the reach of previous methods. These include examples where circuit lightcones extend across the entire system, preventing an application of standard arguments. We obtain an $Ω(n^2/\log n)$ gate lower bound for preparing near-ground states and depth--width tradeoffs, allowing arbitrary one- and two-qubit gates and arbitrarily many discardable ancillas. We also derive lower bounds on entanglement depth and matrix product state bond dimension, and energy obstructions for forward and reverse magic at every fixed level of Parham's magic hierarchy (arXiv:2504.19966). For Clifford circuits doped with $T$-gates, we obtain sharper energy comparisons using product stabilizer states as a more restrictive benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem (arXiv:1810.12197) with metric-entropy bounds for the Gaussian process indexed by the local profiles of states in the class.

quant-ph · cond-mat.dis-nn · cs.CC · math.PR

版本更新 · v2arXiv:2609.40278

Computational Bounds for $f$-Routing

Oren Renard, Nicholas Spooner

原文摘要

The $f$-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, Physical Review A, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers. Our techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length. We show that, for input length $n$ and a sufficiently small constant $ε>0$, a uniform strategy running in time $T$ and succeeding with probability at least $1-ε$ on every input implies the following computational bounds on $f$. 1. If the strategies are arbitrary quantum channels, then $f\in \mathrm{QSZK}(\mathrm{poly}(T))$, where $\mathrm{QSZK}(T)$ is the class of languages having quantum statistical zero-knowledge proofs in which the verifier runs in time $T$ and the simulator in time $\mathrm{poly}(T)$. 2. If the strategies are Clifford+T circuits using at most $t$ magic gates, then $f\in \mathrm{DTIME}(\mathrm{poly}(T2^t))$. 3. If the strategies are explicit Pauli-sparse unitaries acting on at most $T$ qubits and having at most $s$ nonzero Pauli coefficients, then $f\in \mathrm{DTIME}(\mathrm{poly}(Ts))$. Time and space hierarchies then yield explicit functions secure against superlinear and even all polynomial-time adversaries under our computational restrictions. These bounds exceed the bounded-storage qubit bound $q\leq\log n$ of Bluhm, Christandl, and Speelman (Nature Physics, 2022) for the inner product function $f=\mathrm{IP}$, at the cost of restricting adversarial computation and increasing honest evaluation complexity.

quant-ph · cs.CC

新论文 · v1arXiv:2611.03262

Qyantram: A Transparent and Verifiable Quantum Computing Platform

Sharyu Kekane, Sadique Khatib, Abhushan Bokade, Uday Wad, S. M. Kamalapur, Y. D. Bhise

原文摘要

Most quantum circuit platforms focus on idealized circuit assembly and simulation, hiding hardware compilation, error identification, and variational model training behind black-box operations. QYANTRAM addresses this gap through an open platform comprising four subsystems, built around evidence-backed results and independent verification. Its staged compilation pipeline makes every transformation traceable, while the router publishes rejected SWAP candidates and their scores for transparent decision-making. Verification exploits inactive qubits remaining in the |0> state, reducing complexity from 2^N to 2^k for k active qubits. This mathematically exact reduction enables full pre-compilation verification on 127- and 156-qubit layouts, achieving approximately 10,000x speed-ups with execution times below one millisecond. The error identification engine exhaustively evaluates all Pauli error patterns without sampling, matching closed-form predictions within 2.8e-17. Its machine-learning engine achieves numerical agreement within 2.0e-15 of qiskit.quantum_info while training 25-50 times faster. The router introduces approximately 1.27x more SWAP gates than Qiskit's SABRE due to its omission of optimization, trading routing efficiency for complete decision transparency and traceability.

quant-ph · cs.ET

新论文 · v1arXiv:2611.03128

Belief Propagation-Informed Tesseract Decoding of Quantum LDPC Codes

Sana Javed, Francisco Garcia-Herrero, Bane Vasić, Mark F. Flanagan

原文摘要

In quantum error correction, the decoder must estimate the errors from the measurement data accurately and fast enough to avoid a backlog. Search-based decoders such as Tesseract achieve high accuracy by finding a minimum-weight set of error events with an A* search, but their search effort grows rapidly with the physical error rate and the code size. To reduce this search effort while maintaining a logical error rate close to that of Tesseract, we propose a belief propagation (BP)-guided modification of the Tesseract decoder for quantum low-density parity-check (LDPC) codes. Damped sum-product BP is applied to the triggered detectors before the Tesseract search. If the detectors triggered by the BP hard decision match the triggered detectors, this hard decision is accepted directly, and the Tesseract search is skipped. Otherwise, the BP marginal probability estimates, weighted by a trust coefficient, modify the search priority, while the path cost keeps the channel-prior weights so that the decoding objective is unchanged. The framework also supports BP-based initialization, in which selected BP decisions form the starting point of a residual search whose signed-cost objective allows incorrect initial decisions to be removed. A node-exploration limit bounds this residual search; if the limit is reached, the decoder falls back to the BP-guided search on the original triggered detector set. The method is evaluated on the [[72,12,6]], [[90,8,10]], and [[144,12,12]] bivariate bicycle codes under circuit-level noise. With BP-based initialization and a global trust coefficient, the number of Tesseract search nodes expanded is reduced by up to more than two orders of magnitude at low physical error rates, while the logical error rate remains close to that of Tesseract.

quant-ph · cs.IT

新论文 · v1arXiv:2611.02963

Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs

Yali Aharon-Holzman, Michael Ilan, Assaf Reiner, Amnon Ta-Shma

原文摘要

We construct explicit two-sided lossless expanders whose binary adjacency matrices have full rank, and use them to obtain explicit asymptotically good quantum LDPC codes whose specified X- and Z-check matrices have full row rank and satisfy small-set soundness, or confinement, on a linear range. Our lossless expanders are a variant of those of Hsieh, Lubotzky, Mohanty, Reiner, and Zhang, with a free action of a finite 2-group. Under such an action, injectivity and surjectivity of the adjacency matrix are detected on a fixed-size matrix indexed by vertex orbits. Adding a sparse factor to the gadget at the middle vertices of a single type then enforces full rank, with a controlled loss in expansion. To obtain the 2-group action, we observe that reducing the generators of the Lubotzky-Phillips-Sarnak Ramanujan graphs modulo powers of 2, instead of modulo an odd prime, gives Ramanujan Cayley graphs on finite 2-groups. This construction may be of independent interest. Plugging two such expanders into the balanced product of Lin and Hsieh gives the quantum codes, since full rank of the input graphs is inherited by the check matrices. Our construction supplies the code family sought by Hong, Guo, and Lucas. Applying their analysis, within their framework and under their dynamical assumptions, gives quantum memories whose free-energy density is analytic at every positive temperature and whose guaranteed lifetime is $exp(Ω(N))$ at sufficiently low fixed positive temperature, where N is the blocklength. This improves the previously guaranteed stretched-exponential timescale.

quant-ph · cs.CC · cs.DS · math.CO · math.GR