Abstract
Driven by exploring the power of quantum computation with a limited number of qubits, this work presents a novel complete characterization for space-bounded quantum computation. By developing a space-efficient variant of the Quantum Singular Value Transformation (QSVT), the authors identify the first natural complete problems for unitary coRQL and a new family of natural complete problems for BQL based on quantum state testing. Unlike time-bounded settings, space-bounded state testing for trace distance, Hilbert-Schmidt distance, and quantum entropy difference all correspond to the same complexity class.
Introduction
In quantum complexity theory, problems are typically categorized by the resources they consume: time (gate count) or space (qubit count). While time-bounded classes like BQP are well-understood, space-bounded classes such as BQL (Bounded-error Quantum Logspace) have historically lacked "natural" complete problems, often relying on abstract linear algebra tasks.
A significant hurdle in space-bounded algorithm design is the Quantum Singular Value Transformation (QSVT). Standard QSVT implementations are space-intensive, requiring pre-processing steps to find rotation angles that often turn logarithmic-space algorithms into polynomial-space ones. This paper bridges this gap by introducing a space-efficient QSVT and using it to define the limits of computation with restricted qubits.
Methodology: Space-Efficient QSVT
The primary technical contribution is a variant of QSVT that minimizes ancillary qubit overhead.
- Averaged Chebyshev Truncation: Instead of the computationally expensive search for rotation angles, the authors employ "de La Vallée Poussin partial sums" to approximate functions using Chebyshev polynomials.
- Linear Combination of Unitaries (LCU): These polynomial approximations are implemented via the LCU framework, allowing the application of functions to singular values with only constant overhead in ancillary space.
- Algorithmic Holevo-Helstrom Measurement: The new QSVT enables a space-constrained implementation of the Holevo-Helstrom measurement, the optimal method for distinguishing quantum states.
Key Insights and Results
A central revelation of this research is that for space-bounded quantum circuits, testing is as easy as preparing. In the space-bounded regime, determining the distance between two states is no more difficult than the act of preparing those states themselves.
Furthermore, the choice of distance measure—which significantly impacts complexity in time-bounded settings—becomes irrelevant in the space-bounded context. Measures such as Trace Distance ($ℓ_1$ norm), Hilbert-Schmidt distance ($ℓ_2$ norm), and Entropy Difference all collapse into the same complexity level: BQL-complete.
Major Contributions:
- Natural Complete Problems: Identification of the first natural complete problems for coRQUL (one-sided error) and new problems for BQL centered on state certification and testing.
- QSZK and QIP(2): An improved upper bound for Quantum Statistical Zero Knowledge (QSZK), showing it is contained within QIP(2) with a linear-space honest prover.
- Constant Space Overhead: Demonstration that implementing QSVT for piecewise-smooth functions incurs only constant qubit overhead relative to the original encoding.
Limitations and Future Work
While a single application of this QSVT is space-efficient, iterative applications (beyond a constant number) could lead to non-logarithmic qubit growth. Developing methods to "reset" or compress this ancillary space remains an open challenge. Additionally, the current approach has a quadratic dependence on the polynomial degree for query complexity; achieving linear dependence would optimize the algorithm for both space and time. Finally, the authors suggest exploring whether all symmetric $f$-divergences are similarly BQL-complete in this setting.
Summary updated