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

arXiv:2308.05079 · quant-ph, cs.CC · Submitted 2023-08-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Space-bounded quantum state testing via space-efficient quantum singular value transformation".

Mira: Here's the gist of the paper. Driven by exploring the power of quantum computation with a limited number of qubits, this paper presents a novel complete characterization for space-bounded quantum computation, encompassing settings with one-sided error (unitary coRQL) and two-sided error (BQL), approached from a quantum (mixed) state testing perspective.

Kai: The first family of natural complete problems for unitary coRQL are space-bounded quantum state certification for trace distance and Hilbert–Schmidt distance.

Mira: A new family of natural BQL-complete problems are spacebounded quantum state testing for trace distance, Hilbert–Schmidt distance, and (von Neumann) entropy difference.

Kai: The results reveal that the space-bounded state testing problems, considering all three measures, are computationally as easy as preparing quantum states.

Title and authors: Kai: So this paper is called "Space-bounded quantum state testing via space-efficient quantum singular value transformation". It sounds a bit dense, but essentially it's about figuring out what kind of problems you can solve when you only have a limited amount of space on your quantum computer.

Mira: That's right. It looks at two different kinds of error scenarios, one-sided error and two-sided error, and shows how to characterize the complete problems for both using this new testing perspective.

Lev: From an engineering standpoint, it’s interesting because we’re always trying to define the limits of what a quantum device can actually do given its physical constraints like qubit count and gate depth.

Kai: Exactly. The authors are proposing a way to characterize these space-bounded problems that is more natural than the ones that have been studied before, which mostly focused on two-sided error scenarios.

Mira: They're suggesting new complete problems for one-sided error, specifically space-bounded quantum state certification for trace distance and Hilbert–Schmidt distance, and a new set of natural complete problems for two-sided error.

Lev: When we think about building hardware, knowing the exact limits—the complexity class—of what’s possible under strict resource constraints is crucial for designing effective error correction or simulation schemes.

The paper's summary: Kai: So, they summarize this by saying that the space-bounded state testing problems, when you consider all three distance measures they mention, are computationally as easy as just preparing the quantum states themselves.

Mira: That’s a very strong claim. They found that the space-bounded state testing problems for trace distance, Hilbert–Schmidt distance, and von Neumann entropy difference are natural complete for two-sided error.

Lev: If it means they are equivalent in difficulty to just preparing the state, that tells us something about how hard it is to actually verify a quantum computation outcome when resources are limited.

Kai: It really does suggest that the ability to test these properties isn't fundamentally harder than the preparation itself when space is restricted.

Mira: The core idea driving this characterization comes from using a quantum (mixed) state testing perspective, which is different from what previous work has focused on, which was mostly about time-bounded scenarios.

Lev: That’s important because state testing often involves measurements and noise models, so linking it to the preparation complexity gives us a clearer picture of the computational cost involved in verification.

The paper's improvements: Kai: They introduce a main technique called a space-efficient variant of the quantum singular value transformation or QSVT, which they say provides a unified approach for designing space-bounded quantum algorithms.

Mira: What’s key here is that implementing this QSVT for any polynomial that approximates a piecewise-smooth function only costs a constant overhead in terms of the space needed for those special forms of projected unitary encoding.

Lev: Constant overhead in space is fantastic news if it means we can actually fit these verification algorithms onto real hardware with limited qubits without needing exponentially more memory just to run the transformation step.

Kai: It’s different from prior work because they focused on space efficiency rather than time efficiency, which is where most of the QSVT research has been concentrated recently.

Mira: They establish two things here: BQL containment for space-bounded state testing with respect to the squared Hilbert–Schmidt distance, and coRQL-hardness for state certification.

Lev: So they’ve mapped out a landscape, showing which problems are easier or harder under these new metrics, which helps us know exactly where the computational bottlenecks lie.

Conclusion: Kai: To wrap up, the paper "Space-bounded quantum state testing via space-efficient quantum singular value transformation" shows that testing these space-bounded states is computationally as easy as preparing them in a space-bounded manner.

Mira: They achieve this by using a technique called the space-efficient quantum singular value transformation, which allows for polynomial approximations of functions with only constant extra space overhead.

Lev: For us building hardware, this means we have a pathway to design verification routines that don't require massive auxiliary memory just to perform the necessary transformations.

Kai: It also implies that a certain type of space-bounded quantum statistical zero-knowledge is contained within BQL, which is an interesting implication for privacy in quantum computation.

Mira: The work points toward a more natural set of complete problems, driven by testing properties rather than just standard algebraic ones, which should guide future research into characterizing these resource-restricted models.

Lev: It gives us a clearer idea of the computational cost associated with verifying quantum states under strict space constraints when we move from theory to actual implementation.

François Le Gall, Yupan Liu, Qisheng Wang

Graduate School of Mathematics, Nagoya University · School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne · School of Computer Science, Shanghai Jiao Tong University

quant-ph, cs.CC

Submitted: 2023-08-09

Updated: 2026-07-01

Comments: 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

Journal ref: computational complexity, Volume 35, Article 14, 2026

DOI: 10.1007/s00037-026-00284-5

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 98/100

The gist: Driven by exploring the power of quantum computation with a limited number of qubits, this paper presents a novel complete characterization for space-bounded quantum computation…

Key concepts

Space-bounded Quantum Computation
This refers to running a quantum algorithm where the amount of memory (qubits) used is strictly limited by a polynomial in the input size, rather than being unlimited. The paper focuses on problems solvable within these strict space constraints.
Quantum Singular Value Transformation (QSVT)
QSVT is a technique used to design space-efficient quantum algorithms. It provides a unified method for approximating functions using singular values, and this specific variant is optimized for space efficiency, minimizing the memory needed for encoding the unitary operations.
BQL/coRQL
These terms describe different types of error models in quantum computation. BQL (two-sided error) and coRQL (one-sided error) define the complexity class boundaries for quantum problems, showing how hard or easy certain state certification and testing tasks are.
Hilbert–Schmidt Distance
This is a specific mathematical measure used to quantify the distance between two quantum states. The paper uses this distance, along with trace distance and entropy difference, to define the natural complete problems for space-bounded quantum state testing.

Terminology

Summary

Driven by exploring the power of quantum computation with a limited number of qubits, this paper presents a novel complete characterization for space-bounded quantum computation, encompassing settings with one-sided error (unitary coRQL) and two-sided error (BQL), approached from a quantum (mixed) state testing perspective. p. 0

Where the paper says it

Space-bounded quantum state testing via space-efficient quantum singular value transformation François Le Gall∗1 , Yupan Liu†2,1, and Qisheng Wang‡3,1 1Graduate School of Mathematics, Nagoya University 2School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne 3School of Computer Science, Shanghai Jiao Tong University 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 (mixed) state testing perspective: • The first family of natural complete problems for unitary coRQL, namely space-bounded quantum state certification for trace distance and Hilbert–Schmidt distance; • A new family of (arguably simpler) natural complete problems for BQL, namely spacebounded 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 Q0 and Q1, which prepare quantum states ρ0 and ρ1, respectively, with access to their “source code”.

The first family of natural complete problems for unitary coRQL are space-bounded quantum state certification for trace distance and Hilbert–Schmidt distance. p. 0
Where the paper says it

Space-bounded quantum state testing via space-efficient quantum singular value transformation François Le Gall∗1 , Yupan Liu†2,1, and Qisheng Wang‡3,1 1Graduate School of Mathematics, Nagoya University 2School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne 3School of Computer Science, Shanghai Jiao Tong University 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 (mixed) state testing perspective: • The first family of natural complete problems for unitary coRQL, namely space-bounded quantum state certification for trace distance and Hilbert–Schmidt distance; • A new family of (arguably simpler) natural complete problems for BQL, namely spacebounded 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 Q0 and Q1, which prepare quantum states ρ0 and ρ1, respectively, with access to their “source code”.

A new family of natural BQL-complete problems are spacebounded quantum state testing for trace distance, Hilbert–Schmidt distance, and (von Neumann) entropy difference. p. 0
Where the paper says it

Space-bounded quantum state testing via space-efficient quantum singular value transformation François Le Gall∗1 , Yupan Liu†2,1, and Qisheng Wang‡3,1 1Graduate School of Mathematics, Nagoya University 2School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne 3School of Computer Science, Shanghai Jiao Tong University 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 (mixed) state testing perspective: • The first family of natural complete problems for unitary coRQL, namely space-bounded quantum state certification for trace distance and Hilbert–Schmidt distance; • A new family of (arguably simpler) natural complete problems for BQL, namely spacebounded 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 Q0 and Q1, which prepare quantum states ρ0 and ρ1, respectively, with access to their “source code”.

The results reveal that the space-bounded state testing problems, considering all three measures, are computationally as easy as preparing quantum states. p. 0
Where the paper says it

Our goal is to decide whether ρ0 is ϵ1-close to or ϵ2-far from ρ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 (either QSZK-complete or BQP-complete), our results reveal that the space-bounded state testing problems, considering all three measures, are computationally as easy as preparing quantum states.

The main technique is a space-efficient variant of the quantum singular value transformation (QSVT). p. 2

Where the paper says it

Consequently, we can introduce the first family of natural coRQUL-complete promise problems since Watrous [Wat01] introduced unitary RQL and coRQL (known as RQUL and coRQUL, respectively) in 2001, as well as a new family of natural BQL-complete promise problems. Our main technique is a space-efficient variant of the quantum singular value transformation (QSVT) [GSLW19], distinguishing itself from prior works primarily focused on time-efficient QSVT.

This technique provides a unified approach for designing space-bounded quantum algorithms and shows 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. p. 0
Where the paper says it

Our technique provides a unified approach for designing spacebounded 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.

The QSVT technique is distinguished from prior works primarily focused on time-efficient QSVT, focusing instead on space efficiency. p. 2
Where the paper says it

Consequently, we can introduce the first family of natural coRQUL-complete promise problems since Watrous [Wat01] introduced unitary RQL and coRQL (known as RQUL and coRQUL, respectively) in 2001, as well as a new family of natural BQL-complete promise problems. Our main technique is a space-efficient variant of the quantum singular value transformation (QSVT) [GSLW19], distinguishing itself from prior works primarily focused on time-efficient QSVT.

The paper establishes BQL containment for space-bounded state testing with respect to the squared Hilbert–Schmidt distance, as well as coRQUL-hardness for state certification. p. 8

Where the paper says it

Furthermore, establishing BQL hardness, as well as coRQUL-hardness for state certification, is not challenging (see Lemma 4. Regarding space-bounded state testing with respect to the trace distance (ℓ1 norm), we note that [Wat02, Proposition 21] implicitly established an NC containment.

It also derives BQL-hardness for space-bounded state testing with respect to the quantum Jensen–Shannon divergence and the quantum entropy difference. p. 8
Where the paper says it

The BQL-hardness, as well as coRQUL-hardness for state certification, is adapted from [RASW23]. Similarly, we derive the BQL-hardness for space-bounded state testing with respect to the quantum Jensen-Shannon divergence and the quantum entropy difference, building on the previous work [Liu25b].

The framework reduces quantum state testing problems to estimating Tr(P d'(rho')), where P d' is a space-efficiently computable degree- d' polynomial obtained from some degree- d averaged Chebyshev truncation with d' = 2d - 1.

The space-efficient QSVT technique allows for the implementation of the quantum singular value transformation P(SV) d'(A) using O(s(n)) qubits and O(d 2 eta V) queries to U, where eta V is related to the norm of the coefficient vector c hat. This leads to BQL containment for state testing problems. p. 8

Where the paper says it

, coRQUL) containment for state testing (resp. , certification) problems for other distance-like measures beyond the squared Hilbert–Schmidt distance.

The construction of the final polynomial approximation P'd' is achieved by combining space-efficient polynomial approximations for continuously bounded functions (using averaged Chebyshev truncation) and piecewise-smooth functions (using a randomized algorithm based on Fourier series), ensuring error bounds that are independent of d.

The results imply that a space-bounded variant of quantum statistical zero-knowledge is contained in BQL (and indeed satisfies QSZKUL = BQL). p. 6

Where the paper says it

In particular, the promise problem (α, β)-SD asks whether D0 is α-far from or β-close to D1 with respect to ∥D0 − D1∥TV. Although sampling from the distribution is in BPP, 3 testing the closeness between these distributions is SZK-complete [SV03, GSV98], where SZK is the class of promise problems possessing statistical zero-knowledge proofs.

The discussion also touches upon open problems regarding the efficiency and applicability of QSVT for other distance-like measures. p. 0
Where the paper says it

Interestingly, unlike time-bounded state testing problems, which exhibit computational hardness depending on the chosen distance-like measure (either QSZK-complete or BQP-complete), 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.

Relevant excerpts include: Our main result conveys a conceptual message that testing quantum states prepared in bounded space is (computationally) as easy as preparing these states in a space-bounded manner, and The main technique is a space-efficient variant of the quantum singular value transformation (QSVT) [GSLW19], distinguishing itself from prior works primarily focused on time-efficient QSVT.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Space-efficient quantum singular value transformation allows for designing space-bounded quantum algorithms by incurring only a constant overhead in terms of space required for special forms of projected unitary encoding, enabling a unified approach to designing such algorithms.

  2. AI systems can perform space-bounded quantum state certification and testing with one-sided error (unitary coRQL) and two-sided error (BQL) efficiently, characterized by natural complete problems like CertQSDlog and GapQHSlog.

  3. The framework enables the identification of BQL-complete promise problems for space-bounded quantum state testing, such as GapQSDlog, which are computationally as easy as preparing quantum states in a logspace manner.

  4. AI systems can utilize randomized polynomial approximations derived from averaged Chebyshev truncation to construct space-efficient bounded polynomial approximations for piecewise-smooth functions with bounded error.

  5. The method allows for the construction of a bitstring indexed encoding of the quantum singular value transformation with a size related to s plus a plus log d plus O(1) qubits, where d is the degree of the polynomial approximation.

  6. AI systems can implement space-efficient QSVT using O(d squared eta V) uses of U, U dagger, CNOT gates for general linear operators acting on s qubits with a bitstring indexed encoding V.

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, namely space-bounded quantum state certification for trace distance and Hilbert-Schmidt distance; - A new family of natural complete problems for 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 ρ 0 and ρ 1, respectively, with access to their ``source code''. Our goal is to decide whether ρ 0 is ε 1-close to or ε 2-far from ρ 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.

Sources

Related papers