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

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

Roberto Garrone

Published Oct 27, 2026• 0 citations
PDF (CC BY)Publisher

Abstract

Abstract Approximate optimizers are usually judged by how well they recover a mathematical optimum or a near-optimal objective value. In many applications, however, the optimization model is only a surrogate for a downstream decision problem, so mathematical quality and practical decision quality need not coincide. We formalize this distinction through three success probabilities: exact surrogate recovery, surrogate near-optimality, and operational acceptability under stochastic evaluation. The framework is studied on a small binary inventory-control benchmark using a calibrated QUBO surrogate, exact enumeration, greedy search, simulated annealing, uniform feasible sampling, and ideal QAOA at depths p=1,2,3. The confirmatory results show that the near-optimal and operational acceptance sets are generally different. This changes finite-shot requirements substantially: for n=8,p=2, the median number of measurements needed for a 95% chance of observing a successful state falls from 392 under exact recovery to 84 under QUBO near-optimality and 31 under the operational criterion. Because operationally acceptable states can also be common, we compare QAOA with uniform feasible sampling; enrichment is supported only in selected regimes, and the classical baselines outperform QAOA on these small instances. A post-confirmatory IBM hardware study provides a complementary physical test. For n=4, operational success can remain close to its ideal value even when the measured decision distribution is distorted. For n=6,p=1, hardware gives S N =0.02475 and S O =0.01630, showing directly that near-optimal surrogate solutions need not be operationally acceptable. At n=6,p=2, Fez and Kingston yield different distances from the ideal decision distribution (0.4475 and 0.5326) but similar operational-success probabilities (0.0185 and 0.0171). The study does not indicate quantum advantage; it shows that exact recovery, surrogate quality, operational success, and distributional fidelity answer different evaluation questions and should be reported jointly.

DOI
10.21203/rs.3.rs-11499298/v2

Related papers

Feasibility and optimum recovery in warm-start quantum optimization for a drug-response model on a trapped-ion processor

Tanzir Hossain, Rajib Rana, Prabal Datta Barua +5 more

On a seven-compound drug-response model, warm-start quantum approximate optimization (QAOA) on IonQ Forte-1 returned valid assignments more often than random bitstrings, but this alone did not show effective optimization. Ideal QAOA raised optimum probability above uniform feasible sampling in only four of twelve reference circuits. Hardware often fell below its own noiseless circuits, while greedy search solved all hardware models within 200 objective evaluations. Expanded simulations showed a gain over feasible sampling in 28 of 35 CAMA-1 panels and none of four 647-V panels. Annealing solved all these panels in every seed. A Grover mixer preserved feasibility and improved optimum probability over feasible sampling in all ten tested models. We analyzed 25 completed tasks containing 5,300 shots from 18 circuits and 14 instances. The encodings use 6-35 qubits and at most 4,900 feasible assignments, which we enumerated to establish exact optima. Noiseless references now cover both the original six circuits and six wider circuits. At 35 qubits, with 4,900 feasible assignments, ideal feasibility was 35.85%, compared with 7 of 200 valid hardware outputs. Its ideal optimum probability was below both sampling controls. The circuits sample assignments in a model built from measured single-agent and pairwise responses.

quant-pharXiv:2609.22748•Sep 22, 2026•0 citations

Limits of QAOA Depth Scaling on IBM Quantum Hardware for Fault Tree QUBOs

Devin Peters

The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for near-term quantum advantage in combinatorial optimization. A central design parameter is circuit depth p, with theoretical analyses establishing asymptotic convergence under idealized conditions. This paper presents a limits study demonstrating that this theoretical relationship does not translate to measurable improvement on current noisy intermediate-scale quantum (NISQ) hardware for fault tree analysis applications. Across 120 QAOA executions on 60 QUBO-encoded fault tree instances (N ∈ {12, 16, 20, 24, 28, 32}) on IBM Quantum hardware (ibm_torino, 133-qubit Heron processor), circuit depths p = 1 and p = 2 were directly compared. The mean change in optimal state sampling probability from doubling circuit depth was Δmax_prob = 1.22 × 10⁻⁵ with a median Δ of zero. For 8,192 shots, the binomial sampling uncertainty is O(10⁻²); the observed mean delta is therefore approximately three orders of magnitude below the shot-noise scale, making the difference statistically indistinguishable from zero. Output distribution entropy approaches the theoretical maximum of log₂(8192) ≈ 13 bits, indicating hardware noise dominates algorithmic signal. These findings establish that for fault tree minimal cut set identification on current NISQ devices, computational resources are more effectively allocated to increased shot counts than to circuit depth. Complete experimental artifacts with SHA-256 verification are provided, enabling full reproducibility.

•Jan 18, 2026•0 citations

Evaluation of QAOA based on the approximation ratio of individual samples

Jason M. Larkin, Matías Jonsson, Daniel Justice +1 more

Abstract The quantum approximate optimization algorithm (QAOA) is a hybrid quantum–classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors it is a promising candidate likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. In particular for three-regular random graphs, QAOA performance shows improvement by up to two orders of magnitude compared to previous estimates, strongly reducing the performance gap with classical alternatives. This was possible by reducing the number of function evaluations per iteration and optimizing the variational parameters on small graph instances and transferring to large via training. Because QAOA’s performance guarantees are only known for limited applications and contexts, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.

arXiv:2006.04831•Quantum Science and Technology•Apr 22, 2022•45 citations

Beyond QAOA: A Review of AI and Quantum Computing for Adaptive Combinatorial Optimization

Hoong Chuin Lau

Near-term quantum approaches to combinatorial optimization are limited by qubit counts, circuit fidelity, sampling cost, and the difficulty of encoding constraints, while machine learning is increasingly used to configure and control quantum optimization workflows. We call such workflows adaptive: decisions conventionally fixed in advance, from formulation and penalties to shot budgets, backends, and whether to invoke a quantum processor at all, are made by learned policies that respond to the instance, the progress of the solve, or the hardware. This review examines three paradigms, AI for quantum optimization, quantum for AI-driven optimization, and AI-quantum co-optimization, and organizes the literature by the decision being learned rather than by application. A structured search identified a 119-paper corpus, of which 67 papers form an evidence core coded in detail. The evidence is considerably stronger for AI-assisted quantum optimization than for the reverse direction: learning already reduces quantum evaluations, improves initialization, supports decomposition and penalty control, and mitigates noise, whereas evidence that quantum computation improves learned optimizers remains largely confined to small-scale simulation. Experimental controls are thin: of 52 studies in the three paradigms, 22 include no classical baseline, the quantum contribution is fully isolated in 10 of 24 where an ablation applies, and the median largest experiment uses 16 qubits. We introduce an M0-M5 evidence hierarchy, from simulation to practical quantum advantage, and find no broadly convincing result at the highest level. We argue that scaling is increasingly a systems problem: the question is not only whether a problem fits on a quantum processor, but how classical and quantum resources should be allocated across the optimization process.

quant-pharXiv:2610.11759•Oct 9, 2026•1 citation

Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study

Jack S. Baker, Santosh Kumar Radha

Optimizing of a portfolio of financial assets is a critical industrial problem which can be approximately solved using algorithms suitable for quantum processing units (QPUs). We benchmark the success of this approach using the Quantum Approximate Optimization Algorithm (QAOA); an algorithm targeting gate-model QPUs. Our focus is on the quality of solutions achieved as determined by the Normalized and Complementary Wasserstein Distance, $η$, which we present in a manner to expose the QAOA as a transporter of probability. Using $η$ as an application specific benchmark of performance, we measure it on selection of QPUs as a function of QAOA circuit depth $p$. At $n = 2$ (2 qubits) we find peak solution quality at $p=5$ for most systems and for $n = 3$ this peak is at $p=4$ on a trapped ion QPU. Increasing solution quality with $p$ is also observed using variants of the more general Quantum Alternating Operator Ansätz at $p=2$ for $n = 2$ and $3$ which has not been previously reported. In identical measurements, $η$ is observed to be variable at a level exceeding the noise produced from the finite number of shots. This suggests that variability itself should be regarded as a QPU performance benchmark for given applications. While studying the ideal execution of QAOA, we find that $p=1$ solution quality degrades when the portfolio budget $B$ approaches $n/2$ and increases when $B \approx 1$ or $n-1$. This trend directly corresponds to the binomial coefficient $nCB$ and is connected with the recently reported phenomenon of reachability deficits. Derivative-requiring and derivative-free classical optimizers are benchmarked on the basis of the achieved $η$ beyond $p=1$ to find that derivative-free optimizers are generally more effective for the given computational resources, problem sizes and circuit depths.

arXiv:2202.06782•Feb 14, 2022•40 citations

A Comparative Study of QAOA and Classical Metaheuristics for Inventory Optimization

Poonam Chaudhary, Pranav Singh, Sneha Kandacharam +1 more

We investigate whether the Quantum Approximate Optimization Algorithm (QAOA) can compete with classical metaheuristics for multi-product, multi-location retail inventory optimization under demand uncertainty. We formulate the binary inventory decision problem as a Quadratic Unconstrained Binary Optimization (QUBO) model and benchmark QAOA (simulated via classical statevector simulation, $p=2$ layers) against Mixed-Integer Linear Programming (MILP), Simulated Annealing (SA), Genetic Algorithms (GA), and Tabu Search across problem sizes from $n=5$ to $n=200$ binary variables, using Walmart sales and Kaggle retail demand datasets. Our key finding is a \textbf{negative result}: while QAOA achieves a 2.3\% optimality gap and 97\% constraint satisfaction at small scales ($n \leq 20$), it is not competitive with classical metaheuristics at practical problem sizes. Classical heuristics---particularly SA and Tabu Search---consistently outperform QAOA on all instances tested and scale efficiently to $n=200$, whereas QAOA simulation becomes intractable beyond $n=30$ due to exponential memory requirements. We do not claim any quantum speedup. This comparative study provides important insights into the limitations of current QAOA implementations for supply chain problems, including the effects of penalty parameter scaling, barren plateaus in the optimization landscape, and circuit depth constraints. We additionally present an economic sensitivity analysis linking macroeconomic indicators to optimal inventory decisions and a rolling-horizon proof-of-concept for multi-period planning.

Natural Sciences and Applied Technology•Sep 30, 2026•0 citations
Abstract Approximate optimizers are usually judged by how well they recover a mathematical optimum or a near-optimal objective value. In many applications, however, the optimization model is only a surrogate for a downstream decision problem, so mathematical quality and practical decision quality need not coincide. We formalize this distinction through three success probabilities: exact surrogate recovery, surrogate near-optimality, and operational acceptability under stochastic evaluation. The framework is studied on a small binary inventory-control benchmark using a calibrated QUBO surrogate, exact enumeration, greedy search, simulated annealing, uniform feasible sampling, and ideal QAOA at depths p=1,2,3. The confirmatory results show that the near-optimal and operational acceptance sets are generally different. This changes finite-shot requirements substantially: for n=8,p=2, the median number of measurements needed for a 95% chance of observing a successful state falls from 392 under exact recovery to 84 under QUBO near-optimality and 31 under the operational criterion. Because operationally acceptable states can also be common, we compare QAOA with uniform feasible sampling; enrichment is supported only in selected regimes, and the classical baselines outperform QAOA on these small instances. A post-confirmatory IBM hardware study provides a complementary physical test. For n=4, operational success can remain close to its ideal value even when the measured decision distribution is distorted. For n=6,p=1, hardware gives S N =0.02475 and S O =0.01630, showing directly that near-optimal surrogate solutions need not be operationally acceptable. At n=6,p=2, Fez and Kingston yield different distances from the ideal decision distribution (0.4475 and 0.5326) but similar operational-success probabilities (0.0185 and 0.0171). The study does not indicate quantum advantage; it shows that exact recovery, surrogate quality, operational success, and distributional fidelity answer different evaluation questions and should be reported jointly.
On a seven-compound drug-response model, warm-start quantum approximate optimization (QAOA) on IonQ Forte-1 returned valid assignments more often than random bitstrings, but this alone did not show effective optimization. Ideal QAOA raised optimum probability above uniform feasible sampling in only four of twelve reference circuits. Hardware often fell below its own noiseless circuits, while greedy search solved all hardware models within 200 objective evaluations. Expanded simulations showed a gain over feasible sampling in 28 of 35 CAMA-1 panels and none of four 647-V panels. Annealing solved all these panels in every seed. A Grover mixer preserved feasibility and improved optimum probability over feasible sampling in all ten tested models. We analyzed 25 completed tasks containing 5,300 shots from 18 circuits and 14 instances. The encodings use 6-35 qubits and at most 4,900 feasible assignments, which we enumerated to establish exact optima. Noiseless references now cover both the original six circuits and six wider circuits. At 35 qubits, with 4,900 feasible assignments, ideal feasibility was 35.85%, compared with 7 of 200 valid hardware outputs. Its ideal optimum probability was below both sampling controls. The circuits sample assignments in a model built from measured single-agent and pairwise responses.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for near-term quantum advantage in combinatorial optimization. A central design parameter is circuit depth p, with theoretical analyses establishing asymptotic convergence under idealized conditions. This paper presents a limits study demonstrating that this theoretical relationship does not translate to measurable improvement on current noisy intermediate-scale quantum (NISQ) hardware for fault tree analysis applications. Across 120 QAOA executions on 60 QUBO-encoded fault tree instances (N ∈ {12, 16, 20, 24, 28, 32}) on IBM Quantum hardware (ibm_torino, 133-qubit Heron processor), circuit depths p = 1 and p = 2 were directly compared. The mean change in optimal state sampling probability from doubling circuit depth was Δmax_prob = 1.22 × 10⁻⁵ with a median Δ of zero. For 8,192 shots, the binomial sampling uncertainty is O(10⁻²); the observed mean delta is therefore approximately three orders of magnitude below the shot-noise scale, making the difference statistically indistinguishable from zero. Output distribution entropy approaches the theoretical maximum of log₂(8192) ≈ 13 bits, indicating hardware noise dominates algorithmic signal. These findings establish that for fault tree minimal cut set identification on current NISQ devices, computational resources are more effectively allocated to increased shot counts than to circuit depth. Complete experimental artifacts with SHA-256 verification are provided, enabling full reproducibility.
Abstract The quantum approximate optimization algorithm (QAOA) is a hybrid quantum–classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors it is a promising candidate likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. In particular for three-regular random graphs, QAOA performance shows improvement by up to two orders of magnitude compared to previous estimates, strongly reducing the performance gap with classical alternatives. This was possible by reducing the number of function evaluations per iteration and optimizing the variational parameters on small graph instances and transferring to large via training. Because QAOA’s performance guarantees are only known for limited applications and contexts, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.
Near-term quantum approaches to combinatorial optimization are limited by qubit counts, circuit fidelity, sampling cost, and the difficulty of encoding constraints, while machine learning is increasingly used to configure and control quantum optimization workflows. We call such workflows adaptive: decisions conventionally fixed in advance, from formulation and penalties to shot budgets, backends, and whether to invoke a quantum processor at all, are made by learned policies that respond to the instance, the progress of the solve, or the hardware. This review examines three paradigms, AI for quantum optimization, quantum for AI-driven optimization, and AI-quantum co-optimization, and organizes the literature by the decision being learned rather than by application. A structured search identified a 119-paper corpus, of which 67 papers form an evidence core coded in detail. The evidence is considerably stronger for AI-assisted quantum optimization than for the reverse direction: learning already reduces quantum evaluations, improves initialization, supports decomposition and penalty control, and mitigates noise, whereas evidence that quantum computation improves learned optimizers remains largely confined to small-scale simulation. Experimental controls are thin: of 52 studies in the three paradigms, 22 include no classical baseline, the quantum contribution is fully isolated in 10 of 24 where an ablation applies, and the median largest experiment uses 16 qubits. We introduce an M0-M5 evidence hierarchy, from simulation to practical quantum advantage, and find no broadly convincing result at the highest level. We argue that scaling is increasingly a systems problem: the question is not only whether a problem fits on a quantum processor, but how classical and quantum resources should be allocated across the optimization process.
Optimizing of a portfolio of financial assets is a critical industrial problem which can be approximately solved using algorithms suitable for quantum processing units (QPUs). We benchmark the success of this approach using the Quantum Approximate Optimization Algorithm (QAOA); an algorithm targeting gate-model QPUs. Our focus is on the quality of solutions achieved as determined by the Normalized and Complementary Wasserstein Distance, ηηη, which we present in a manner to expose the QAOA as a transporter of probability. Using ηηη as an application specific benchmark of performance, we measure it on selection of QPUs as a function of QAOA circuit depth ppp. At n=2n = 2n=2 (2 qubits) we find peak solution quality at p=5p=5p=5 for most systems and for n=3n = 3n=3 this peak is at p=4p=4p=4 on a trapped ion QPU. Increasing solution quality with ppp is also observed using variants of the more general Quantum Alternating Operator Ansätz at p=2p=2p=2 for n=2n = 2n=2 and 333 which has not been previously reported. In identical measurements, ηηη is observed to be variable at a level exceeding the noise produced from the finite number of shots. This suggests that variability itself should be regarded as a QPU performance benchmark for given applications. While studying the ideal execution of QAOA, we find that p=1p=1p=1 solution quality degrades when the portfolio budget BBB approaches n/2n/2n/2 and increases when B≈1B \approx 1B≈1 or n−1n-1n−1. This trend directly corresponds to the binomial coefficient nCBnCBnCB and is connected with the recently reported phenomenon of reachability deficits. Derivative-requiring and derivative-free classical optimizers are benchmarked on the basis of the achieved ηηη beyond p=1p=1p=1 to find that derivative-free optimizers are generally more effective for the given computational resources, problem sizes and circuit depths.
We investigate whether the Quantum Approximate Optimization Algorithm (QAOA) can compete with classical metaheuristics for multi-product, multi-location retail inventory optimization under demand uncertainty. We formulate the binary inventory decision problem as a Quadratic Unconstrained Binary Optimization (QUBO) model and benchmark QAOA (simulated via classical statevector simulation, p=2p=2p=2 layers) against Mixed-Integer Linear Programming (MILP), Simulated Annealing (SA), Genetic Algorithms (GA), and Tabu Search across problem sizes from n=5n=5n=5 to n=200n=200n=200 binary variables, using Walmart sales and Kaggle retail demand datasets. Our key finding is a \textbf{negative result}: while QAOA achieves a 2.3\% optimality gap and 97\% constraint satisfaction at small scales (n≤20n \leq 20n≤20), it is not competitive with classical metaheuristics at practical problem sizes. Classical heuristics---particularly SA and Tabu Search---consistently outperform QAOA on all instances tested and scale efficiently to n=200n=200n=200, whereas QAOA simulation becomes intractable beyond n=30n=30n=30 due to exponential memory requirements. We do not claim any quantum speedup. This comparative study provides important insights into the limitations of current QAOA implementations for supply chain problems, including the effects of penalty parameter scaling, barren plateaus in the optimization landscape, and circuit depth constraints. We additionally present an economic sensitivity analysis linking macroeconomic indicators to optimal inventory decisions and a rolling-horizon proof-of-concept for multi-period planning.