Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

Abstract

When does a noisy quantum sampler yield an end-to-end polynomial-time optimization algorithm with performance guarantees? Building on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA, we show that inverse-polynomial ideal probability on the optimal set, together with independent sampling, polynomial-time feasibility repair, and scoring, produces an exact-hit fully polynomial randomized approximation scheme, which we call an FPRASq. This guarantee survives device noise within an instance-dependent window. For effective circuit depth linear in the product of layer count and problem size, preserving an inverse-depth fraction of the ideal optimal mass increases the required shot complexity by one power of the problem size. Beyond this window, deterministic repair guarantees feasibility and provides an instance-dependent approximation guarantee whenever the induced objective inflation is controlled. The resulting NP-HQ algorithm fits the Chen-Cotler-Huang-Li oracle model. On any NP-hard kernel-admissible promise family, reproducing its inverse-polynomial optimal overlap with a polynomial-time classical sampler would imply that NP is contained in BPP, even with identical repair and perfect access to the constraint structure. Thus, the separation lies in generating the sampling distribution. We further introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical post-processing cost by one power of the problem size. Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables and match or improve every tested QOptlib reference tour.

The paper asks when a noisy quantum optimization sampler can support an end-to-end polynomial-time algorithm with guarantees. It extends Constraint-Enhanced QAOA (CE-QAOA) with deterministic feasibility checking, repair, and objective scoring, returning the best repaired sample. For assignment encodings, repair is nearest-permutation projection in Hamming distance, implemented by Hungarian matching in $O(n^3)$ time per sample. The principal guarantee assumes ideal probability $p_0\ge c n^{-k}$ on the optimal feasible set. With effective circuit depth $G=O(pn)$ and effective per-layer diamond-norm error $\epsilon$, a telescoping bound gives $\|P_\epsilon-P_0\|_{\mathrm{TV}}\le G\epsilon/2$. If $\epsilon\le(2p_0/G)(1-1/G)$, optimal mass remains at least $p_0/G$, so $O(pn^{k+1}\log(1/\delta))$ independent shots recover an optimum with confidence $1-\delta$. This is termed an exact-hit FPRAS$_q$. A conditional complexity argument shows that classical inverse-polynomial optimal overlap on an NP-hard promise family would imply $\mathrm{NP}\subseteq\mathrm{BPP}$. Heavy-hitter filtering bounds the retained candidate set by $O(n^k)$ when an individual optimal string retains probability $\Omega(n^{-k})$, giving $O(n^{k+3})$ checking/repair/scoring cost. IBM Eagle-r3 demonstrations use 16–100 logical qubits for 4–10-city TSP instances; repaired outputs match or improve the tested QOptlib reference tours. The guarantees remain conditional on instance-dependent optimal mass, suitable sampling parameters, and a shrinking low-noise window; reference-model bounds require additional envelope, phase-gap, and coherent-comparison conditions. Outside that window, repair guarantees feasibility, but approximation quality requires separate objective-inflation promises. More aggressive empirical candidate compression can discard the best sampled solution.