跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

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

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

统计口径与数据新鲜度

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

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

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

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

浏览论文库

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

找到 251 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-15 07:44(北京时间)
版本更新 · v2arXiv:2609.26705

When are bosonic Gaussian states classical to learn?

Senrui Chen, Antonio Anna Mele, Francesco Anna Mele, John Preskill

原文摘要

A fundamental question in physics is: When does classical behavior emerge from quantum systems? Bosonic Gaussian states provide a natural setting to explore this quantum-classical boundary, as they capture both the classical field behavior and the intrinsic quantum nature of light. Here, we address this problem from a learning-theoretic perspective by asking: When are bosonic Gaussian states classical to learn? That is, under what conditions (if any) can an n-mode bosonic Gaussian state be learned with as few samples, and with operations as simple, as are needed to learn a classical 2n-variate Gaussian distribution? We establish a smooth crossover in learnability governed by the state's thermal fluctuations: - Cold Gaussian states are non-classical to learn: When the covariance matrix satisfies $Σ\le(\frac12+O(\frac1n))I$, i.e. close to the vacuum covariance, tomography under single-copy (i.e., non-entangled) measurements fundamentally requires $Ω(n^3)$ copies, strictly exceeding the sample complexity $Θ(n^2)$ of learning classical Gaussian distributions. We show that this hardness persists even when few-copy entangled measurements are allowed. - Warm Gaussian states are classical to learn: When thermal fluctuations exceed the vacuum noise, parameterized by $Σ\ge(\frac12+ν)I$ for any parameter $ν>0$, we prove that single-copy tomography requires $N=Θ\left(n^2\min(n,1+ν^{-1})\right)$ copies. This bound is tight and is achieved by simple, non-adaptive, unentangled heterodyne measurements. Crucially, for $ν=Ω(1)$, the sample complexity drops to $Θ(n^2)$, matching the classical case. Our results tightly characterize a quantum-to-classical crossover in the learnability of bosonic Gaussian states, reveal a novel connection between fundamental physics and statistical learning theory, and have implications for real-world sensing experiments.

quant-ph · cs.IT · cs.LG · math-ph

新论文 · v1arXiv:2611.11626

Proof of the Aaronson-Ambainis Conjecture: An Exposition

Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan

原文摘要

We give an exposition of a recent proof of the Aaronson-Ambainis conjecture, which states that every degree-$d$ polynomial $p : \{0,1\}^n \to [0,1]$ has a variable of influence at least $\mathrm{poly}(\mathrm{Var}(p)/d)$. This implies that quantum query algorithms for decision problems can be efficiently simulated classically on most inputs. It also yields a near-equivalence between the status of the $\mathsf{BPP}$ vs. $\mathsf{BQP}$ problem in the random oracle and unrelativized worlds. We organize the proof around four main steps and discuss how each connects to the literature on the analysis of boolean functions and probabilistic combinatorics. To bring out the key ideas, we do not optimize parameters, and our presentation yields weaker exponents than the original. $\textbf{Authors' note.}$ The proof was discovered by David Turturean using a research system developed at Physical Superintelligence (PSI), in combination with a non-public Anthropic model. The proof was then shared with the authors, who worked to understand it and prepare this exposition. Anthropic's public models were used in this process. The authors did not receive financial compensation from Anthropic or PSI. This article is not intended for publication at a conference or in a journal.

quant-ph · cs.CC

版本更新 · v5arXiv:2410.02583

Sample-Efficient Quantum State Tomography for Structured Quantum States in One Dimension

Zhen Qin, Casey Jameson, Alireza Goldar, Michael B. Wakin, Zhexuan Gong, Zhihui Zhu

原文摘要

In this paper, we answer this fundamental question affirmatively by using a class of informationally complete positive operator-valued measures (IC-POVMs), including symmetric IC-POVMs (SIC-POVMs) and spherical $t$-designs, focusing on sample complexity while not accounting for the implementation complexity of the measurement settings. For SIC-POVMs and spherical 2-designs, we show that the number of state copies to guarantee bounded recovery error of an MPO state with a constrained least-squares estimator depends on the probability distribution of the MPO under the POVM but scales only linearly with $n$ when the distribution is approximately uniform. For general spherical $t$-designs with a sufficiently large $t$, we prove that only a number of state copies proportional to the number of independent parameters in the MPO is sufficient for a guaranteed recovery of any state represented by an MPO. In addition, we establish a sample complexity lower bound based on the Cramer-Rao bound, showing that, for strictly positive definite MPO states and unbiased estimators, a number of state copies proportional to the number of independent parameters in the MPO is also necessary, although the upper and lower bounds do not yet match in their dependence on the target accuracy. Furthermore, we propose a spectral method and a projected gradient descent (PGD) algorithm to solve the constrained least-squares problem, both equipped with rigorous recovery error guarantees.

quant-ph · cs.IT · eess.SP · math.OC

新论文 · v1arXiv:2611.11537

Weight-Space Programming of Variational Quantum Circuits: Large Language Models Write Quantum Circuit Parameters Without an Optimizer

Debarshi Kundu, Swaroop Ghosh, Vasant G Honavar

原文摘要

Variational quantum algorithms (VQAs) optimize circuit angles through repeated quantum-device evaluations, often facing vanishing gradients and high optimization costs. We ask whether a large language model (LLM) can write these angles directly. Extending *weight-space programming* from classical networks to quantum circuits, we provide a frontier LLM (\gpt) with the problem, circuit, and gate conventions. Its angles are executed exactly as written, without returning losses, gradients, or accuracy feedback. Across 139 requests, we test handwritten-digit classification, VQE ground-state estimation for spin chains and H$_2$, and MaxCut QAOA, comparing against random weights, classical optimization, and optimization initialized with LLM weights on the same circuit. When parameters have interpretable structure, the LLM matches or approaches the optimizer: it achieves 95--100\% of the energy spectrum on every VQE problem, derives the exact H$_2$ ground state in closed form, finds optimal depth-one QAOA angles for every graph, and reaches 93--96\% accuracy on digits 3 versus 8 with 12--18 hand-written weights, outperforming an optimizer trained on the same ten examples. Its weights are also strong warm starts: optimization reaches its best value after a median of one evaluation rather than hundreds. Allowed to design circuits, the LLM chooses data-dependent rotation chains encoding pixel importance in all 30 cases (one qubit for binary tasks, one chain per qubit for ten classes), reaching 65\% accuracy across ten digits. Yet the approach fails in opaque weight spaces: accuracy drops to chance when fixed circuits exceed 30 weights, while optimization improves. It is also sensitive to gate conventions: 6 of 42 QAOA replies reverse mixing-angle signs and fail. We release all prompts, replies, and scores.

quant-ph · cs.AI

版本更新 · v3arXiv:2610.02068

Sequential Capacity of Quantum Processes with Finite Memory

Yibin Wang

原文摘要

How complex can the responses of a quantum process become as it runs longer with fixed internal memory? We measure this complexity by sequential response capacity, the depth of an adaptive tree of experiments whose acceptance probabilities separate possible processes by a prescribed gap. Each experiment uses a fresh complete run, and one fixed process must realize every response along a path. For any fixed common visible dimension of at least two and internal memory cap, we prove that capacity has order $K\log((K+1)/γ)$ for $K$ transitions per run and probability gap $0<γ\leq1$. Time-dependent single-qubit phase channels without internal memory already attain the fixed-gap $K\log K$ growth, realizing each path with zero-or-one response probabilities. Under the same tester permissions, classical stochastic processes that measure in a fixed basis at every transition have only linear capacity at fixed dimensions and gap. For phase sequences selected by a classical address stored inside the process, we then quantify how known independent Pauli noise changes this logarithmic enhancement. With ideal tester controls and weak residual phase noise after correction, we prove matching capacity bounds at a fixed small gap. At fixed address size and fixed positive residual noise, the logarithmic enhancement saturates once the phase-sequence length exceeds the inverse noise scale, and capacity then grows linearly with sequence length.

quant-ph · cs.LG

版本更新 · v2arXiv:2609.39234

Breaking the Bounded Entanglement Barrier for Quantum Position Verification

Amit Behera, Vipul Goyal

原文摘要

Position verification, introduced by Chandran et al. (SIAM J. Computing 2014), allows verifiers to test a prover's claimed position by an interactive protocol. Classical position verification is impossible. Even for Quantum Position Verification (QPV), there always exists an LOCC (Local Operations and Classical Communication) attack if the adversary can hold an exponentially large amount of preshared entanglement. Somewhat surprisingly, we show that we can circumvent this barrier in the idealized continuous-time model, where time is represented by a real-valued parameter and challenge messages can be sent at a time sampled uniformly from a real interval. In this model, we give a BB84-based protocol that remains secure against any finite coalition of LOCC adversaries with arbitrary finite (possibly exponential) quantum storage and entanglement. Our construction can also be instantiated in the discrete-time model. Although prior impossibility results apply, our information-theoretic QPV protocol achieves any desired polynomial gap between the honest parties' total resources (communication and storage) and the adversarial resource bound. To our knowledge, all prior constructions that do not rely on idealized oracles required resources of the honest parties to be at least as large as the proven adversarial entanglement bound. Interestingly, the resource gap depends on the precision in measuring time. As clock precision improves, the adversarial resource bound increases while honest resources remain largely unchanged. We call this the "I sleep, you work" paradigm. Finally, we show that our techniques extend to an information-theoretic, position-based message authentication protocol, which in turn extends to an information-theoretic, position-based quantum key exchange protocol with the same guarantees as our position-verification protocol in the continuous-time and discrete-time models.

quant-ph · cs.CR

版本更新 · v3arXiv:2603.18318

Efficient Soft-Output Guessing for Enhanced Quantum Tanner Code Decoding

Lukas Rapp, Muriel Médard, Eugene Tang, Ken R. Duffy

原文摘要

We introduce a generalized low-density parity-check decoding framework for quantum Tanner codes utilizing soft-output guessing random additive noise decoding (SOGRAND). By soft-output decoding entire component codes rather than individual parity checks, we mitigate the effects of trapping sets and cycles, resulting in improved convergence. Because our decoder preserves the message passing structure of standard belief propagation (BP), it is compatible with many BP enhancements. We demonstrate this with OSD postprocessing, quaternary BP, and RelayBP, each yielding further gains. Standalone SOGRAND outperforms the standard BP+OSD baseline by over two orders of magnitude in logical error rate. In combination with the Relay principle, SOGRAND outperforms RelayBP by over one order of magnitude, providing a way forward for scalable decoding of the emerging class of Tanner-code-based quantum codes.

quant-ph · cs.IT

新论文 · v1arXiv:2611.10801

Trained, Frozen, or Absent: Identifying What a Quantum Layer Contributes to Cross-Sectional Equity Ranking

Chi-Sheng Chen, Xinyu Zhang, En-Jui Kuo, Rong Fu, Qiuzhe Xie, Fan Zhang

原文摘要

Hybrid quantumclassical models are increasingly proposed for nancial prediction, but reported gains are rarely separated from the classical components around them. We study a hybrid quantum temporal convolutional network for daily cross-sectional ranking of 2000 Tokyo Stock Exchange equities under a protocol built to make the quantum contribution identiable: six conditions (circuit trained, frozen or absent, a parameter-matched classical surrogate, and the circuit alone, trained or frozen) through one code path; four walk-forward folds with ve seeds; bootstrap intervals, Deated Sharpe Ratios, backtest-overtting probabilities and family-wise error control; ve classical baselines including a gradient-boosted tree; and a locked holdout. On 500 out-of-sample days two one-sided tests place the trained-versus-frozen dierence inside 0.03 annualised Sharpe (p = 0.0055, minimum detectable eect 0.02): the circuit is equivalent to a frozen one, not merely indistinguishable from it. With the circuit as the head's only input the two are equivalent inside 0.25; against the network with no circuit the design resolves only 0.50. No condition is distinguishable from zero (best De-ated Sharpe Ratio 0.17). The holdout reproduces the ablation on a protable window, and 2000 US equities reproduce it where every condition loses money.

quant-ph · cs.AI · q-fin.CP

版本更新 · v2arXiv:2509.16801

Sublinear Time Quantum Sensitivity Sampling

Zhao Song, David P. Woodruff, Lichen Zhang

原文摘要

We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume $n,d\geq\mathrm{poly}(k/ε)$ and, for regression, $n\geq\mathrm{poly}(d)$: - $k$-median/$k$-means: For $n$ points in $\mathbb{R}^d$, we build an $ε$-coreset of input points of size $\tilde O(k^{4/3}ε^{-2})$ (resp. $\tilde O(k^{3/2}ε^{-2})$) in time $\tilde O(ε^{-1}n^{0.5}dk^{1.67})$ (resp. $\tilde O(ε^{-1}n^{0.5}dk^{1.75})$). Our better $d$- and linear $1/ε$-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for $d\geqΩ(k^{7/3})$ (resp. $Ω(k^{2.5})$). - $\ell_p$ regression: For $\min_x\|Ax-b\|_p$, $A\in\mathbb{R}^{n\times d}$, we build an $ε$-coreset of size $\tilde O_p(d^{\max\{1,p/2\}}ε^{-2})$ in time $\tilde O_p(n^{0.5}d^{1.5}ε^{-1})$ for $p\leq 2$ and $\tilde O_p(n^{0.5}d^{p/4+1}(ε^{-1}+d^{0.5}))$ for $p>2$, matching [Liu and Ji, ICML'26] for $p\leq 2$ and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all $p>2$. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-$k$ approximation of $A\in\mathbb{R}^{d\times n}$ free of data-dependent parameters, running in $\tilde O(n^{0.5}dk^{0.5}ε^{-0.5})$ time with factored output (plus $\tilde O(nk^2ε^{-2})$ to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity $S$, any quantum algorithm outputting an $ε$-coreset of size $o(\sqrt{nS})$ needs $Ω(\sqrt{nS})$ queries, so our query complexity is optimal up to $\mathrm{poly}(ε^{-1},\log n)$ and VC-dimension factors.

cs.DS · cs.LG · quant-ph

新论文 · v1arXiv:2611.10796

BP-based qLDPC Decoding under Long-range Correlated Noise: Trapping Configurations and Prior Mismatch

Abhinav Dangi, Avhishek Chatterjee

原文摘要

We study the robustness of two state-of-the-art BP-based qLDPC decoders, Relay-BP and beam search, designed for independent noise when applied to spatially correlated noise with unchanged single-mechanism error probabilities. We generate correlated errors with a hidden Gaussian Markov random field, which lets us control the strength and range of the correlation while keeping every marginal error probability exact. This setting complements correlation-aware decoding: it asks how existing decoders perform when their assumed joint error model is mismatched. Across multiple tested circuits and code instances that we simulated, we observe that correlations can change logical error rates by orders of magnitude, reduce the finite-size distance advantage, and alter the relative ranking of Relay-BP, beam search, and BP-OSD. On one of the two tested circuits, Relay-BP and beam search become worse than BP-OSD, and increasing relay memory or beam width does not compensate for the degradation. Configuration analysis indicates that correlation primarily increases the probability of trapping configurations that are known to challenge these decoders; at matched error weight, correlated errors still cause decoding failures several times more often than i.i.d. errors. Finally, supplying the decoders with the marginals conditioned on the hidden field recovers most of the lost performance in the tested settings identifying prior mismatch as a major contributor to performance degradation under correlation.

cs.IT · quant-ph

新论文 · v1arXiv:2611.10793

Trainability-Simulability Tradeoff in Parameterized IQP-based Reinforcement Learning Policies

André Sequeira

原文摘要

Parameterized instantaneous quantum polynomial-time (IQP) circuits generate distributions conjectured to be hard to sample classically. As reinforcement learning (RL) policies, their $2^n$ measurement outcomes are typically mapped to a smaller action space by a classical decoder. This aggregation can mitigate initialization concentration while making the policy classically simulable. We characterize this tradeoff through the decoder's Fourier--Pauli expansion. Under independent uniform initialization, we express policy variance as an exact sum over groups of nonconstant Pauli components with identical active-generator signatures. Each group contributes its squared aggregate coefficient times $2^{-r}$, where $r$ is the binary rank of its active generators. An inverse-polynomial aggregate coefficient with logarithmic rank prevents exponential policy concentration. Sparse Pauli expansions and contiguous action bins permit efficient classical additive estimation of action probabilities. We introduce a majority decoder combining protected low-weight components with exponentially large exact Fourier support, preserving initialization nonconcentration while excluding polynomial-size enumeration of the exact expansion. Numerical experiments corroborate the variance laws. In ten-qubit CartPole experiments, majority achieves higher returns than recursive parity and the tested local readouts, while higher-weight Pauli sectors contribute an increasing relative share of gradient magnitude during training. A complementary 21-qubit block-chain policy outperforms an extensive pool of fully connected classical neural networks in episode efficiency, even though its bounded-width structure permits efficient classical simulation. These results guide decoder design for quantum and quantum-inspired RL, distinguishing policy nonconcentration, learning performance, and classical simulability.

quant-ph · cs.LG

版本更新 · v3arXiv:2602.11042

Characterizing the Trainability of Instantaneous Quantum Polynomial Circuit Born Machines

Kevin Shen, Susanne Pielawa, Vedran Dunjko, Hao Wang

原文摘要

Instantaneous Quantum Polynomial Circuit Born Machines (IQP-QCBMs) have been proposed as quantum generative models that combine a classically tractable training objective - based on the maximum mean discrepancy (MMD) - with a potential quantum advantage motivated by sampling-complexity arguments. While recent works have explored this model across various application domains, fundamental questions remain: does the model suffer from exponentially vanishing loss gradients, known as the barren plateau problem - a pervasive obstacle in quantum machine learning - and how do regimes of trainability relate to regimes of possible quantum advantage? Here, we address both questions analytically. To study trainability, we derive closed-form expressions for the variances of the partial derivatives of the MMD loss function and establish general upper and lower bounds. We explicitly characterize how trainability depends on the generator set and the spectrum of the chosen kernel, identifying regimes in which low Hamming-weight kernels avoid exponential gradient suppression under structured topologies. Regarding potential quantum advantage, we reformulate the anti-concentration property in terms of the same generator-set quantities that govern trainability, enabling a unified analysis. We show that sparse IQP architectures can produce classically intractable output distributions while simultaneously remaining trainable, at least at lower-weight frequencies. Our analytical results corroborate the numerical observations of prior work and provide principled guidelines for designing scalable IQP-QCBM architectures.

quant-ph · cs.LG

版本更新 · v3arXiv:2610.08299

Pauli Decomposition by Character Theory: A Memory-Bounded Algorithm for Qubits and Qudits

Mohammadreza Khellat, Mohammad Masoumi, Saman Nasoori, Soroush Nasoori

原文摘要

Pauli decomposition of an $n$-qubit operator is expensive if each of the $4^n$ Pauli strings is treated as an unstructured object. Labeling those strings by the configuration space $(\mathbb{Z}_2)^n$ makes them displacement operators $X^{\otimes x}Z^{\otimes z}$ on the computational space: shifts by~$x$ and multiplications by characters $Z^{\otimes z}$ in the computational basis. That labeling organizes the operator into $2^n$ fibers of length $2^n$, one per shift~$x$, each collecting the computational-basis amplitudes that hop by~$x$. Expanding each fiber function in the character basis of $(\mathbb{Z}_2)^n$ --- a length-$2^n$ Walsh--Hadamard transform --- recovers the Pauli coefficients at total cost $O(n\cdot4^n)$. The same fiber / shift--character picture extends to $(\mathbb{Z}_p)^n$ (Heisenberg--Weyl qudits). \texttt{paulikit} is a memory-bounded realization for qubits: for matrix-sparse inputs, peak memory need not densify to a full $2^n\times2^n$ operator. Performance is checked on a stated low-end GNU/Linux platform for a coupled-oscillator sweep beyond a billion Pauli terms.

quant-ph · cs.MS

新论文 · v1arXiv:2611.10640

A Grover-Amplified Oracle for Maximum Clique on Graph, Minimum Hitting set and Dualizations on Hypergraphs Built on Quantum Phase Estimation

Francisco Piñero, Fernando L. \Pelayo, Hernan I. de la Cruz, Jose J. Paulet, Mauro Mezzini, Fernando Cuartero

原文摘要

In this paper, we use a quantum circuit called the Graph Encoding Operator which, applied to the complement $\bar G$ of any graph $G$, yields an oracle for the maximum clique problem suitable for amplification via Grover's algorithm. Analogously, we devise a Hypergraph Encoding Operator which, when applied to a hypergraph $\mathcal H$, yields an oracle for the minimum hitting set suitable for amplification via Grover's algorithm. Interestingly, the latter oracle provides, when measured, an approximation of the number of hitting sets of the hypergraph, thus solving the dualization problem for positive Boolean functions represented in a positive irredundant disjunctive normal form. We give the full construction of both operators, prove their correctness, analyze their complexity, and provide an implementation on a quantum simulator. We discuss the resulting complexity, contrast them with existing quantum computer algorithms based on Grover search and we will show that our algorithms outperform, to the best of our knowledge, all of the previous algorithms on space computational complexity by requiring only $O(N)$ number of qubits with respect to the number of vertices $N$, for representing both graphs and hypergraphs in the encoding operator and, consequently, results in an oracle for both graphs and hypergraphs that uses only $O(N)$ qubits even when the hypergraph contains an exponential (on the number of vertices) number of hyperedges.

quant-ph · cs.CC

版本更新 · v2arXiv:2410.04252

Lazy Qubit Reordering for Accelerating Parallel State-Vector-based Quantum Circuit Simulation

Yusuke Teranishi, Shoma Hiraoka, Wataru Mizukami, Masao Okita, Fumihiko Ino

原文摘要

This article proposes two quantum operation scheduling methods for accelerating parallel state-vector-based quantum circuit simulation using multiple graphics processing units (GPUs). The proposed methods reduce all-to-all communication caused by qubit reordering, which can dominate the overhead of parallel simulation. Our out-of-order approach eliminates redundant reorderings by introducing intentional delays in reordering communications such that multiple reorderings can be aggregated into a single reordering. The delays are carefully introduced based on the principles of time-space tiling, or a cache optimization technique for classical computers, which we use to arrange the execution order of quantum operations. Moreover, we develop these methods tailored for two primary procedures in variational quantum eigensolver simulation: quantum state update (QSU) and expectation value computation (EVC). Our QSU simulation takes an advantage of the hierarchical interconnection of GPU systems to avoid slow inter-node communication. On the other hand, our EVC simulation reduces the number of reorderings by diagonalization of Pauli strings. Experimental validation on 32-GPU executions demonstrates acceleration in QSU and EVC$\unicode{x2014}$up to 54$\times$ and 1,657$\times$, respectively$\unicode{x2014}$compared to an inorder-based method. We believe that our out-of-order approach is useful for accelerating large-scale quantum circuit simulations, including QSU and/or EVC that operate qubits in a regular manner.

quant-ph · cs.DC

新论文 · v1arXiv:2611.10588

Initialization masks overcome decoding obstructions in compressed QAOA

Emilio Semre, Steven Frankel

原文摘要

In compressed quantum optimization, a variational state is converted into a classical assignment by decoding noncommuting observables. We show that this step creates structural restrictions that changing the initialization can remove, even when increasing circuit depth cannot. For an explicit infinite family of connected cubic graphs on $n=3r$ vertices, with a fixed Pauli encoding and deterministic sign decoder, every all-plus QAOA circuit has cut at most $2r$, at every finite depth and every real angle sequence. A uniform signed product-state mask at fixed depth-one angles has expected cut $13r/4$, an additive advantage $5n/12$; an infinite subfamily admits an optimal mask. A second construction retains a linear depth-one separation under weak weighted couplings, a bounded cost-angle domain and a specified production-encoder ordering. Noiseless simulations then test classical mask selection before energy optimization. On 1,699 random cubic MaxCut instances, one selected mask achieves mean ratio $0.9100$, versus $0.7067$ for the all-plus $X$ baseline and $0.9125$ for the best of $r^2$ separately optimized random masks. On complete cohorts of weighted MaxCut, sparse Ising, Max-2-XOR and Max-2-SAT, the selected mask also improves on the baseline at every size, but it trails the pool at small sizes and leads it significantly only at the larger MaxCut and Ising sizes. Finite-pool order statistics separate the effect of selection from that of drawing a random mask. The results distinguish decoded expressivity from optimized energy and empirical performance; they do not establish a quantum computational advantage.

quant-ph · cs.CC

版本更新 · v4arXiv:2603.27397

Benchmarking Quantum Computers via Protocols, Comparing Superconducting and Ion-Trap Quantum Technology

Nitay Mayo, Tal Mor, Yossi Weinstein

原文摘要

Both Superconducting and Ion-Trap are leading quantum architectures common in the current landscape of the quantum computing field, each with distinct characteristics and operational constraints. Understanding and measuring the underlying $\underline{\text{quantumness}}$ of these devices is essential for assessing their readiness for practical applications and guiding future progress and research. Building on earlier work (Meirom, Mor and Weinstein Arxiv 2505.12441), we utilize a benchmarking strategy applicable for comparing these two architectures by measuring "quantumness" directly on optimal sub-chips. Distinct from existing metrics, our approach employs rigorous binary fidelity thresholds derived from the classical limits of state transfer. This enables us to definitively establish quantum advantage of a designated sub-region. Here we apply this quality assurance methodology to platforms from both technologies. This comparison provides a protocol-based evaluation of quantumness advantage, revealing not only the strengths and weaknesses of each tested chip and its sub-chips but also offering a common language for their assessment. By abstracting away technical differences in the final result, we demonstrate a benchmarking strategy that bridges the gap between disparate quantum-circuit technologies, enabling fair performance comparisons and establishing a critical foundation for evaluating future claims of quantum advantage. We encourage other companies to emulate the independent qubit availability and the fair pricing, as do IBM and AQT, which allow researchers to perform such assessments. In the discussion section, we consider an important future direction of using "benchmarking via protocols" also for fault-tolerant quantum computing with logical qubits.

quant-ph · cs.DC · cs.ET

新论文 · v1arXiv:2611.10544

Compact Quantum Channel Attention for Static ASL Recognition: A Controlled Study with Parameter-Matched Baselines

Ronak Bhalgami, Deep Kothadiya, Nikita Bhatt

原文摘要

Hybrid quantum-classical models often report good accuracy on image tasks, but it is rarely clear whether the quantum part is responsible. This paper proposes QCA-DenseNet, a static American Sign Language (ASL) recognition pipeline in which an eight-qubit variational circuit acts as a channel-attention gate on DenseNet121 features. The quantum channel attention (QCA) gate has 17,464 parameters, 7.51 times fewer than a squeeze-and-excitation (SE) block. The pipeline is tested on 1,815 MU HandImages images by holding out one of five signers at a time, and a frozen-backbone ablation uses small parts of the Kaggle ASL Alphabet data. On unseen signers, QCA-DenseNet reaches 94.50% mean accuracy, above SE (93.72%) and within 0.28 points of the best model. A matched classical MLP and a model without attention perform about the same, and no difference is significant. QCA gives a much smaller attention gate without a detectable loss in accuracy, but no quantum advantage.

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

新论文 · v1arXiv:2611.10527

QAOA Inside ADMM: Subproblem Wins Do Not Become Decomposition Wins at Matched Budgets

Mohammad Arif Hossain, Sanim Yousuf Fahim

原文摘要

We benchmark the quantum approximate optimization algorithm (QAOA) as the binary subproblem solver in a two-block alternating direction method of multipliers (ADMM) for mixed-binary problems against classical solvers under matched budgets. With 23 optimizer evaluations per subproblem, scoring determines the comparison: on its final readout, the optimized QAOA loses to random search at $n=12$ and 16 binary variables (inconclusive at 20; exploratory and post hoc tests). When credited with its best sample, it wins. In a noiseless 12-qubit simulation, transferred-angle depth-2 QAOA finds the exact optimum of 97.3\% of planted-family subproblems, against 50.6\%--67.4\% for the four strongest local heuristics (100\% against 90.4\%--94.4\% crediting the four best bitstrings) and a not significantly different 96.5\% for semidefinite rounding with local search (SDP+LS). Under our evaluation-counting convention, its time to solution there is a factor of three to five below the local heuristics' but grows with a larger exponent; it is ten times that of SDP+LS and, in seconds, 54 times that of tabu search with restarts. For the benchmark class, an unconstrained binary quadratic problem in disguise, ADMM's binary step is a proximal step on the reduced problem: at unit penalty ADMM re-solves it, and for larger penalties exact solutions increasingly stall. On two families that do not reduce to one, less accurate solvers found the problem optimum more often at unit and larger penalties. No family gave QAOA a better ADMM outcome than the best classical solver and penalty. The benchmark includes a correctness gate and a log of its hypothesis tests.

quant-ph · cs.DC

版本更新 · v4arXiv:2510.16420

Exact Quantum Circuit Optimization is co-NQP-hard

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

原文摘要

As quantum computing resources remain scarce and error rates high, minimizing the resource consumption of quantum circuits is essential for achieving practical quantum advantage. Here we consider the natural problem of, given a circuit $C$, computing a circuit $C'$ that behaves equivalently on a desired subspace, and that minimizes a quantum resource type, expressed as the count or depth of (i) all gates, or (ii) non-Clifford gates, or (iii) superposition gates, or (iv) entanglement gates. We show that, when $C$ is expressed over any gate-set that can implement the H and TOF gates exactly, a standard property of approximately universal gate-sets, each of the above optimization problems is hard for co-NQP, and hence outside the Polynomial Hierarchy, unless the Polynomial Hierarchy collapses. This complements a recent result of Van de Wetering and Amy (arXiv, 2023) which establishes an NP-hardness lower bound when equivalence is over the full state space, and tightens the gap to the corresponding $\text{NP}^\text{NQP}$ upper bound known for cases (i)-(iii) over Clifford+T and (i)-(iv) over H+TOF circuits. Our result also generalizes a result by Tanaka (Int. J. Quantum Inf., 2010) to other gate-sets and quantum resources.

quant-ph · cs.CC

版本更新 · v4arXiv:2609.10802

A Time-Frequency Framework for GKP Codes

Franz Luef, Eduard Ortega

原文摘要

We develop a time--frequency framework for lattice GKP codes in which ideal codewords are realized in the modulation space $M^\infty$ and identified, through a vector-valued Zak transform, with a finite logical fibre over the continuous syndrome torus. Multi-window Gabor analysis then represents the logical vector by a finite block of adjoint-lattice coefficients. We prove that the normalized block map is an isometry, obtain an explicit recovering projection, and derive stable logical reconstruction. We further construct normalizable GKP approximants as lattice-envelope Gabor multipliers and establish weak-$*$ convergence and asymptotically isometric encoding. Finally, we recover displacement syndromes from phase relations between translated coefficient blocks and quantify their stability under additive perturbations.

math-ph · cs.IT · math.FA · math.OA · quant-ph

版本更新 · v2arXiv:2503.07992

Certified Lipschitz Bounds for Hybrid Quantum-Classical Decision Models

Sajjad Hashemian, Mohammad Saeed Arvenaghi

原文摘要

We study certified upper bounds on Lipschitz constants for hybrid quantum-classical decision models, which combine classical neural-network layers with parameterized quantum circuits. We pair an SDP-based certificate for classical layers with an exact spectral characterization for probability-output quantum models. For hybrid architectures, these componentwise estimates are connected through the encoding maps to obtain a certified composition bound for the complete model. The resulting bounds support sensitivity analyses relevant to robustness, stability, generalization, and fairness.

quant-ph · cs.AI

新论文 · v1arXiv:2611.10283

Regev's Reduction Reaches Reconstruction

Stephen P. Jordan, Quynh T. Nguyen, Leo Zhou

原文摘要

Regev's reduction uses a quantum Fourier transform to carry out reductions between various problems related to lattices and codes. We apply it to the problem of sampling from Gibbs distributions of certain classical spin glass Hamiltonians, which can equivalently be thought of as cost functions for average-case instances of an optimization problem called $D$-regular max-$k$-LINSAT. This problem becomes hard at low temperature. Here, we use a quantum decoding algorithm called Belief Propagation with Quantum Messages (BPQM) to solve the decoding problem arising from Regev's reduction. Our main contribution is a proof that the minimum temperature reachable using Regev+BPQM is exactly equal to the reconstruction threshold temperature for noisy channels transmitting signals on a tree network. This equality can be understood via Renes' duality between classical and quantum channels, which we use to show that quantum decoding is possible exactly when classical reconstruction on the dual problem is impossible. M{é}zard and Montanari identified this reconstruction temperature with a dynamical glass transition predicted by the one-step replica-symmetry breaking (1RSB) cavity equation. It is conjectured that local samplers such as Metropolis Monte Carlo and Glauber dynamics cannot equilibrate efficiently below this reconstruction temperature but may do so above it; our large numerical experiments show close agreement with this prediction across hundreds of different problem parameters. Therefore, our results rigorously show that Regev+BPQM reaches a temperature for which, to our knowledge, there is no matching classical guarantee, and brings Regev+BPQM to the conjectured limit of efficient Gibbs sampling by classical local dynamics.

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

新论文 · v1arXiv:2611.09809

超越 n/2 阈值:计算汉明重量与对称函数的量子查询复杂度

Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions

Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu, Vahab Mirrokni, Jianan Shao, David P. Woodruff

AI 速读 基于摘要

作者构造了一类需要 n/2+Ω(n^{1/3}) 次量子查询的对称布尔函数,并给出用 n/2+O(n^{1/3}) 次查询精确恢复汉明重量的算法,从而确定该加性阶数的最优性。

quant-ph · cs.CC

查看原文摘要

The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+Ω(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.

新论文 · v1arXiv:2611.09773

Aaronson-Ambainis 猜想的证明

A proof of the Aaronson-Ambainis conjecture

David Turturean

AI 速读 基于摘要

作者证明低次有界多项式在离散立方体上必有有影响的变量,从而证实 Aaronson-Ambainis 猜想。

cs.CC · quant-ph

查看原文摘要

Aaronson and Ambainis conjectured that every bounded polynomial of low degree on the discrete cube has an influential variable. They showed that the conjecture implies that the acceptance probability of every quantum algorithm making $T$ queries can be approximated on most inputs by a classical algorithm making $\mathrm{poly}(T)$ queries. We prove their conjecture: every function $f\colon\{-1,1\}^n\to[-1,1]$ of degree at most $d\ge1$ has a variable of influence at least $c\,\operatorname{Var}(f)^{5/2}/d^{6}$, where $c>0$ is an absolute constant. In the original formulation, for polynomials of degree at most $d$ with values in $[0,1]$ on $\{0,1\}^n$ and variance at least $\varepsilon$, this gives a variable of influence at least $(\varepsilon/d)^{7}$. The proof is elementary, with steps inspired by works of others. Thus, as Aaronson and Ambainis anticipated, superpolynomial quantum speedups in the query model require structure, such as a promise on the inputs.

版本更新 · v3arXiv:2511.16558

在图上以多项式时间模拟高斯玻色采样

Simulating Gaussian boson sampling on graphs in polynomial time

Konrad Anand, Zongchen Chen, Mary Cryan, Graham Freifeld, Leslie Ann Goldberg, Heng Guo, Xinyuan Zhang

AI 速读 基于摘要

作者报告,与图上高斯玻色采样(GBS)相关的一个分布以及另一个与玻色采样相关的分布,都可以在经典计算下以多项式时间采样。

quant-ph · cs.DS

查看原文摘要

We show that a distribution related to Gaussian Boson Sampling (GBS) on graphs can be sampled classically in polynomial time. Graphical applications of GBS typically sample from this distribution, and thus quantum algorithms do not provide exponential speedup for these applications. We also show that another distribution related to Boson sampling can be sampled classically in polynomial time.

版本更新 · v4arXiv:2607.21551

Unconditional Unclonable Encryption

Prabhanjan Ananth, Seyoon Ragavan, Amit Sahai

原文摘要

We give an unconditional construction of information-theoretically secure one-time private-key unclonable encryption for one-bit messages, with efficient encryption and decryption and exponentially small unclonable-indistinguishability advantage. Previous work by Bhattacharyya and Culf (Nature Physics, 2026) and Bhattacharyya, Broadbent, and Culf (arXiv:2603.08916) either only showed inverse-polynomial security loss or required inefficient encryption/decryption operations; we avoid both of these caveats. Our scheme's key is a uniformly random non-identity phase-free Pauli on $n$ qubits, and bit $a$ is encrypted as a random $(-1)^a$ eigenstate of that Pauli. We prove that the probability that both receivers recover the bit is at most $1/2 + O\left(2^{-n/2}\right).$ By a lower bound due to Broadbent, Culf, and Rochette (IACR Communications in Cryptology, 2026), this is the best probability bound achievable with $n$-qubit ciphertexts while ensuring perfect correctness (up to the constant hidden in the $O(\cdot)$).

quant-ph · cs.CR

新论文 · v1arXiv:2611.09659

Quantum Integration Software Suite For HPC-Quantum Computing Workflows

Mateusz Meller, Joseph C. R. Thacker, Thomas W. Keal, Vendel Szeremi

原文摘要

In this work, we focus on addressing challenges related to modelling the integration of conventional high-performance computing (HPC) and quantum computing (QC). We introduce the Quantum Assembly Compiler (QASC) for OpenQASM3.0 files. The compiler produces an executable that leverages the high-performance simulator QuEST to simulate quantum programs. Additionally, we introduce a performance modelling tool, QACC-perf, which can estimate the cost of integrating QC in classical HPC workflows, as well as the execution time of the quantum circuits. Finally, we demonstrate the utility of these tools in the context of multiscale quantum chemistry workflows using the ChemShell computational chemistry environment.

quant-ph · cs.ET

版本更新 · v2arXiv:2607.15873

A Physically-Realisable Quantum Programming Language with Quantum-Controlled Quantum Channels

Kengo Hirata, Takeshi Tsukada

原文摘要

In contrast to a classical bit, which can only take the value $0$ or $1$, its quantum counterpart---a qubit---can exist in a superposition of $0$ and $1$. This is a superposition of data values, and it is then tempting to superpose programs as well. Indeed, a particular superposition of programs, known as the quantum SWITCH, has attracted considerable attention. A natural way to superpose programs is conditional branching on quantum data, and several studies have pursued this idea. However, there is a well-known semantic difficulty with this approach, and the fundamental question of whether the languages proposed in prior work can be physically realised remains open. This paper proposes a physically realisable quantum programming language with quantum branching over quantum channels. We first analyse the semantic difficulty from an implementation perspective and show that the difficulty is caused by arbitrariness in the implementation. We then design a language that is free from this arbitrariness. As expected from its implementation-oriented design, our language is physically realisable. We argue for this from two directions: first, we give a method for compiling programs into quantum circuits; and second, we show that our programs stay within the physically admissible range, namely, that they neither yield probabilities greater than one nor violate causal inequalities. The absence of such violations is established through the inclusion of our language in QC-QC, a notion of realisability studied in physics.

cs.PL · cs.LO · quant-ph

版本更新 · v2arXiv:2610.37122

Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions

Kuan Cheng, Ruiyang Wu

原文摘要

We establish an equivalence between matrix samplers and quantum-proof randomness extractors. The classical sampler-extractor equivalence is established by a seminal work of Zuckerman (Random Structures & Algorithms, 1997). Using this equivalence, we construct explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity via constructing quantum-proof extractors. Specifically for matrix dimension $D$, accuracy $\varepsilon$ and failure probability $δ\leq\varepsilon$, our matrix sampler uses $$ m+O_α(\log(D/δ))\text{ random bits and } O_α\!\left(\varepsilon^{-2-α}\log^{1+α}(D/δ)\right)\text{ samples}, $$ for any constant $α>0$. Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under optimal random seed length, we can replace the $\operatorname{poly} D$ dependence in the number of samples by $O(\log^{1+α} D)$. Under the same scale of sample size, we can remove their $\log\log D$ factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length $n-O_α(a+\log(1/η))$ and seed length at most $(1+α)\log a+(2+α)\log(1/η)+O_α(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $η$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-Ω(n)}$, having optimal seed length $O(\log(n/η))$ and output length $Ω(n)$, improving previous constructions.

cs.CC · quant-ph