arXiv:2610.02145
A provable quantum advantage for approximate optimization via decoded quantum interferometry
Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones, Jens Eisert, Franz J. Schreiber
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.
AI Summary
Can decoded quantum interferometry (DQI) provably outperform arbitrary classical algorithms for approximate optimization? This paper establishes an oracle separation for balanced folded optimal polynomial intersection: find a low-degree polynomial maximizing the fraction of folded evaluation blocks accepted by membership oracles. Each acceptance set contains half the block alphabet; classical lower bounds use independently sampled uniform half-size sets. For every fixed rational code rate $R\in(0,1)$, DQI runs in quantum polynomial time using $M$ coherent membership queries and achieves expected score $\alpha_Q=(1+\sqrt{R(2-R)})/2+o(1)$ on every promised instance. Prange’s interpolation strategy attains $\alpha_C=(1+R)/2$ on sampled instances. Any classical algorithm exceeding $\alpha_C$ by a fixed amount with constant probability requires $\exp(\Omega(M/\log M))$ queries, even with unlimited intervening computation. At $R=0.3$, these scores are approximately $0.8571$ and $0.65$. Verification and repetition convert the quantum expectation into bounded-error threshold guarantees. The proof extends the DQI semicircle score law to folded predicates, uses conventional Reed–Solomon unique decoding, and combines folded-code list recoverability with conditional binomial tails for classical hardness. Complete list decoding and coherent syndrome-fiber summation further achieve every fixed score below $1/2+\sqrt{R(1-R)}$ for $R\leq1/2$, and exact satisfaction for $R>1/2$, on typical sampled instances. Typical perfect satisfiability transfers score separations to approximation ratios. The separation relies on oracle access and an exponentially large block alphabet. Stronger quantum guarantees are distributional, not worst-case; non-oracular hardness and scalar-OPI advantage remain open.
Through an iterative exchange, the model proposed candidate proof strategies and generated preliminary theorem statements and proof drafts. The central proof strategy ultimately used in this manuscript emerged through that exchange.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 59 pages, 3 figures