Exponential quantum advantages for decoded quantum interferometry in the streaming setting

@misc{wu2026exponential,
  title = {{Exponential quantum advantages for decoded quantum interferometry in the streaming setting}},
  author = {Kewen Wu and Guangxu Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.01902},
  eprint = {2610.01902},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.01902},
}

TY  - UNPB
TI  - Exponential quantum advantages for decoded quantum interferometry in the streaming setting
AU  - Kewen Wu
AU  - Guangxu Yang
PY  - 2026
DA  - 2026/10/03
PB  - arXiv
DO  - 10.48550/arxiv.2610.01902
UR  - https://arxiv.org/abs/2610.01902
AB  - 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.
ER  -