Can Random Order Replenish Quantum Memory in Streaming Problems?

Replenishment is rebuilding a consumed quantum state

A quantum sketch can hold useful information in very little space, but querying it may remove elements or destroy it. The paper's motivating example is Hidden Matching: Alice holds a Boolean string x of N bits, Bob holds a perfect matching on [N], and Bob must output an edge of his matching together with the parity of its two endpoints in x. A phase encoding of x using O(log N) qubits lets Bob measure and answer correctly, but that measurement consumes the state; a second matching would need a second copy.

In a stream, the data describing x keeps arriving. An occurrence of a coordinate already seen need not reveal anything new about x, yet it can still be used to prepare a fresh quantum state after an earlier one has been measured. The paper calls this replenishment, and builds its algorithm on the phase-accumulation method of quantum oracle sketching, which constructs coherent quantum operations from randomly arriving classical samples.

The order of those occurrences is what matters. If all data arrives before the requests, the algorithm must answer every request from stored memory alone. If updates arrive between requests, the same small memory can be reused. The paper isolates this timing question in an artificial problem rather than claiming that all streaming tasks behave the same way.

One problem separates three streaming models

The paper introduces Atomized Refreshable Hidden Matching (ARHM). Its stream presents a fixed Boolean string through repeated coordinate updates, interspersed with Hidden Matching requests. Each request asks for an edge of a specified matching and the parity of its endpoints, and must be answered before the next item arrives. All three models compared receive the same multiset of input items and must meet the same output deadlines, with joint success probability at least 2/3, and space is measured as a function of stream length.

Under uniformly random order, ARHM admits a one-pass quantum algorithm using O(log N log r + 1) space, where r is the number of independent online matching requests and r is at most the square root of N. The algorithm constructs approximate Hidden Matching phase states from arriving coordinate items, consumes them to answer requests, and replenishes them from later coordinate items.

The same problem unconditionally requires polynomial space for classical random-order algorithms and for quantum algorithms in adversarial order. The paper states that this is, to its knowledge, the first unconditional exponential space separation between one-pass quantum random-order and quantum adversarial-order streaming that allows online outputs. The adversarial-order lower bound already holds when all updates precede all requests.

The two lower bounds rule out two easy explanations. The classical random-order algorithm receives the same repeated data as the quantum algorithm, so repetition alone does not account for the small quantum space bound. The quantum adversarial-order algorithm also receives all the repetitions, so the amount of data supplied does not explain the gap between the two quantum models. What changes is whether the data remains available while requests are answered.

Repeated requests cost linear qubits, not square-root

The quantum update-first lower bound rests on a communication question: Alice holds one input, Bob wants to answer several questions about it, and the message must grow with the number of questions even though Alice's underlying data stays the same. Gilboa, Jain, and McClean formalized this through consumable quantum data and proved an Omega(sqrt(m)) quantum communication lower bound for m Hidden Matching requests when m is at most N/2.

The paper strengthens this. For Multiple Hidden Matching, without prior entanglement, any quantum encoding supporting r independent matching requests requires Omega(r) qubits for r at most N^(1/2 - delta) and every fixed delta in (0, 1/2), even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through r = Theta(sqrt(N)). In both cases all answers must be correct with probability at least 2/3, and Alice may choose an arbitrary encoding.

The proof uses a forest-information argument. Correct edge parities on a forest with s edges impose s independent constraints on a uniform string X, so once the output transcript is fixed at most 2^(N - s) strings satisfy those constraints; cycles add no independent parity constraint, so the useful quantity is the spanning forest size of the selected edges. For simultaneous requests, the argument forces a large forest for every coordinated edge choice, which requires a small vertex set containing an edge of every requested matching; for independent balanced matchings this probability is bounded by a union bound over sets of 2s vertices. For sequential requests, the forest is analyzed as it grows, and the chance that a new edge fails to increase forest size is at most (i choose 2)/(N - 1) after i - 1 output edges.

Because the cost is a property of the task rather than of the usual Hidden Matching protocol, it transfers to ARHM when all updates precede the requests, and also applies when an interleaved prefix is followed by a sufficiently long sequence of fresh independent requests with no further updates.

Repeated edges let one sketch serve successive blocks

The paper then asks whether replenishment improves an algorithm for an established graph problem. Kallaugher's triangle-counting algorithm, the first polynomial quantum space advantage for a natural streaming problem, combines a quantum sketch with a classical sampling estimator; obtaining enough observations for an accurate estimate requires many copies of the estimator to coexist.

The paper adapts this algorithm to uniformly random streams in which every edge of the underlying simple graph appears equally often, with all occurrences uniformly permuted. Later occurrences let the algorithm rebuild the quantum sketch and resample the classical estimator, obtaining further observations with the same memory across successive blocks of the stream. Rebuilding the sketch and resampling the estimator improve the expected-space bound in suitable parameter regimes.

The quantity being estimated is still the number of triangles in the underlying graph; repetition changes access to the graph, not the answer. This is an algorithmic use of replenishment under a stronger input promise, and the paper notes that its arbitrary-encoding consumability lower bounds concern Hidden Matching rather than triangle counting.

Noisy Gap Cycle keeps its linear quantum space cost

The second behavior is an obstruction that survives quantum memory. The paper extends the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. Noisy Gap Cycle is useful for studying the difficulty of recovering global graph structure from a stream because short portions of a cycle do not reveal its length.

The additional quantum ingredient is a lower bound for Block Hidden XOR, a problem implicit in the original paper, obtained by replacing the classical Fourier-analytic step with its standard matrix-valued analog. For sufficiently large w and t at least 512 ln w, any one-way quantum protocol for Distributional Hidden XOR with success at least 1/2 + 1/(6w) communicates Omega(wt) qubits.

This yields an Omega(n) one-pass quantum space lower bound for Noisy Gap Cycle in uniformly random edge order, for admissible cycle lengths at least Omega(log n) where n is the number of vertices, with error at most 1/3. The corresponding one-way quantum communication problem under a uniformly random edge partition also requires linear communication without prior entanglement.

The resulting applications include lower bounds for approximating connected components, matching, independent set, and minimum spanning tree weight, and for generating random walks. The paper is explicit that the approximation results restrict how space depends on accuracy; they do not assert linear space for every fixed approximation error.

Where the lower bounds stop and what stays open

The Noisy Gap Cycle bound concerns single-arrival graph streams, with a decision made after the pass, and the transfer proposition requires that continuation be determined by the complete live state and public parameters together with Bob's remaining input, so any needed position or control information must be counted in the state or locally reconstructible. The paper also notes that the current reduction does not automatically give a rank lower bound under uniformly random individual matrix-entry order, because one graph edge produces a coupled pair of nonzero Tutte-matrix entries, so random graph-edge order yields random order of pairs rather than necessarily random order of the individual entries.

The paper states an open question directly: can repeated edges reduce the quantum space required for Noisy Gap Cycle? Its lower bound concerns a single arrival of each edge. Under repetition, a random partition of stream items can expose copies of the same edge to both parties, changing the information available in the communication problem, so the present argument does not establish a lower bound for repeated-edge streams.

The paper also reports concurrent work by Bouland, Ding, and Jain proving exponential quantum-classical space separations in random-order streaming for Code Intersection and low-rate Optimal Polynomial Intersection. Their quantum algorithms work in every order while their classical lower bounds hold in random order; the ARHM result gives a concurrent exponential quantum-classical separation under different input and output requirements, and additionally compares two orders of the same stream within the quantum model.

Read the result as a split, not a general rule

The paper's own framing is that there is no single answer to how random order changes the role of quantum memory. The effect depends on the nature of the data, the way information is distributed among items in the stream, and how later computation uses information from the earlier part of the input.

The sharpest comparison is between ARHM and Noisy Gap Cycle. In ARHM, later coordinate items replenish a small consumable representation, giving polylogarithmic quantum space in uniformly random order against polynomial space classically in random order and quantumly when updates precede requests. In Noisy Gap Cycle, the Assadi-Sundaresan random-order lower-bound framework remains robust in the quantum setting, and linear quantum space is still required for large enough cycles.

The most decision-relevant threshold is the timing of access. The ARHM separation turns on whether updates remain available while requests are answered, not on how much data the stream contains, since all three models receive the same multiset of items. The consumability bound marks the boundary: once access to the source ends, answering r independent matching requests from one quantum message costs Omega(r) qubits for r up to N^(1/2 - delta) with simultaneous revelation, and through r = Theta(sqrt(N)) for sequential requests. Whether repeated edges can push the Noisy Gap Cycle obstruction below linear space is left open.

Sources used in this answer