Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.03645

Exponential quantum space advantage in random data streams

Adam Bouland, Matthew Ding, Siddhartha Jain

quant-phcs.CCSubmitted Oct 2, 2026• Announced Oct 5, 2026• 3 citations• Revised Nov 2, 2026 (v2)
v1 · Oct 2, 2026v2 · Nov 2, 2026
arXivHTMLPDF

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.

No sign of AI-generated textAI use disclosed
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

Related papers

Exponential quantum advantages for decoded quantum interferometry in the streaming setting

Kewen Wu, Guangxu Yang

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.

quant-pharXiv:2610.01902•Oct 2, 2026•3 citations

Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds

Nadezhda Voronova

How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment. We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests. To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting $r$ independent matching requests requires $Ω(r)$ qubits for $r\le N^{1/2-δ}$ and every fixed $δ\in(0,1/2)$, even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through $r=Θ(\sqrt N)$. We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes. Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an $Ω(n)$ space lower bound in random edge order for large enough cycles, with consequences for several graph problems. Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.

quant-pharXiv:2610.06727•Oct 6, 2026•1 citation

A provable quantum advantage for approximate optimization via decoded quantum interferometry

Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones +2 more

Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate $0.3$, DQI achieves expected scores of approximately $0.85$. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.

quant-pharXiv:2610.02145•Oct 2, 2026•5 citations

Exponential quantum space advantage for Shannon entropy estimation in data streams

Weijun Feng, Yongzhen Xu, Lvzhou Li +2 more

Near-term quantum devices with limited qubits motivate the study of space-bounded quantum computation in the data stream model. We show that Shannon entropy estimation exhibits an exponential separation between quantum and classical space complexity in this setting. Technically, we develop a two-stage quantum streaming algorithm based on a quantum procedure with an explicitly constructed oracle derived from the streaming input. This algorithm achieves logarithmic space complexity in the accuracy parameter over the data stream, whereas any classical streaming algorithm under the same pass complexity requires polynomial space. In sharp contrast, existing results for Shannon entropy estimation in the quantum query model achieve only a quadratic speedup. Our work establishes a natural problem with practical applications in computer networking that admits an exponential quantum space advantage, revealing a fundamental gap between quantum query complexity and streaming space complexity.

quant-pharXiv:2604.18014•Apr 21, 2026•3 citations

Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model

John Kallaugher, Ojas Parekh, Nadezhda Voronova

While the search for quantum advantage typically focuses on speed­ups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been restricted to specially-constructed problems Le Gall, SPAA ‘06 or polynomial advantage Kallaugher, FOCS ‘21. We show an exponential quantum space advantage for the maximum directed cut problem. This is the first known exponential quantum space advantage for any natural streaming problem. This also constitutes the first unconditional exponential quantum resource advantage for approximating a discrete optimization problem in any setting.

arXiv:2311.14123•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•15 citations

Parallel Quantum Advantage with Limited Adaptivity Requires Structure

Qipeng Liu, Saachi Mutreja

Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any $T$-query quantum algorithm, its acceptance probability can be approximated on a $(1-δ)$ fraction of inputs, up to $ε$ additive error, using $\mathrm{poly}(T, 1/ε, 1/δ)$ classical queries. At a high level, the conjecture suggests that exponential quantum speedups are possible only on sufficiently structured inputs. In this work, we make progress on this conjecture by proving it for quantum algorithms that make massively parallel quantum queries. In contrast, Yamakawa and Zhandry (Journal of the ACM, 2024) showed that quantum algorithms restricted to parallel queries can still achieve exponential speedups over classical algorithms for sampling problems. We establish our simulation theorem by proving the stronger statement that parallel-query quantum algorithms cannot distinguish the uniform distribution over oracles from oracles drawn from so-called "dense distributions". Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions. We further extend this approach beyond the purely parallel setting. We prove simulation theorems for quantum algorithms with constant rounds of adaptivity, and for quantum algorithms with a bounded quantum-query prefix followed by a massively parallel quantum-query stage.

quant-pharXiv:2608.20297•Aug 21, 2026•3 citations
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))(x,f(x))(x,f(x)) pairs for a uniformly random function fff 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 ddd and nnn evaluation points, attaining 1/2+Ω(d/n)1/2 + Ω(\sqrt{d/n})1/2+Ω(d/n​) fraction of satisfied OPI constraints via streaming requires Ω(n)Ω(n)Ω(n) classical bits of memory but only O(dlog⁡n)O(d\log n)O(dlogn) 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.
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 poly⁡(n)\operatorname{poly}(n)poly(n) qubits and succeeds with probability 1−o(1)1-o(1)1−o(1), whereas classical algorithms using at most 2c1nc22^{c_1n^{c_2}}2c1​nc2​ bits have success probability 2−Ω(n)2^{-\Omega(n)}2−Ω(n), for constants c1,c2>0c_1,c_2>0c1​,c2​>0.
For Optimal Polynomial Intersection, with n=q−1n=q-1n=q−1 evaluation points and polynomials of degree below ddd, streaming DQI achieves at least ⌈n/2+dn/8⌉\lceil n/2+\sqrt{dn}/8\rceil⌈n/2+dn​/8⌉ satisfied random constraints using O(dlog⁡n)O(d\log n)O(dlogn) qubits. When d=ω(log⁡n)d=\omega(\log n)d=ω(logn) and d=o(n/log⁡n)d=o(n/\log n)d=o(n/logn), achieving this target classically requires Ω(n)\Omega(n)Ω(n) bits; below a constant-times-nnn memory bound, success is at most 2−Ω(d)2^{-\Omega(d)}2−Ω(d). Taking d=Θ(log⁡2n)d=\Theta(\log^2 n)d=Θ(log2n) gives O(log⁡3n)O(\log^3 n)O(log3n) quantum space versus Ω(n)\Omega(n)Ω(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.
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%93\%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%76\%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.
How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment. We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests. To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting rrr independent matching requests requires Ω(r)Ω(r)Ω(r) qubits for r≤N1/2−δr\le N^{1/2-δ}r≤N1/2−δ and every fixed δ∈(0,1/2)δ\in(0,1/2)δ∈(0,1/2), even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through r=Θ(N)r=Θ(\sqrt N)r=Θ(N​). We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes. Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an Ω(n)Ω(n)Ω(n) space lower bound in random edge order for large enough cycles, with consequences for several graph problems. Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.
Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate 0.30.30.3, DQI achieves expected scores of approximately 0.850.850.85. In contrast, exceeding the classical threshold of 0.650.650.65 by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.
Near-term quantum devices with limited qubits motivate the study of space-bounded quantum computation in the data stream model. We show that Shannon entropy estimation exhibits an exponential separation between quantum and classical space complexity in this setting. Technically, we develop a two-stage quantum streaming algorithm based on a quantum procedure with an explicitly constructed oracle derived from the streaming input. This algorithm achieves logarithmic space complexity in the accuracy parameter over the data stream, whereas any classical streaming algorithm under the same pass complexity requires polynomial space. In sharp contrast, existing results for Shannon entropy estimation in the quantum query model achieve only a quadratic speedup. Our work establishes a natural problem with practical applications in computer networking that admits an exponential quantum space advantage, revealing a fundamental gap between quantum query complexity and streaming space complexity.
While the search for quantum advantage typically focuses on speed­ups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been restricted to specially-constructed problems Le Gall, SPAA ‘06 or polynomial advantage Kallaugher, FOCS ‘21. We show an exponential quantum space advantage for the maximum directed cut problem. This is the first known exponential quantum space advantage for any natural streaming problem. This also constitutes the first unconditional exponential quantum resource advantage for approximating a discrete optimization problem in any setting.
Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any TTT-query quantum algorithm, its acceptance probability can be approximated on a (1−δ)(1-δ)(1−δ) fraction of inputs, up to εεε additive error, using poly(T,1/ε,1/δ)\mathrm{poly}(T, 1/ε, 1/δ)poly(T,1/ε,1/δ) classical queries. At a high level, the conjecture suggests that exponential quantum speedups are possible only on sufficiently structured inputs. In this work, we make progress on this conjecture by proving it for quantum algorithms that make massively parallel quantum queries. In contrast, Yamakawa and Zhandry (Journal of the ACM, 2024) showed that quantum algorithms restricted to parallel queries can still achieve exponential speedups over classical algorithms for sampling problems. We establish our simulation theorem by proving the stronger statement that parallel-query quantum algorithms cannot distinguish the uniform distribution over oracles from oracles drawn from so-called "dense distributions". Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions. We further extend this approach beyond the purely parallel setting. We prove simulation theorems for quantum algorithms with constant rounds of adaptivity, and for quantum algorithms with a bounded quantum-query prefix followed by a massively parallel quantum-query stage.