Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.12858

Shots-to-Approximate-Solution Scaling in Neutral-Atom Quantum Optimization

Junwoo Jung, Jaewook Ahn

quant-phphysics.atom-phSubmitted Aug 13, 2026• Announced Aug 14, 2026• 0 citations
arXivHTMLPDF

Abstract

Whether neutral-atom quantum optimization protocols exhibit genuine concentration toward low-energy solution structure remains an open question. Here, we introduce a shots-to-approximate-solution metric, STS(r), where r denotes the approximation ratio, and evaluate it using postprocessed outputs modeled by a degeneracy-weighted shell distribution governed by a single effective parameter, $β$, that quantifies concentration toward near-optimal independent sets. To extract the genuine concentration effect in the quantum data, we apply identical postprocessing to both experimental bitstrings and randomly generated bitstrings with matched excitation density, thereby constructing an excitation-matched random baseline. Experiments on programmable Rydberg-atom arrays with system sizes up to 125 sites show that quantum annealing consistently exceeds the random baseline, demonstrating enhanced concentration toward low-energy solution structure beyond what can be attributed solely to excitation density. The results further reveal two distinct target-dependent regimes. For near-exact targets with $r \approx 1$, the required shot count grows exponentially with system size and is reduced at the same exponential level by quantum annealing within the shell-model description. By contrast, for relaxed targets, the shot cost becomes effectively constant, and the corresponding quantum enhancement diminishes, with the classical postprocessing heuristic alone reaching the target in order-unity attempts. Together, these results establish an operational method for quantifying quantum optimization performance and clarify the regimes under which quantum approaches can yield practical benefits.

Comments
17 pages, 8 figures ; data and code available at https://doi.org/10.6084/m9.figshare.33205122

Related papers

Quantum-Enhanced Deterministic Inference of $k$-Independent Set Instances on Neutral Atom Arrays

Juyoung Park, Junwoo Jung, Jaewook Ahn

Noisy quantum annealing experiments on Rydberg atom arrays produce measurement outcomes that deviate from ideal distributions, complicating performance evaluation. To enable a data-driven benchmarking methodology for quantum devices that accounts for both solution quality and the classical computational cost of inference from noisy measurements, we introduce deterministic error mitigation (DEM), a shot-level inference procedure informed by experimentally characterized noise. We demonstrate this approach using the decision version of the $k$-independent set problem. Within a Hamming-shell framework, the DEM candidate volume is governed by the binary entropy of the bit-flip error rate, yielding an entropy-controlled classical postprocessing cost. Using experimental measurement data, DEM reduces postprocessing overhead relative to classical inference baselines. Numerical simulations and experimental results from neutral atom devices validate the predicted scaling with system size and error rate. These scalings indicate that one hour of classical computation on an Intel i9 processor corresponds to neutral atom experiments with up to $N=250-450$ atoms at effective error rates, enabling a direct, cost-based comparison between noisy quantum experiments and classical algorithms.

quant-pharXiv:2602.05432•Feb 6, 2026•0 citations

Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization

Anonymous, Denis A. Kulikov, B. I. Bantysh +3 more

We study a modified fixed-point version of the Quantum Approximate Optimization Algorithm (fpQAOA), where parameters are trained classically on small instances and then transferred to larger problems. Our scheme combines three ingredients: (i) targeting approximate solutions via a prescribed approximation ratio (AR), (ii) scaling the circuit depth linearly with the problem size using a two-parameter sin-cos angle encoding, and (iii) normalizing QUBO Hamiltonians by their Frobenius norm. Noiseless numerical simulations (for system sizes up to 30 qubits) across a variety of random QUBO ensembles show that with these modifications the median number of quantum circuit runs ("shots") required to achieve AR=0.95 counterintuitively decreases towards a nearly constant value as the problem size increases, while the per-shot time remains polynomial. Extrapolation of this finite-size behavior is consistent with an effectively constant sampling complexity. Moreover, removing any single component of the scheme restores rapid growth of the required number of shots, highlighting the synergistic nature of the three modifications. These empirical findings suggest that fpQAOA, equipped with the proposed protocol, may achieve scalable approximate performance with polynomial-depth circuits for the considered problem classes.

arXiv:2509.19035•Physical Review A•Aug 3, 2026•1 citation

Iterative Optimization with Partial Convergence Guarantees on Neutral Atom Quantum Computers

Cédrick Perron, Yves Bérubé-Lauzière, Victor Drouin-Touchette

Neutral atom quantum computers (NAQCs) have emerged as a promising platform for solving the maximum weighted independent set (MWIS) problem. However, analog quantum approaches face two key limitations: constraints of the atomic layout on realizable graph geometries and the absence of performance guarantees. We introduce Lp-Quts, a hybrid quantum-classical framework that integrates an NAQC sampler into a classical cutting-plane algorithm. At each iteration, a relaxed linear program (RLP) bounds the MWIS and induces a reduced graph from which independent sets are sampled using an analog quantum sampler. A novel sample-informed separation problem guides odd-cycle cut selection and accelerates convergence. For t-perfect graphs, Lp-Quts inherits polynomial-time convergence guarantees from the classical theory of cutting planes. We evaluate our approach on instances with up to 300 vertices -- a scale that exceeds the capabilities of current NAQC hardware. In this regime, Lp-Quts reaches solutions within 5--10\% of optimality, outperforming direct analog quantum protocols and greedy baselines under equal sampling budgets. As expected, simulated annealing remains the strongest sample-based solver at this scale. These results demonstrate how quantum samplers can be effectively embedded within classical optimization frameworks to deliver near-optimal solutions with reduced quantum resources while preserving formal guarantees.

quant-pharXiv:2603.28933•Apr 1, 2026•0 citations

Beyond Exact Recovery: Operational Success Probability and Sampling Cost for Approximate Quantum Optimization under Stochastic Uncertainty

Roberto Garrone

Abstract Approximate optimization algorithms are commonly evaluated through exact optimum recovery or objective-space approximation, although these criteria need not coincide with the quality of the resulting decision in its downstream operating environment. This paper develops an end-to-end evaluation framework that separates three notions of solver success: exact recovery of the mathematical optimum, near-optimality with respect to the optimization surrogate, and operational acceptability under stochastic downstream evaluation. We study the framework using a small binary inventory-control benchmark represented by a calibrated and held-out-validated QUBO surrogate and solved with exact enumeration, greedy search, simulated annealing, uniform feasible sampling, and ideal QAOA at depths p=1,2,3. The results show that mathematical near-optimality and downstream operational acceptability define distinct solution sets. For QAOA, the probability mass assigned to operationally acceptable solutions can differ materially from both exact-recovery and QUBO-near-optimal probability, producing substantial differences in the number of measurements required to observe an acceptable solution. For n=8 at p=2, the median number of shots required for 95% observation probability decreases from 392 under exact recovery to 84 under QUBO near-optimality and 31 under the operational criterion. However, operational success alone can be misleading when acceptable states are abundant. We therefore use a descriptive enrichment comparison against uniform feasible sampling. Statistically supported enrichment is observed only in selected regimes, while classical greedy and simulated-annealing baselines outperform QAOA on these small instances. The results therefore do not indicate quantum advantage; rather, they show that solver evaluation can change materially when success is defined in terms of downstream decision consequences rather than surrogate-objective recovery alone. The QAOA statevector implementation and selected frozen confirmatory cases were independently reproduced with Qiskit and Qiskit Aer to floating-point precision.

•Oct 27, 2026•0 citations

Measurements Number Scaling in the Quantum Approximate Optimization Algorithm for MaxCut: A Statistical Analysis

Inbar Chefer, Uri Shaham, Adi Makmal

We provide a statistical analysis of the measurement (shot) requirements of the quantum approximate optimization algorithm (QAOA) for the MaxCut problem. We derive sufficient conditions on the number of shots per cost operator evaluation to: (a) estimate the expected cost to within a relative error $δ$ and a confidence $1-ε$, and (b) ensure SGD-based parameter optimization converges to a target relative suboptimality level with high probability. In addition, we provide an explicit bound on the number of SGD iterations required to reach the target accuracy. Our analysis reveals an unexpected scaling phenomenon: for specific graph classes, which we formally characterize, the total shot budget needed to achieve a fixed relative-performance metric decreases as the instance size grows. This result complements earlier cost function concentration arguments regarding parameter optimization redundancy, thereby highlighting the potential for high-performance, low-overhead QAOA implementations for large-scale MaxCut instances. To assist practitioners, we translate our analytical findings into practical rules of thumb for shot-budget allocation and validate these results with numerical simulations, offering new insights into the interplay between graph size, structural complexity, and resource requirements in QAOA.

quant-pharXiv:2607.03340•Jul 6, 2026•0 citations

Complexity Barriers to State Preparation in Quantum Approximate Optimization

Stuart Hadfield

For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

quant-pharXiv:2609.31520•Sep 28, 2026•0 citations
Whether neutral-atom quantum optimization protocols exhibit genuine concentration toward low-energy solution structure remains an open question. Here, we introduce a shots-to-approximate-solution metric, STS(r), where r denotes the approximation ratio, and evaluate it using postprocessed outputs modeled by a degeneracy-weighted shell distribution governed by a single effective parameter, βββ, that quantifies concentration toward near-optimal independent sets. To extract the genuine concentration effect in the quantum data, we apply identical postprocessing to both experimental bitstrings and randomly generated bitstrings with matched excitation density, thereby constructing an excitation-matched random baseline. Experiments on programmable Rydberg-atom arrays with system sizes up to 125 sites show that quantum annealing consistently exceeds the random baseline, demonstrating enhanced concentration toward low-energy solution structure beyond what can be attributed solely to excitation density. The results further reveal two distinct target-dependent regimes. For near-exact targets with r≈1r \approx 1r≈1, the required shot count grows exponentially with system size and is reduced at the same exponential level by quantum annealing within the shell-model description. By contrast, for relaxed targets, the shot cost becomes effectively constant, and the corresponding quantum enhancement diminishes, with the classical postprocessing heuristic alone reaching the target in order-unity attempts. Together, these results establish an operational method for quantifying quantum optimization performance and clarify the regimes under which quantum approaches can yield practical benefits.
Quantum-Enhanced Deterministic Inference of kkk-Independent Set Instances on Neutral Atom Arrays
Noisy quantum annealing experiments on Rydberg atom arrays produce measurement outcomes that deviate from ideal distributions, complicating performance evaluation. To enable a data-driven benchmarking methodology for quantum devices that accounts for both solution quality and the classical computational cost of inference from noisy measurements, we introduce deterministic error mitigation (DEM), a shot-level inference procedure informed by experimentally characterized noise. We demonstrate this approach using the decision version of the kkk-independent set problem. Within a Hamming-shell framework, the DEM candidate volume is governed by the binary entropy of the bit-flip error rate, yielding an entropy-controlled classical postprocessing cost. Using experimental measurement data, DEM reduces postprocessing overhead relative to classical inference baselines. Numerical simulations and experimental results from neutral atom devices validate the predicted scaling with system size and error rate. These scalings indicate that one hour of classical computation on an Intel i9 processor corresponds to neutral atom experiments with up to N=250−450N=250-450N=250−450 atoms at effective error rates, enabling a direct, cost-based comparison between noisy quantum experiments and classical algorithms.
We study a modified fixed-point version of the Quantum Approximate Optimization Algorithm (fpQAOA), where parameters are trained classically on small instances and then transferred to larger problems. Our scheme combines three ingredients: (i) targeting approximate solutions via a prescribed approximation ratio (AR), (ii) scaling the circuit depth linearly with the problem size using a two-parameter sin-cos angle encoding, and (iii) normalizing QUBO Hamiltonians by their Frobenius norm. Noiseless numerical simulations (for system sizes up to 30 qubits) across a variety of random QUBO ensembles show that with these modifications the median number of quantum circuit runs ("shots") required to achieve AR=0.95 counterintuitively decreases towards a nearly constant value as the problem size increases, while the per-shot time remains polynomial. Extrapolation of this finite-size behavior is consistent with an effectively constant sampling complexity. Moreover, removing any single component of the scheme restores rapid growth of the required number of shots, highlighting the synergistic nature of the three modifications. These empirical findings suggest that fpQAOA, equipped with the proposed protocol, may achieve scalable approximate performance with polynomial-depth circuits for the considered problem classes.
Neutral atom quantum computers (NAQCs) have emerged as a promising platform for solving the maximum weighted independent set (MWIS) problem. However, analog quantum approaches face two key limitations: constraints of the atomic layout on realizable graph geometries and the absence of performance guarantees. We introduce Lp-Quts, a hybrid quantum-classical framework that integrates an NAQC sampler into a classical cutting-plane algorithm. At each iteration, a relaxed linear program (RLP) bounds the MWIS and induces a reduced graph from which independent sets are sampled using an analog quantum sampler. A novel sample-informed separation problem guides odd-cycle cut selection and accelerates convergence. For t-perfect graphs, Lp-Quts inherits polynomial-time convergence guarantees from the classical theory of cutting planes. We evaluate our approach on instances with up to 300 vertices -- a scale that exceeds the capabilities of current NAQC hardware. In this regime, Lp-Quts reaches solutions within 5--10\% of optimality, outperforming direct analog quantum protocols and greedy baselines under equal sampling budgets. As expected, simulated annealing remains the strongest sample-based solver at this scale. These results demonstrate how quantum samplers can be effectively embedded within classical optimization frameworks to deliver near-optimal solutions with reduced quantum resources while preserving formal guarantees.
Abstract Approximate optimization algorithms are commonly evaluated through exact optimum recovery or objective-space approximation, although these criteria need not coincide with the quality of the resulting decision in its downstream operating environment. This paper develops an end-to-end evaluation framework that separates three notions of solver success: exact recovery of the mathematical optimum, near-optimality with respect to the optimization surrogate, and operational acceptability under stochastic downstream evaluation. We study the framework using a small binary inventory-control benchmark represented by a calibrated and held-out-validated QUBO surrogate and solved with exact enumeration, greedy search, simulated annealing, uniform feasible sampling, and ideal QAOA at depths p=1,2,3. The results show that mathematical near-optimality and downstream operational acceptability define distinct solution sets. For QAOA, the probability mass assigned to operationally acceptable solutions can differ materially from both exact-recovery and QUBO-near-optimal probability, producing substantial differences in the number of measurements required to observe an acceptable solution. For n=8 at p=2, the median number of shots required for 95% observation probability decreases from 392 under exact recovery to 84 under QUBO near-optimality and 31 under the operational criterion. However, operational success alone can be misleading when acceptable states are abundant. We therefore use a descriptive enrichment comparison against uniform feasible sampling. Statistically supported enrichment is observed only in selected regimes, while classical greedy and simulated-annealing baselines outperform QAOA on these small instances. The results therefore do not indicate quantum advantage; rather, they show that solver evaluation can change materially when success is defined in terms of downstream decision consequences rather than surrogate-objective recovery alone. The QAOA statevector implementation and selected frozen confirmatory cases were independently reproduced with Qiskit and Qiskit Aer to floating-point precision.
We provide a statistical analysis of the measurement (shot) requirements of the quantum approximate optimization algorithm (QAOA) for the MaxCut problem. We derive sufficient conditions on the number of shots per cost operator evaluation to: (a) estimate the expected cost to within a relative error δδδ and a confidence 1−ε1-ε1−ε, and (b) ensure SGD-based parameter optimization converges to a target relative suboptimality level with high probability. In addition, we provide an explicit bound on the number of SGD iterations required to reach the target accuracy. Our analysis reveals an unexpected scaling phenomenon: for specific graph classes, which we formally characterize, the total shot budget needed to achieve a fixed relative-performance metric decreases as the instance size grows. This result complements earlier cost function concentration arguments regarding parameter optimization redundancy, thereby highlighting the potential for high-performance, low-overhead QAOA implementations for large-scale MaxCut instances. To assist practitioners, we translate our analytical findings into practical rules of thumb for shot-budget allocation and validate these results with numerical simulations, offering new insights into the interplay between graph size, structural complexity, and resource requirements in QAOA.
For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For d∈{2,3}d\in\{2,3\}d∈{2,3} variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor 1/d21/d^21/d2. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard nnn-qubit families with relative quantum relaxation excess Θ(1/n)Θ(1/n)Θ(1/n), while the maximally mixed state has energy approximation ratio 1−Θ(1/n)1-Θ(1/n)1−Θ(1/n), zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.