Metraipolis › archive › dc_f28cf3e8fc12
Exponential quantum advantages for decoded quantum interferometry in the streaming setting — arXiv:2610.01902
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.01902
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T11:38:11.228Z
- SHA-256 of the archived text
0d35c1475fe5f295618a439cf7c45132ac8fe1afb8d6e7126d98f7ca1db91028- Stable URL of this page
https://metraipolis.com/documento/dc_f28cf3e8fc12
How to cite
Exponential quantum advantages for decoded quantum interferometry in the streaming setting — arXiv:2610.01902 — arXiv (en), https://arxiv.org/abs/2610.01902 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f28cf3e8fc12 (Metraipolis archive dc_f28cf3e8fc12, sha256 0d35c1475fe5f295618a439cf7c45132ac8fe1afb8d6e7126d98f7ca1db91028)
BibTeX
@misc{dcf28cf3e8fc12,
title = {Exponential quantum advantages for decoded quantum interferometry in the streaming setting — arXiv:2610.01902},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.01902},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f28cf3e8fc12; sha256 0d35c1475fe5f295618a439cf7c45132ac8fe1afb8d6e7126d98f7ca1db91028},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.01902. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Besides time, space is another central resource: storing and manipulating a massive input can be very challenging, especially when logical qubits carry substantial fault-tolerant implementation overhead. This motivates the following question: does DQI yield quantum advantages in memory, and can we prove it unconditionally? We give an affirmative answer to this question in the streaming setting. In particular, we consider a natural generalization of OPI using Hermite interpolation and Hasse derivatives, which asks for a low-degree polynomial satisfying as many constraints on its values and derivatives as possible. As a concrete example, we show [Quantum efficiency.] An adaptation of the DQI algorithm produces a polynomial satisfying $93\%$ of the constraints; moreover, it only reads the input stream in one pass, uses polylogarithmic space, and has polylogarithmic computation time per stream entry. [Classical hardness.] Any classical algorithm that produces an answer satisfying just $76\%$ of the constraints requires polynomial space, even if it can read the input stream with polynomially many passes and can use unlimited time. Our result provides a complete tradeoff curve for the tunable parameters, and implies that DQI has provable quantum advantages for the original OPI problem. 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.01902 — 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.722Z 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).