Decoded quantum interferometry beats classical memory in streaming tasks
Exponential quantum advantages for decoded quantum interferometry in the streaming setting
Computational ComplexityData Structures and Algorithms
Summary
Some computer problems are very hard for classical computers because they require a lot of memory and time. The authors study a quantum algorithm called decoded quantum interferometry (DQI) that can solve a tricky math problem faster and with less memory when the data comes in a stream you can only read once. They show that classical algorithms must use much more memory and still can't get as good results as DQI. This proves that quantum methods can have real advantages in memory-limited situations.
What this means in practice
- •For quantum algorithm developers: Design memory-efficient quantum algorithms for streaming data problems outperforming classical methods.
- •For data streaming engineers: Explore new quantum-accelerated approaches to handle large data streams with limited memory resources.
Authors
Kewen Wu, Guangxu Yang
Abstract
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.