Quantum 2025 – wissenschaftliches Programm
Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
TUE: Tuesday Contributed Sessions
TUE 6: Quantum Computing and Communication: Contributed Session I (Algorithms & Theory)
TUE 6.7: Vortrag
Dienstag, 9. September 2025, 15:45–16:00, ZHG007
Beyond Classical Approximation Guarantees in the NISQ Era — •Chinonso Onah1,2 and Kristel Michielsen2,3 — 1Volkswagen Group, Germany — 2Department of Physics, RWTH Aachen, Germany — 3Forschungszentrum Jülich, Germany
We present the first constant-low-depth, ancilla-free constrained QAOA variant that (1) provably concentrates inverse-polynomial probability on the target bit-strings, (2) exponentially outperforms generic QAOA at any depth by massively boosting the probability of legal solutions, (3) amplifies any generic QAOA parameter set by a super-exponential factor, and (4) serves as the quantum core of an Exact Hybrid Quantum*Classical solver that is a fully-polynomial randomized approximation scheme whose success probability*and additive-gap performance under Hungarian repair*cannot be matched by any polynomial-time classical sampler unless NP is contained in BPP. On the QOPTLib TSP benchmark (all instances up to one hundred qubits that fit on today*s superconducting hardware), our solver recovers or improves upon every previously published tour*achieving up to a 12.3 percent shorter route on the hardest instance. This dramatic gain on the most challenging benchmarks underlines the practical promise of our approach on near-term devices.
Keywords: Constant-depth constrained QAOA; Hybrid quantum–classical solver; Fully polynomial randomized approximation scheme; Quantum advantage; Quantum optimization