Memory Constraints on Quantum Query and Sample Complexity

18 concepts10 papers

In theoretical quantum computer science, algorithms are frequently analyzed under idealized conditions. We often assume a quantum circuit has an arbitrarily large workspace of clean qubits, or that a quantum learning algorithm can store an infinite number of state copies to perform massive joint measurements.

However, physical quantum hardware is strictly limited. Qubits are a scarce resource, and maintaining quantum coherence across a large memory buffer is exceptionally difficult. This physical reality has driven a foundational research direction: characterizing the fundamental trade-offs between memory (both quantum and classical) and informational complexity (the number of queries or physical samples required to solve a problem).

Why Quantum Memory Compresses Sample Complexity

To understand why quantum memory is a critical resource, consider the task of learning properties of an unknown quantum state $\rho$ or identifying the dynamics of a quantum system. If an algorithm has zero quantum memory, it must ingest copies of $\rho$ sequentially, measuring each copy immediately before receiving the next. This restricts the learner to independent, local measurements.

When an algorithm possesses a quantum memory buffer, it can store multiple copies of $\rho$ and perform a joint measurement across the entire entangled ensemble. As demonstrated by Sitan Chen et al. in Exponential separations between learning with and without quantum memory, this capacity provides an exponential advantage. Without quantum memory, learning certain physical dynamics requires an unfeasible, exponential number of samples; with it, the sample complexity drops to polynomial. The authors proved a strict scaling law for intermediate regimes: as the available quantum memory decreases below the full system size, the required sample complexity grows exponentially relative to the missing memory capacity.

However, maximizing this trade-off introduces a hidden cost. In Optimal tradeoffs for estimating Pauli observables, Sitan Chen et al. showed that using multi-copy measurements to reduce qubit workspace requirements imposes a "precision tax." While storing and jointly measuring a few copies optimizes the sample dependence on the number of qubits ($n$), it severely degrades the dependence on the desired error tolerance ($\epsilon$), shifting the sample complexity from $1/\epsilon^2$ to $1/\epsilon^4$.

To circumvent these heavy memory requirements, alternative quantum resources can be leveraged. For instance, Robbie King et al. demonstrated in Exponential Learning Advantages with Conjugate States and Minimal Quantum Memory that if an algorithm is granted access to a state's complex conjugate alongside the state itself, it can achieve exponential learning advantages while maintaining a minimal quantum memory footprint.

The Space-Query Tension in Black-Box Algorithms

A parallel tension exists in query complexity, where the resource being minimized is the number of times an algorithm evaluates a black-box oracle.

Why does restricting workspace size (qubits) force an algorithm to make more queries? Quantum speedups typically rely on constructing and maintaining large superposition states that represent multiple computational paths simultaneously. If the qubit workspace is strictly limited, the algorithm cannot store these intermediate superpositions or maintain a history of previous states.

As noted by Scott Aaronson in Open Problems Related to Quantum Query Complexity, restricting the number of available qubits prevents optimal query efficiency for tasks like collision detection, because the system lacks the memory to track and cross-reference prior lookups. This persistence of classical space-time bottlenecks within the quantum realm was early identified by Jaikumar Radhakrishnan et al. in The Quantum Complexity of Set Membership, which proved that quantum data structures face rigid boundaries when trading off storage space for query probes.

Understanding this boundary allows researchers to deliberately design algorithms that accept a marginal increase in queries in exchange for massive space savings. In Robust and Space-Efficient Dual Adversary Quantum Query Algorithms, Michael Czekanski et al. utilized dimensionality reduction techniques to compress the general adversary method. The authors proved that many quantum algorithms originally requiring linear space can be modified to run using only logarithmic space, making them highly viable for near-term, memory-constrained hardware. This aligns with work by Kai DeLorenzo et al. in Applications of the quantum algorithm for st-connectivity, which demonstrated that reducing fundamental graph problems to undirected connectivity yields a logarithmic qubit complexity.

The Hidden Footprint of Classical Control

A complete picture of memory-constrained quantum computing cannot look at qubits alone; it must also account for the classical infrastructure required to operate the quantum system.

In Space Complexity of Streaming Algorithms on Universal Quantum Computers, Yanglin Hu et al. analyzed streaming problems by treating the classical controller's instruction set as a physical resource. The authors proved that when the classical memory needed to store quantum gate sequences is factored into the total space complexity, the celebrated exponential space advantages of quantum streaming algorithms completely vanish for core problems like equality testing.

Similarly, classical processing bottlenecks emerge in statistical tasks. Sergey Bravyi 0001 et al. showed in Quantum Algorithms for Testing Properties of Distributions that while quantum queries can dramatically speed up distribution testing, the algorithms still require significant classical memory that scales polynomially with the size of the outcome space to process the results.

To map the ultimate limits of these constraints, researchers also study alternative models of memory reuse. In Quantum Catalytic Space, Sathyawageeswar Subramanian et al. explored how space-bounded quantum computations can utilize an additional "catalytic" quantum memory—space that is borrowed, acted upon, and must be returned to its exact initial state, revealing that reusable memory structures can expand the power of logspace quantum circuits.

Conclusion

Quantum advantage is not an absolute property of an algorithm; it is a fluid boundary governed by resource trade-offs. Whether dealing with the sample complexity of state learning or the query complexity of black-box functions, restricting the available memory workspace forces a steep price in data acquisition. Mapping this trade-off curve is essential for translating asymptotic quantum speedups into practical protocols for real-world, memory-limited hardware.

Key Foundational Work

Quantum Algorithms for Testing Properties of Distributions (2011) — contributed 2 concept elements to this direction.
The Quantum Complexity of Set Membership (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quantum_memory_sample_tradeoff_70f345cc,
  title = {quantum memory-sample tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quantum-memory-sample-tradeoff/rdr_70f345ccb9ce40fd8d921ec7d50171ee},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_quantum_memory_sample_tradeoff_70f345cc_v1,
  title = {quantum memory-sample tradeoff},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quantum-memory-sample-tradeoff/rdr_70f345ccb9ce40fd8d921ec7d50171ee/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake