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

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

Problem Statement
Approximate optimization algorithms, particularly the Quantum Approximate Optimization Algorithm (QAOA), are traditionally evaluated based on their ability to recover the exact mathematical optimum of a formulated problem or to achieve a specific approximation ratio within the objective space. However, in practical decision pipelines, the optimization model often serves as a surrogate for a downstream stochastic decision problem. A solution that is mathematically near-optimal for the surrogate model (e.g., a Quadratic Unconstrained Binary Optimization or QUBO) is not necessarily operationally acceptable when evaluated against the consequences of the decision in a stochastic environment.

Current benchmarking often fails to distinguish between three distinct levels of success:

1. Exact Recovery: Finding the precise mathematical optimum of the surrogate.
2. Surrogate Near-Optimality: Finding a solution within a small tolerance of the surrogate optimum.
3. Operational Acceptability: Finding a solution that satisfies performance criteria (e.g., cost and risk tolerances) when evaluated in the original stochastic environment.

The paper investigates whether these definitions of success coincide and how the choice of definition impacts the estimated sampling cost (number of measurements) required to observe a "successful" solution.

Methodology
The author proposes an end-to-end evaluation framework applied to a controlled stochastic inventory-control benchmark. The experimental design is rigorous and "frozen" to prevent data leakage:

• Benchmark Construction: A stochastic binary inventory replenishment problem is defined. The operational loss function includes holding costs, penalty costs for stockouts, and ordering costs. Demand is modeled as a stochastic variable.
• Surrogate Modeling: The stochastic problem is approximated by a calibrated QUBO surrogate. Parameters for the QUBO were selected using a calibration set and then "frozen" before evaluation on held-out and independent confirmatory datasets.
• Success Definitions:
  • $S_E$: Probability of recovering the exact QUBO optimum.
  • $S_N$: Probability of finding a solution within a normalized QUBO energy gap $\epsilon_Q$.
  • $S_O$: Probability of finding a solution satisfying downstream operational criteria, defined by expected cost regret ($R_J \le \epsilon_J$) and Conditional Value-at-Risk (CVaR) deviation ($R_C \le \delta_C$).
• Baselines and Solvers: The study compares ideal statevector QAOA (at depths $p=1, 2, 3$) against:
  • Exact enumeration (ground truth).
  • Greedy heuristic.
  • Simulated annealing.
  • Uniform feasible sampling (to establish a baseline prevalence of acceptable solutions).
• Metrics:
  • Set Disagreement: Analysis of the intersection and difference between the near-optimal set ($Q_{\epsilon}$) and the operational acceptance set ($O_{\epsilon, \delta}$).
  • Sampling Cost ($N_{95}$): The number of shots required to observe at least one successful solution with 95% probability, calculated as $N_{95}(S) = \lceil \log(0.05) / \log(1-S) \rceil$.
  • Operational Enrichment ($E_O$): The ratio of the solver's probability mass on the operational set to the prevalence of that set under uniform sampling ($E_O = P_{solver}(O) / P_{uniform}(O)$). This controls for the possibility that acceptable solutions are simply abundant.
• Validation: The custom statevector implementation was independently verified against Qiskit and Qiskit Aer to floating-point precision.

Key Results
The experiments, conducted on instances with $n \in \{4, 6, 8\}$ binary variables, yield the following findings:

1. Distinct Solution Sets: The set of mathematically near-optimal QUBO solutions and the set of operationally acceptable solutions are empirically distinct and non-nested.

   • Solutions exist that are mathematically near-optimal but operationally unacceptable ($Q \setminus O$).
   • Solutions exist that are operationally acceptable but mathematically far from the QUBO optimum ($O \setminus Q$).
   • Consequently, $S_N$ and $S_O$ are not interchangeable, and relaxing the success criterion from exact recovery to operational acceptability changes the probability mass assigned to "success."

2. Sampling Cost Reduction: Redefining success from exact recovery to operational acceptability drastically reduces the estimated sampling cost.

   • For $n=8, p=2$, the median number of shots required for 95% observation probability drops from 392 (exact recovery) to 84 (QUBO near-optimality) and further to 31 (operational acceptability).
   • The author emphasizes this is a consequence of the success definition, not a quantum speedup, as the underlying output distribution remains unchanged.

3. No Quantum Advantage: Classical baselines significantly outperform the tested QAOA configurations.

   • Greedy search and simulated annealing achieve much higher success probabilities ($S_E, S_N, S_O$) than QAOA on these small instances.
   • At $p=1$, QAOA is often under-enriched relative to uniform feasible sampling ($E_O < 1$), meaning it concentrates less probability on acceptable solutions than random sampling would.
   • At $p=2$ and $p=3$, some regimes show $E_O > 1$, but classical methods still dominate in absolute performance.

4. Depth Sensitivity: Increasing QAOA depth ($p$) does not guarantee monotonic improvement under a fixed parameter-search budget. For $n=8$, operational success ($S_O$) peaked at $p=2$ and slightly decreased at $p=3$, attributed to the sparsity of the parameter search space as dimensionality grows ($2p$ parameters).

Significance and Claims
The paper modestly claims a methodological contribution rather than a demonstration of quantum advantage. Its primary significance lies in the evaluation framework:

• Decoupling Success Levels: It demonstrates that "solver success" is not a monolithic concept. In decision-focused pipelines, mathematical near-optimality does not guarantee downstream operational quality.
• Operational Enrichment: It introduces the necessity of comparing solver performance against uniform feasible sampling to distinguish between an algorithm concentrating probability on useful states versus the mere abundance of acceptable states in the search space.
• Reframing Benchmarking: The results suggest that evaluating approximate quantum optimizers solely on surrogate-objective recovery may be misleading for applications where the model is a proxy for a stochastic environment. A more complete evaluation should report exact recovery, mathematical approximation, downstream acceptability, and baseline prevalence.

The author explicitly states that the study does not claim quantum advantage; rather, it shows that the apparent performance of a solver changes materially when success is defined by downstream decision consequences rather than surrogate-objective recovery alone. The work serves as a cautionary framework for benchmarking quantum algorithms in application-oriented contexts where the optimization model is an intermediate step.