{"id":"arxiv/2610.02145","url":"https://arxiv.org/abs/2610.02145","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"A provable quantum advantage for approximate optimization via decoded quantum interferometry","domain":"quant-ph","source":"arxiv","authors":["Maximilian J. Kramer","Elies Gil-Fuster","Benjamin D. M. Jones","Jens Eisert","Franz J. Schreiber"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}