A provable quantum advantage for approximate optimization via decoded quantum interferometry
Abstract
Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate $0.3$, DQI achieves expected scores of approximately $0.85$. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.
Related
- Provable Classical and Quantum Local Algorithms for Max-k-Cut and Quantum Advantage at Moderate Girth
- The Quantum Sphere: A Physically Realizable Optimization Benchmark with Provable Linear Convergence in White- and Black-Box Settings
- Quantum-Fisher-information-aware optimization yields a quantum reservoir advantage over tuned classical reservoirs
- Binary Optimization with Complex Constraints via Quantum Approximate Multi-Objective Optimization
- Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer
BibTeX
@misc{kramer2026provable,
title = {{A provable quantum advantage for approximate optimization via decoded quantum interferometry}},
author = {Maximilian J. Kramer and Elies Gil-Fuster and Benjamin D. M. Jones and Jens Eisert and Franz J. Schreiber},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02145},
eprint = {2610.02145},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02145},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A provable quantum advantage for approximate optimization via decoded quantum interferometry
AU - Maximilian J. Kramer
AU - Elies Gil-Fuster
AU - Benjamin D. M. Jones
AU - Jens Eisert
AU - Franz J. Schreiber
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02145
UR - https://arxiv.org/abs/2610.02145
AB - Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate $0.3$, DQI achieves expected scores of approximately $0.85$. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.
ER -