Metraipolis › archive › dc_33c7f2cd7eb7

A provable quantum advantage for approximate optimization via decoded quantum interferometry — arXiv:2610.02145

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.02145
License (as archived)
CC0-1.0
Archived
2026-10-07T11:38:35.766Z
SHA-256 of the archived text
432b35b66bd0ea222eb33f83ee46ffaf45a8779d901260edb65cbc69c3adbba9
Stable URL of this page
https://metraipolis.com/documento/dc_33c7f2cd7eb7

How to cite

A provable quantum advantage for approximate optimization via decoded quantum interferometry — arXiv:2610.02145 — arXiv (en), https://arxiv.org/abs/2610.02145 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_33c7f2cd7eb7 (Metraipolis archive dc_33c7f2cd7eb7, sha256 432b35b66bd0ea222eb33f83ee46ffaf45a8779d901260edb65cbc69c3adbba9)
BibTeX
@misc{dc33c7f2cd7eb7,
  title = {A provable quantum advantage for approximate optimization via decoded quantum interferometry — arXiv:2610.02145},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.02145},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_33c7f2cd7eb7; sha256 432b35b66bd0ea222eb33f83ee46ffaf45a8779d901260edb65cbc69c3adbba9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.02145. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-10-02 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.02145 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:19:01.760Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).