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.06727

Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds

Nadezhda Voronova

quant-phcs.DSSubmitted Oct 5, 2026• Announced Oct 6, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks how random arrival order changes quantum streaming memory when queries consume stored states. Its mechanism, “replenishment,” uses later repetitions of classical data to rebuild quantum sketches between queries. It constructs Atomized Refreshable Hidden Matching (ARHM), an artificial problem with repeated coordinate updates and immediate matching-query outputs. For $r\le\sqrt N$ requests and stream length $\Theta(Nr^2)$, quantum random-order space is $O(\log N\log(r+1))$, whereas classical random-order space is $\Omega(\sqrt N)$ and quantum update-first space is $\Omega(r)$, with all answers jointly correct with probability at least $2/3$. The algorithm accumulates weak coordinate phases in alternating register banks; hypergeometric error bounds and request-occupancy tails control accuracy and availability. The quantum lower bounds strengthen Multiple Hidden Matching consumability: arbitrary one-way encodings require $\Omega(r)$ qubits for simultaneous requests when $r\le N^{1/2-\delta}$ for fixed $\delta>0$, and for sequential requests through $r=\Theta(\sqrt N)$. The proofs extract independent parity information from forests in the selected output edges. For triangle counting with exactly $R$ repetitions per edge in random order, rebuilding quantum and classical estimators gives expected simultaneous space $\widetilde O(1+m^{8/5}\Delta_E^{4/5}/(RT^{6/5}))$ in specified regimes. This assumes supplied parameter estimates and does not establish a separation or expected-peak-space bound. Finally, matrix hypercontractivity yields a quantum Block Hidden XOR communication bound, extending robust Noisy Gap Cycle reductions to prove $\Omega(n)$ quantum space for admissible cycle lengths $k\ge1600\ln n$, with graph-problem consequences. Communication bounds exclude prior entanglement. Natural-problem order separations, optimal repeated-edge complexities, and NGC hardness under repetition remain open.

Little sign of AI-generated textAI use disclosedStrong assumptions
AI tools (GPT-6 Astra) were used to prototype the proofs, search for the right parameter regimes, or shorter/cleaner proofs

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy

Minbo Gao, Chenghua Liu, Guangxu Yang +1 more

We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of a quantum protocol jointly. As applications of our method, we establish the first tight quantum lower bounds for two fundamental search problems in some natural parameter regimes: collision finding and triangle finding. For collision finding, we prove a tight $Ω(N^{1/4})$ one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was $Ω(N^{1/12})$ due to Göös and Jain (RANDOM 2022), and no stronger bound was known even under the one-way restriction. For triangle finding in graph streams, we prove a one-pass quantum streaming space lower bound of $Ω\left(\sqrt{Δ_V}\right)$ for graphs with $m$ edges, $Θ(m)$ triangles, and constant $Δ_E$, where $Δ_V$ and $Δ_E$ denote the maximum number of triangles sharing a common vertex and edge, respectively, under the condition that $1\le Δ_V\le m^{2/3}$. This constitutes the first nontrivial quantum space lower bound in this regime, matching the classical upper bound of Jayaram and Kallaugher (RANDOM 2021) up to logarithmic factors. Notably, our method also recovers the classical lower bound of Kallaugher and Price (SODA 2017) through an entirely different argument, avoiding their Boolean-Hidden-Matching reduction that breaks down for quantum protocols.

quant-pharXiv:2607.08517•Jul 10, 2026•1 citation

Exponential quantum space advantage in random data streams

Adam Bouland, Matthew Ding, Siddhartha Jain

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.

quant-pharXiv:2610.03645•Oct 5, 2026•3 citations

A Quantum Advantage for a Natural Streaming Problem

John Kallaugher

Data streaming, in which a large dataset is received as a "stream" of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA `06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph streaming - the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.

arXiv:2106.04633•Jun 8, 2021•1 citation

A Quantum Advantage for a Natural Streaming Problem

John Kallaugher

Data streaming, in which a large dataset is received as a “stream” of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA '06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best-studied problems in classical graph streaming-the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.

Annual Symposium on Foundations of Computer Science•Feb 1, 2022•9 citations

A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds

Paul Beame, Blake Holman, Niels Kornerup

Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.

cs.CCCross-listedarXiv:2609.40334•Oct 1, 2026•0 citations

A Quantum Advantage for a Natural Streaming Problem.

John Kallaugher

Data streaming, in which a large dataset is received as a stream of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA `06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph streaming - the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.

•Jan 1, 2022•1 citation
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.
The paper asks how random arrival order changes quantum streaming memory when queries consume stored states. Its mechanism, “replenishment,” uses later repetitions of classical data to rebuild quantum sketches between queries.
It constructs Atomized Refreshable Hidden Matching (ARHM), an artificial problem with repeated coordinate updates and immediate matching-query outputs. For r≤Nr\le\sqrt Nr≤N​ requests and stream length Θ(Nr2)\Theta(Nr^2)Θ(Nr2), quantum random-order space is O(log⁡Nlog⁡(r+1))O(\log N\log(r+1))O(logNlog(r+1)), whereas classical random-order space is Ω(N)\Omega(\sqrt N)Ω(N​) and quantum update-first space is Ω(r)\Omega(r)Ω(r), with all answers jointly correct with probability at least 2/32/32/3. The algorithm accumulates weak coordinate phases in alternating register banks; hypergeometric error bounds and request-occupancy tails control accuracy and availability.
The quantum lower bounds strengthen Multiple Hidden Matching consumability: arbitrary one-way encodings require Ω(r)\Omega(r)Ω(r) qubits for simultaneous requests when r≤N1/2−δr\le N^{1/2-\delta}r≤N1/2−δ for fixed δ>0\delta>0δ>0, and for sequential requests through r=Θ(N)r=\Theta(\sqrt N)r=Θ(N​). The proofs extract independent parity information from forests in the selected output edges.
For triangle counting with exactly RRR repetitions per edge in random order, rebuilding quantum and classical estimators gives expected simultaneous space O~(1+m8/5ΔE4/5/(RT6/5))\widetilde O(1+m^{8/5}\Delta_E^{4/5}/(RT^{6/5}))O(1+m8/5ΔE4/5​/(RT6/5)) in specified regimes. This assumes supplied parameter estimates and does not establish a separation or expected-peak-space bound.
Finally, matrix hypercontractivity yields a quantum Block Hidden XOR communication bound, extending robust Noisy Gap Cycle reductions to prove Ω(n)\Omega(n)Ω(n) quantum space for admissible cycle lengths k≥1600ln⁡nk\ge1600\ln nk≥1600lnn, with graph-problem consequences. Communication bounds exclude prior entanglement. Natural-problem order separations, optimal repeated-edge complexities, and NGC hardness under repetition remain open.
We study one-way quantum communication lower bounds for search problems. Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of a quantum protocol jointly. As applications of our method, we establish the first tight quantum lower bounds for two fundamental search problems in some natural parameter regimes: collision finding and triangle finding. For collision finding, we prove a tight Ω(N1/4)Ω(N^{1/4})Ω(N1/4) one-way quantum communication lower bound. Previously, the best-known quantum communication lower bound for collision finding was Ω(N1/12)Ω(N^{1/12})Ω(N1/12) due to Göös and Jain (RANDOM 2022), and no stronger bound was known even under the one-way restriction. For triangle finding in graph streams, we prove a one-pass quantum streaming space lower bound of Ω(ΔV)Ω\left(\sqrt{Δ_V}\right)Ω(ΔV​​) for graphs with mmm edges, Θ(m)Θ(m)Θ(m) triangles, and constant ΔEΔ_EΔE​, where ΔVΔ_VΔV​ and ΔEΔ_EΔE​ denote the maximum number of triangles sharing a common vertex and edge, respectively, under the condition that 1≤ΔV≤m2/31\le Δ_V\le m^{2/3}1≤ΔV​≤m2/3. This constitutes the first nontrivial quantum space lower bound in this regime, matching the classical upper bound of Jayaram and Kallaugher (RANDOM 2021) up to logarithmic factors. Notably, our method also recovers the classical lower bound of Kallaugher and Price (SODA 2017) through an entirely different argument, avoiding their Boolean-Hidden-Matching reduction that breaks down for quantum protocols.
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.
Data streaming, in which a large dataset is received as a "stream" of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA `06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph streaming - the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.
Data streaming, in which a large dataset is received as a “stream” of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA '06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best-studied problems in classical graph streaming-the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.
Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an Ω(n4/3(log⁡log⁡n)/(S1/3log⁡n))Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))Ω(n4/3(loglogn)/(S1/3logn)) lower bound on the number of queries that a fully general quantum algorithm with at most SSS qubits of memory requires to sort nnn numbers from [n2][n^2][n2]. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family HHH from nnn bits to mmm bits, almost all hash functions in HHH require any algorithm with at most SSS qubits of memory to make Ω(nm/S)Ω(nm/S)Ω(nm/S) quantum queries to input xxx in order to compute h(x)h(x)h(x), even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing h(x)h(x)h(x) with both hhh and xxx as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.
Data streaming, in which a large dataset is received as a stream of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA `06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph streaming - the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.