A provable quantum advantage for approximate optimization via decoded quantum interferometry
AuthorsMaximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones, Jens Eisert, Franz J. Schreiber
AffiliationsDahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany · Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany · Helmholtz-Zentrum Berlin für Materialien und Energie, 14109 Berlin, Germany
This paper proves that, for a specially constructed optimization problem, quantum interferometry can achieve approximation scores that classical algorithms cannot match efficiently.
Key results
Illustrative rate used to compare the classical and quantum score guarantees.
Prange’s benchmark at rate 0.3; a fixed improvement requires super-polynomially many classical queries.
Expected score at rate 0.3, guaranteed uniformly over promised instances.
Score at rate 0.3 on typical sampled instances, using complete list decoding and coherent syndrome-fiber summation.
For rates above this boundary, the stronger algorithm achieves exact search on typical sampled instances.
What the paper found
This paper proves a quantum advantage for approximate optimization in a membership-oracle setting, using folded optimal polynomial intersection: find a low-degree polynomial whose grouped evaluations land in as many acceptance sets as possible. Each set accepts exactly half of its block alphabet, and the instances use folded Reed–Solomon codes. Decoded quantum interferometry, or DQI, uses coherent Fourier interference and unique decoding of the dual code to beat the classical score threshold on every promised instance, with one coherent query per block. Prange’s classical strategy reaches the threshold, while any classical algorithm that improves on it by a fixed amount with constant probability needs super-polynomially many queries on sampled instances—even with unlimited computation. At rate 0.3, the classical threshold is 0.65, DQI’s expected score is 0.8571, and a stronger quantum method reaches 0.9583 on typical sampled instances. That method combines complete list decoding with coherent summation of labels sharing a syndrome; for rates above 0.5, it can find a polynomial accepted in every block on typical instances. The result is an oracle-based separation, not a proof of advantage for ordinary, non-oracle optimization problems. The paper also discloses that OpenAI’s GPT-5.6 Sol and GPT-6 Astra, and Anthropic’s Claude Opus 5.5, assisted with proof development and checking; the researchers say they verified the final claims.
Original 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 larger gap on the folded OPI problem, yielding an even stronger quantum separation. As a concrete example, for code rate $0.3$, DQI and the modified algorithm achieve expected scores of approximately $0.85$ and $0.95$, respectively. 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.
Read the original paperMore in Optimization
Browse all 39 papers →AF-Muon: An AdamW-Free Muon Optimizer for Tied-Embedding Models
Arash Lagzian, Paniz Halvachi, Junming Zhang, Zhouhan Lin, Dianbo Liu
AF-Muon adapts Muon to tied embeddings, reducing optimizer memory while improving training across language, image, and protein models.
Planning to Learn
Ian Osband
This paper makes classification more forward-looking by designing a loss that values not just immediate accuracy gains, but how much future learning an update enables.
An $Ω(κ_y^8ε^{-6})$ Lower Bound for Stochastic NC-SC Bilevel Optimization with First-order Oracles
Zhihao Gu, Qilong Wu, Junchi Yang
This work proves that stochastic bilevel optimization fundamentally requires up to epsilon^{-6} oracle queries, showing existing methods are asymptotically optimal.