Exponential quantum space advantage in random data streams
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 + Ω(√(d/n)) fraction of satisfied OPI constraints via streaming requires Ω(n) classical bits of memory but only O(dlog 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.
Related
- Exponential advantage in continuous-variable quantum state learning
- An Exponential Sample-Complexity Advantage for Coherent Quantum Inference
- Exponential Quantum Advantage in Numbers-on-Forehead Communication
- Exponential Quantum Advantage in Testing Fourier Dimensionality
- Exponential Quantum Advantage in Stationary Signal Sensing
BibTeX
@misc{bouland2026exponential,
title = {{Exponential quantum space advantage in random data streams}},
author = {Adam Bouland and Matthew Ding and Siddhartha Jain},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03645},
eprint = {2610.03645},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03645},
}
RIS
TY - UNPB
TI - Exponential quantum space advantage in random data streams
AU - Adam Bouland
AU - Matthew Ding
AU - Siddhartha Jain
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03645
UR - https://arxiv.org/abs/2610.03645
AB - 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 + Ω(√(d/n)) fraction of satisfied OPI constraints via streaming requires Ω(n) classical bits of memory but only O(dlog 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.
ER -