{"id":"arxiv/2608.01121","url":"https://arxiv.org/abs/2608.01121","tags":["quant-ph","cs.CC","cs.DM","math-ph","physics.app-ph"],"score":0,"title":"Polynomial Time Quantum Approximation Schemes for Constrained Optimisation","domain":"quant-ph","source":"arxiv","authors":["Chinonso Onah","Kristel Michielsen"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-02","reactions":{}}