Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds
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≤ N1/2−δ and every fixed δ∈(0,1/2), even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through 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) 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.
Related
- TandemQEC: Joint Provisioning of Streaming Quantum Error Correction in Tightly-Integrated Quantum-Classical Systems
- Streaming the partial-transpose moment hierarchy with order-independent quantum memory
- Exponential quantum advantages for decoded quantum interferometry in the streaming setting
- Streaming Regev's Quantum Factoring Algorithm
- Passive-reflector bounds and robust bilateral nonequilibrium Casimir repulsion
BibTeX
@misc{voronova2026random,
title = {{Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds}},
author = {Nadezhda Voronova},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06727},
eprint = {2610.06727},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06727},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds
AU - Nadezhda Voronova
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06727
UR - https://arxiv.org/abs/2610.06727
AB - 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≤ N^1/2−δ and every fixed δ∈(0,1/2), even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through 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) 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.
ER -