PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential quantum space advantage in random data streams

Adam Bouland, Matthew Ding, Siddhartha Jain

arXiv:2610.03645v1quant-phcs.CC

TL;DR

The paper asks whether quantum algorithms can achieve exponential space advantage when streaming inputs in uniformly random order. It combines communication-lower-bound ideas with branching-program techniques and adapts them to Code Intersection and OPI. It proves exponential quantum advantage for random-order Code Intersection and a streaming OPI space advantage in certain parameter regimes.

  • Problem

    Prior proven exponential quantum space advantages in streaming used structured or worst-case streams, leaving open whether one holds under uniformly random ordering.

    Source: §1 · p. 2

  • Method

    The authors combine communication lower-bound techniques with ROBP methods, using density-restoring partitions and a convex potential adapted to Code Intersection and OPI.

    Source: §1.2 · p. 4

  • Results

    Random-order Code Intersection needs poly(n) qubits quantumly versus exp(n^Ω(1)) classical bits; for OPI, DQI uses O(d log n) qubits while classical streaming needs Ω(n) bits to achieve the stated value.

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    The Code Intersection result demonstrates quantum advantage without structure in either input values or stream ordering.

    Source: §1.1 · p. 3

    The lower bounds apply to streaming models and do not establish an advantage for the original OPI problem.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

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. Our lower bound is shown using density-restoring partitions as in the work of G\"o\"os, Gur, Jain, and Li (STOC 2025) combined with a convex potential, similar to the work of Raz (J.ACM 2018) on parity learning and its generalization by Garg, Raz, and Tal (STOC 2018). 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 (Nature 2025; arXiv:2510.10967). In particular, we show that for degree $d$ and $n$ evaluation points, attaining $1/2 + \Omega(\sqrt{d/n})$ fraction of satisfied OPI constraints via streaming requires $\Omega(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.

1 Introduction

The paper establishes quantum space advantages for two problems in random-order streaming, including Code Intersection on completely unstructured streams. It combines techniques for communication and branching-program lower bounds, with a convex potential adapted to Code Intersection and OPI.

1 Introduction

  • The open question is whether quantum algorithms can achieve exponential streaming-space advantage when inputs arrive in uniformly random order.Prior proven exponential advantages used structured or worst-case streams, and one maximum-directed-cut advantage disappears under random ordering.Source: §1 · p. 2

1.1 Our results

  • Code Intersection admits exponential quantum space advantage in random order: the Yamakawa–Zhandry algorithm uses poly(n) qubits, while classical streaming requires exp(n^Ω(1)) bits.The result applies even to uniformly random function values streamed as (x, f(x)) pairs in uniformly random order.Source: §1.1 · pp. 2–3
  • For streaming OPI, DQI achieves the stated value using O(d log n) qubits, while classical algorithms achieving that value require Ω(n) bits.The stated bounds hold when d = ω(log n) and d = o(n / log n); an exponential separation occurs, for example, at d = Θ(log^2 n), yielding O(log^3 n) quantum versus Ω(n) classical space.Source: §1.1 · p. 3, §1.2 · p. 3

1.2 Proof sketch

  • Both quantum algorithms are nonadaptive, so their input-dependent commuting gates can be applied in one streaming pass.The paper uses a more space-efficient version of DQI [KSG+25].Source: §1.2 · p. 3
  • Existing communication lower bounds do not directly transfer to random-order streams, and generic ROBP techniques target unique planted solutions rather than these search problems.Code Intersection also has a zero-communication protocol in random order.Source: §1.2 · p. 4
  • The lower-bound approach combines the Code Intersection communication technique with ROBP methods for space-bounded learning.The authors cannot reduce the random-order setting to subcubes because the coordinate-wise input split used in that argument no longer holds.Source: §1.2 · p. 4
  • Density-restoring partitions concentrate certainty onto a small fixed marginal while leaving other marginals near-maximally uncertain, supporting the entropy analysis.The partitions draw on query-to-communication lifting work.Source: §1.2 · p. 4
  • A convex potential tracks progress by summing conditional probabilities of codewords that have crossed a threshold of coordinates mapped to 1.For OPI, the potential allows approximation, while the lower bound uses the fact that distinct degree-less-than-d polynomials agree on at most d − 1 points.Source: §1.2 · pp. 4–5

2 Preliminaries

The preliminaries define the random-order streaming problems and the branching-program framework used to analyze them. They also establish the code and entropy tools used in the lower bounds.

2.1 Probability

  • The preliminaries set probability and notation conventions used throughout the analysis, including Hoeffding’s inequality for sums of independent bounded variables.They also specify notation for supports, indicators, and the min-entropy of a random variable.Source: §2 · p. 5, §2.1 · pp. 5–6, §2.5 · p. 9

2.2 Streaming model and problem definition

  • A stream contains oracle-labeled address pairs, and the problems ask for a codeword or polynomial meeting specified oracle constraints after one pass.For Code Intersection, every selected coordinate must map to 1; OPI requires at least τ satisfied evaluation points.Source: §2.2 · pp. 6–7

2.3 Branching programs

  • The analysis models deterministic streaming algorithms as layered branching programs whose width represents bounded memory.A fixed stream determines a computation path, and each leaf corresponds to an output.Source: §2.3 · p. 7

2.4 List-recoverable codes

  • List-recoverability bounds how many codewords can agree with coordinate-wise candidate lists of limited total size.The folded Reed–Solomon family is used for the Code Intersection lower bound and has the stated list-recoverability property.Source: §2.4 · p. 8

2.5 Min-entropy and density-restoring partitions

  • A density-restoring partition decomposes a high-min-entropy distribution into parts fixed on some coordinates and dense on the remaining coordinates.The preliminaries introduce this tool alongside min-entropy bounds for branching-program states.Source: §2.5 · p. 9

1. Core group X core: Every X (j) in the group satisfies

The core group comprises partition parts whose entropy deficit is not too small. Its entropy constraints relate the size of the fixed coordinate set to the remaining coordinates’ min-entropy.

Core group X core

  • Each part fixes the coordinates in I_j to α_j, while the complementary marginal has min-entropy between |J| − D − γ|I_j| + δ_j and |J| − |I_j|.These bounds follow from the partition properties and the support’s assumed min-entropy.Source: §1 · p. 10
  • For each core part, the deficit parameter δ_j is at least log(η).The core consists of parts with indices j < j*, where j* is the first index with δ_j < log(η).Source: §1 · p. 10
  • The excess group collects parts with indices j ≥ j*, beginning at a part whose deficit is below log(η).If no such index exists, the excess group is empty.Source: §1 · p. 10

3 Classical space lower bound for streaming Code Intersection

The section proves classical space lower bounds for random-order Code Intersection by tracking how much candidate codeword information a streaming algorithm can accumulate. A threshold-crossing potential and list-recoverability control that accumulation.

3 Classical space lower bound for streaming Code Intersection

  • In random order, conditioned on the observed addresses and memory state, the next element is uniform among unseen addresses with an independent fair oracle bit, and receiving it leaves the oracle posterior unchanged.This conditional structure supports the potential-growth analysis.Source: §3 · p. 10

3.1 Potential method for Code Intersection space lower bound

  • The threshold-crossing potential tracks only codewords with enough observed matching addresses and posterior success probability above a cutoff.The threshold is eventually set using ρ, n, γ, and η, with η exponentially small in n.Source: §3.1 · p. 11

3.2 Applying the potential to Code Intersection

  • Density-restoring partitions and list-recoverability bound the contribution of high-posterior candidates, controlling the potential’s growth as codewords first cross the threshold.The proof separates good and bad vertices using posterior min-entropy and bounds the good-vertex contribution through list-recovery.Source: §3.2 · pp. 13, 16
  • For the folded Reed–Solomon Code Intersection instance, success is at most 2^-Ω(n) for sufficiently large n under the theorem’s stated memory bound.The theorem’s probability is over the oracle and stream ordering.Source: §3.2 · p. 16
  • For general list-recoverable codes satisfying the stated parameter conditions, any algorithm using o(ℓ) memory has success at most 2^-Ω(n).The parameter conditions include log |C| + n = o(ℓ) and log L + log log M = o(n).Source: §3.2 · p. 17

4 Classical space lower bound for streaming Optimal Polynomial Intersection

The section extends the threshold-potential lower-bound framework from Code Intersection to OPI. For Reed–Solomon evaluation vectors, it obtains an exponentially small success bound for classical algorithms within the theorem’s stated setting.

4.1 Extending the potential to constraint optimization

  • The generalized potential tracks the chance that a codeword reaches a target value τ, using a threshold κ that can vary with the number of observed addresses.It begins at zero and bounds the final success probability.Source: §4.1 · pp. 17–18

4.2 Bounding the potential for Optimal Polynomial Intersection

  • Unlike the Code Intersection argument, the OPI high-value-polynomial bound does not use density-restoring partitions; it uses the pairwise agreement limit instead.The OPI potential threshold concerns observed value, not merely the number of observed coordinates.Source: §4.2 · p. 19
  • For OPI, the proof bounds high-value polynomials using the fact that distinct degree-less-than-d polynomials agree on at most d − 1 evaluation points.Under the lemma’s conditions, fewer than n/(dη) codewords have event probability at least 2η.Source: §4.2 · p. 19
  • For OPI, any classical streaming algorithm using at most cn bits of memory has success at most 2^-Ω(d) in the theorem’s stated setting.The probability is over the oracle and stream ordering.Source: §4.2 · p. 22

A Quantum streaming algorithms for Code Intersection and Optimal Polynomial Intersection

The section presents quantum streaming algorithms for Code Intersection and Optimal Polynomial Intersection (OPI). The Yamakawa–Zhandry algorithm uses polynomial memory for every stream ordering, while the OPI algorithm uses O(d log n) memory and succeeds with high probability for every ordering.

Related papers

Loading 2610.03645v1…