Space-bounded quantum state testing via space-efficient quantum singular value transformation

François Le Gall, Yupan Liu, Qisheng Wang

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.

  1. 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.
  2. 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.
  3. 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.

Comparison of complexity classes for state testing across different computational models and distance measures.

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

Abstract

Driven by exploring the power of quantum computation with a limited number of qubits, we present a novel complete characterization for space-bounded quantum computation, which encompasses settings with one-sided error (unitary coRQL) and two-sided error (BQL), approached from a quantum state testing perspective: - The first family of natural complete problems for unitary coRQL, i.e., space-bounded quantum state certification for trace distance and Hilbert-Schmidt distance; - A new family of natural complete problems for BQL, i.e., space-bounded quantum state testing for trace distance, Hilbert-Schmidt distance, and quantum entropy difference. In the space-bounded quantum state testing problem, we consider two logarithmic-qubit quantum circuits (devices) denoted as $Q_0$ and $Q_1$, which prepare quantum states $\rho_0$ and $\rho_1$, respectively, with access to their ``source code''. Our goal is to decide whether $\rho_0$ is $\epsilon_1$-close to or $\epsilon_2$-far from $\rho_1$ with respect to a specified distance-like measure. Interestingly, unlike time-bounded state testing problems, our results reveal that the space-bounded state testing problems all correspond to the same class. Moreover, our algorithms on the trace distance inspire an algorithmic Holevo-Helstrom measurement, implying QSZK is in QIP(2) with a quantum linear-space honest prover. Our results primarily build upon a space-efficient variant of the quantum singular value transformation (QSVT) introduced by Gily\'en, Su, Low, and Wiebe (STOC 2019), which is of independent interest. Our technique provides a unified approach for designing space-bounded quantum algorithms. Specifically, we show that implementing QSVT for any bounded polynomial that approximates a piecewise-smooth function incurs only a constant overhead in terms of the space required for special forms of the projected unitary encoding.
BibTeX
@article{gall2023space,
  author = {François Le Gall and Yupan Liu and Qisheng Wang},
  title = {{Space-bounded quantum state testing via space-efficient quantum singular value transformation}},
  journal = {Electron. Colloquium Comput. Complex.},
  year = {2023},
  url = {https://openreview.net/forum?id=QRqoRtOwbb},
}
Figure