arXiv:2610.01902
Exponential quantum advantages for decoded quantum interferometry in the streaming setting
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.
AI Summary
Decoded quantum interferometry (DQI) gives approximation guarantees for optimal polynomial intersection (OPI) beyond known efficient classical algorithms, but unconditional time separations remain open. This paper asks whether DQI instead yields provable memory advantages in streaming, including against classical algorithms allowed many passes and unlimited computation. It studies OPI and a Hermite generalization that asks for a bounded-degree polynomial satisfying allowed sets of values and Hasse derivatives. The input explicitly lists membership bits for each allowed-set address, giving stream length $N=(q-1)q^\ell$, where $\ell$ is the jet length. A one-pass quantum algorithm achieves every fixed approximation ratio below $(2+\sqrt3)/4\approx0.93301$, using $O(q\ell\log q)$ space and $\operatorname{poly}(q,\ell)$ preprocessing, per-entry processing, and postprocessing time. Every classical $p$-pass algorithm achieving $\alpha>3/4$ requires space at least $q^{1+\ell\kappa(\alpha)}/[p(\ell\log q)^{C_\alpha\ell}]$, with $\kappa(\alpha)=(4\alpha-3)/(4\alpha-2)$. Choosing growing $\ell$ gives polylogarithmic quantum memory versus polynomial classical memory, even with polynomially many passes. Original OPI has a polynomial memory separation. The quantum construction prepares a DQI error state directly from the stream, then uses coherent syndrome decoding and Fourier sampling. Classical lower bounds combine multiparty communication, density-restoring refinements, and Hermite-code list recovery. Classical algorithms match the $3/4$ threshold and nearly match the one-pass approximation–space frontier for fixed $\ell$. Approximation arbitrarily close to one is also possible quantumly, but uses $q^{O(q\ell)}$ postprocessing. Efficient near-optimal decoding, exact optimization, and tight classical multipass tradeoffs remain open. The exponential separation concerns memory on explicitly expanded inputs, not unconditional runtime advantage.
GPT-6 was also used to draft the paper, which was fully rewritten by the authors.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.