arXiv:2610.03645
Exponential quantum space advantage in random data streams
Adam Bouland, Matthew Ding, Siddhartha Jain
Abstract
We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa-Zhandry Code Intersection problem admits exponential quantum advantage in the streaming model when its inputs are streamed in random order. This means quantum computers exhibit exponential space advantage even when simply receiving $(x,f(x))$ pairs for a uniformly random function $f$ in a uniformly random order. Notably, our classical space lower bound does not follow from a communication lower bound. Instead, we utilize density-restoring partitions from communication complexity directly with potential-function analysis in the style used to prove memory-sample tradeoffs for learning. The resulting argument is distinct from both lines of work. Second, we use our framework to show quantum space advantage for the Optimal Polynomial Intersection (OPI) problem in certain regimes via a streaming version of the Decoded Quantum Interferometry algorithm. In particular, we show that for degree $d$ and $n$ evaluation points, attaining $1/2 + Ω(\sqrt{d/n})$ fraction of satisfied OPI constraints via streaming requires $Ω(n)$ classical bits of memory but only $O(d\log n)$ qubits. This yields provable quantum advantage in a "low-rate" regime when the number of evaluation points is much larger than the degree, with a space advantage that can be as large as exponential in certain parameter settings.
AI Summary
Can quantum algorithms achieve exponential space savings when classical input data arrive in uniformly random order? This paper establishes unconditional separations for two single-pass streaming search problems, with random inputs as well as random ordering. For Yamakawa–Zhandry Code Intersection, the stream enumerates a uniformly random Boolean oracle on coordinate–symbol pairs; the goal is to find a codeword whose coordinates all map to one. For a folded Reed–Solomon code family, a quantum algorithm uses $\operatorname{poly}(n)$ qubits and succeeds with probability $1-o(1)$, whereas classical algorithms using at most $2^{c_1n^{c_2}}$ bits have success probability $2^{-\Omega(n)}$, for constants $c_1,c_2>0$. For Optimal Polynomial Intersection, with $n=q-1$ evaluation points and polynomials of degree below $d$, streaming DQI achieves at least $\lceil n/2+\sqrt{dn}/8\rceil$ satisfied random constraints using $O(d\log n)$ qubits. When $d=\omega(\log n)$ and $d=o(n/\log n)$, achieving this target classically requires $\Omega(n)$ bits; below a constant-times-$n$ memory bound, success is at most $2^{-\Omega(d)}$. Taking $d=\Theta(\log^2 n)$ gives $O(\log^3 n)$ quantum space versus $\Omega(n)$ classical space. The classical proofs use threshold-crossing potentials for read-once branching programs, combined with density-restoring partitions and list recoverability for Code Intersection, and pairwise polynomial agreement bounds for OPI. Quantum algorithms accumulate commuting input-dependent gates during the pass and postprocess afterward. These are space, not runtime, separations: streams enumerate entire oracle tables, and the space-bounded DQI implementation permits exponential-time decoding. The OPI lower bound applies only to streaming, not unrestricted optimization.
ChatGPT 6 Astra provided the first proof sketch of the classical streaming lower bound, which the authors then formalized, simplified, and verified.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 27+3 pages. v2: fixed minor typos and added concurrent work statement