computational complexity · 10 Nov 2026
Space-bounded quantum state testing via space-efficient quantum singular value transformation
François Le Gall, Yupan Liu, Qisheng Wang
Citations by database
Each database indexes a different set of journals, preprints and books, so they are shown side by side rather than blended.
- OpenCitations0
- Crossref0
Citations per year
The current year is still counting.
- 2026 so far0
Abstract
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 ) and two-sided error ( ), approached from a quantum (mixed) state testing perspective: The first family of natural complete problems for unitary $$\text {\textsf {coRQL}} $$ coRQL , namely space-bounded quantum state certification for trace distance and Hilbert–Schmidt distance; A new family of (arguably simpler) natural complete problems for , 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$$ Q 0 and $$Q_1$$ Q 1 , which prepare quantum states $$\rho _0$$ ρ 0 and $$\rho _1$$ ρ 1 , respectively, with access to their “source code”. Our goal is to decide whether $$\rho _0$$ ρ 0 is $$\epsilon _1$$ ϵ 1 -close to or $$\epsilon _2$$ ϵ 2 -far from $$\rho _1$$ ρ 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 -complete or -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. 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.
What the data shows
- No database records a citation yet, as is usual for a paper this new.
Graph
This paper in the middle, its authors and their most-cited papers below, the papers it cites to the left and the papers citing it to the right. The timeline lays every paper out by year.
Select a node for its details. Drag to pan, scroll to zoom, drag a node to move it.
Start with
Cited by 0 papers
Who cites this paper, from open citation data, with Crossref's record of each; the 100 newest when there are more.
References (78)
What it cites, from open citation data, with Crossref's record of each.
Sign in to see 58 more references
A free account opens the rest of the citing papers and references on every paper’s page.