arXiv preprint ·
Exponential quantum space advantage in random data streams
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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. Our lower bound is shown using density-restoring partitions as in the work of Göös, Gur, Jain, and Li (STOC 2025) combined with a convex potential, similar to the work of Raz (J.ACM 2018) on parity learning and its generalization by Garg, Raz, and Tal (STOC 2018). 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 (Nature 2025; arXiv:2510.10967). 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Hamiltonian locality testing and certification do not achieve the Heisenberg limit
A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numbers
No Size-Preserving Amplification with Quantum Advice
Nonuniform QCPH Collapse Implies QCPH Collapse
The Plan Language of a Curriculum: A Formal Model and the Complexity of Degree Planning
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.