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

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 $\mathsf{coRQL}$) and two-sided error ($\mathsf{BQL}$), approached from a quantum state testing perspective: - The first family of natural complete problems for unitary $\mathsf{coRQL}$, namely space-bounded quantum state certification for trace distance and Hilbert-Schmidt distance; - A new family of natural complete problems for $\mathsf{BQL}$, namely space-bounded quantum state testing for trace distance, Hilbert-Schmidt distance, and (von Neumann) 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 $\ddot{I}{}_0$ and $\ddot{I}{}_1$, respectively, with access to their ``source code''. Our goal is to decide whether $\ddot{I}{}_0$ is $\hat{I}{\mu }_1$-close to or $\hat{I}{\mu }_2$-far from $\ddot{I}{}_1$ with respect to a specified distance-like measure. Interestingly, unlike time-bounded state testing problems, which exhibit computational hardness depending on the chosen distance-like measure, our results reveal that the space-bounded state testing problems, considering all three measures, are computationally as easy as preparing quantum states. Our results primarily build upon a space-efficient variant of the quantum singular value transformation (QSVT) introduced by Gilyén, 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.

73 pages, 3 figures, 4 algorithms. v3: Section 5 of [v2] was removed and extended into arXiv:2512.11597; calculation errors in Lemma 2.15 were fixed, with corresponding changes in later results; and minor changes were made. v2: Clarified the scope of robust oblivious AA in Theorem 3.17, and added new results on algorithmic Holevo-Helstrom measurement and an implication for QSZK in Section 5