Space-bounded quantum state testing via space-efficient quantum singular value transformation
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 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”. 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”. 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”. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The main technique is a space-efficient variant of the quantum singular value transformation (QSVT). p. 2 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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].Where the paper says it
Where the paper says it
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 , coRQUL) containment for state testing (resp. , certification)
problems for other distance-like measures beyond the squared Hilbert–Schmidt distance.Where the paper says it
The results imply that a space-bounded variant of quantum statistical zero-knowledge is contained in BQL (and indeed satisfies QSZKUL = BQL). p. 6 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. 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.Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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.
-
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.
-
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
- Estimating Entropy of Distributions in Constant Space
- Measuring Quantum Entropy
- A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
- Quantum Circuits with Mixed States
- Estimation of Entropy in Constant Space with Improved Sample Complexity
- Quantum SDP-Solvers: Better upper and lower bounds
- Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
- Tight bounds on quantum searching
- Simulating Hamiltonian dynamics with a truncated Taylor series
- On the Power of Statistical Zero Knowledge
- Quantum fingerprinting
- Properties of Classical and Quantum Jensen-Shannon Divergence
- Quantum Amplitude Amplification and Estimation
- Quantum state certification
- Finding Angles for Quantum Signal Processing with Machine Precision
- Optimal Algorithms for Testing Closeness of Discrete Distributions
- A Variational Quantum Algorithm for Preparing Quantum Gibbs States
- Communication and Memory Efficient Testing of Discrete Distributions
- Efficient phase-factor evaluation in quantum signal processing
- Space-Efficient Error Reduction for Unitary Quantum Computations
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements