aiqbench analysis
This research establishes rigorous performance guarantees for noisy quantum optimization algorithms, demonstrating that a specific sampling strategy combined with classical repair can yield exact solutions in polynomial time even under device noise. The study proves that the fundamental separation between efficient classical and quantum approaches lies specifically in generating the required probability distributions rather than solving constraints directly. Furthermore, experimental results on IBM hardware validate these theoretical bounds for instances involving up to one hundred logical variables, bridging complex complexity theory with practical near-term applications.
Geometry-Informed Polynomial Time Quantum Approximation Schemes for Constrained Optimisation
arXiv:2608.01121v1 Announce Type: new 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.
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.
Quantum Physics (quant-ph); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Mathematical Physics (math-ph); Applied Physics (physics.app-ph)
arXiv:2608.01121 [quant-ph]
(or arXiv:2608.01121v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2608.01121 arXiv-issued DOI via DataCite (pending registration)
Full text under the publisher's open licence · 255 words
Related coverage
Lattice-Based Cryptography Explained
Quantum Zeitgeist · Aug 15, 2026
Fixed points in de Finetti hierarchies
arXiv · Jul 28, 2026
Approximating fixed size quantum correlations in polynomial time
arXiv · Aug 6, 2026
A Solution to Cryptographic Boxes for Unfriendly AI
LessWrong · Jul 19, 2026