arXiv:2610.06727
Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds
Nadezhda Voronova
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.
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.