Recent advancements in quantum devices have posed an intriguing challenge of verifying their intended functionality.These devices, typically time-bounded, are often designed to prepare specific 𝑛-qubit states, denoted as 𝜌 ! and 𝜌 " .The problem of (tolerant) quantum state testing aims to design algorithms that can efficiently decide whether 𝜌 ! is either 𝜀 " -close to or 𝜀 # -far from 𝜌 " with respect to a chosen distance-like measure.This problem generalizes classical distribution testing to the quantum domain and forms a part of quantum property testing, an emerging field dedicated to developing efficient quantum testers for properties of quantum objects.The computational complexity of time-bounded state testing varies significantly with the choice of closeness measure, exhibiting a dichotomy-like behavior:• For both the trace distance (ℓ " norm) and the quantum (von Neumann) entropy difference, the problems correspond to the complexity class QSZK, as shown in Watrous (FOCS 2002), Watrous (SICOMP 2009), and Ben-Aroya, Schwartz, and Ta-Shma (CCC 2008), which is widely believed to be strictly more powerful than BQP.
Recent advancements in quantum devices have posed an intriguing challenge of verifying their intended functionality.These devices, typically time-bounded, are often designed to prepare specific 𝑛-qubit states, denoted as 𝜌 ! and 𝜌 " .The problem of (tolerant) quantum state testing aims to design algorithms that can efficiently decide whether 𝜌 ! is either 𝜀 " -close to or 𝜀 # -far from 𝜌 " with respect to a chosen distance-like measure.This problem generalizes classical distribution testing to the quantum domain and forms a part of quantum property testing, an emerging field dedicated to developing efficient quantum testers for properties of quantum objects.The computational complexity of time-bounded state testing varies significantly with the choice of closeness measure, exhibiting a dichotomy-like behavior:• For both the trace distance (ℓ " norm) and the quantum (von Neumann) entropy difference, the problems correspond to the complexity class QSZK, as shown in Watrous (FOCS 2002), Watrous (SICOMP 2009), and Ben-Aroya, Schwartz, and Ta-Shma (CCC 2008), which is widely believed to be strictly more powerful than BQP.
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form Lφ(ρ)=tr(φ(dρ))/d, where ρ is an unknown d-dimensional quantum state and φ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating Lφ(ρ) from properties of φ, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting.
The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is Θ(εlog2(d)max{1,εlog2(d)}d2+ε2log2(d)), and the sample complexity of spectrum estimation is Θ(ε2log2(d)max{1,ε2log2(d)}d2). In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
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 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, 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.
We study the problem of property testing quantum states: given a pure state ∣ψ⟩ that either (A) belongs to some class C of pure states, or (B) is ε-far in trace distance from all states in C, determine which is the case with high probability. It is known that there exists classes C for which the sample complexity of property testing necessarily scales with the size of the system. In this work, we identify classes for which testing only requires a size-independent number of samples. We prove a tight sample complexity of Θ(1/ε2) for the property testing of five important classes of Gaussian quantum states: 1) Fermionic Gaussian states, 2) Slater determinants, 3) bosonic Gaussian states, 4) zero-mean bosonic Gaussian states, and 5) bosonic coherent states.
While property testers for some of these classes have been studied previously, those analyses only gave upper bounds scaling polynomially in the number of modes. In each case, our tester is the projection onto the ``top'' irrep of two or three copies. We get to constant sample complexity by lower bounding how quickly the rejection probability increases with distance from the class; the main technical component involves bounding the spectral gap of symmetric extension of the test projector. We then establish optimality by proving matching lower bounds based on binary state discrimination for each class. Our testers and optimality claims also extend to the tolerant setting, wherein ψ may be O(ε)-close to C in case (A), rather than lying exactly inside.
Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including:
1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity tr(ρ2) and the inner product tr(ρσ).
2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals tr(ρk).
3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal.
4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state.
5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states.
6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal.
To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.
Abstract The complexity class Quantum Statistical Zero-Knowledge captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, deciding whether T(ρ0,ρ1) T ( ρ 0 , ρ 1 ) is at least α α or at most β β , known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However, QSDP[α,β] QSDP [ α , β ] is in only within the constant polarizing regime, where αandβ α and β are constants satisfying α2>β α 2 > β (rather than α>β α > β ), similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due to the polarization lemma (error reduction for SDP). Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the containment of SDP beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. Our work introduces proper quantum analogs for these problems by defining quantum counterparts for triangular discrimination. We investigate whether the quantum analogs behave similarly to their classical counterparts and examine the limitations of existing approaches to polarization regarding quantum distances. These new -complete problems improve containments of QSDP beyond the polarizing regime and establish a simple -hardness for the quantum entropy difference problem (QEDP) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that QSDP with some exponentially small errors is in , while the same problem without error is in .
We explore potential quantum speedups for the fundamental problem of testing the properties of closeness andk-wise uniformity of probability distributions. •Closeness testingis the problem of distinguishing whether twon-dimensional distributions are identical or at least ε-far in ℓ1- or ℓ2-distance. We show that the quantum query complexities for ℓ1- and ℓ2-closeness testing areO(√n/ε) andO(1/ε), respectively, both of which achieve optimal dependence on ε, improving the prior best results of Gilyén and Li (2019). •k-wise uniformity testingis the problem of distinguishing whether a distribution over {0, 1}nis uniform when restricted to anykcoordinates or ε-far from any such distribution. We propose the first quantum algorithm for this problem with query complexityO(√nk/ε), achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexityO(nk/ε2) by O’Donnell and Zhao (2018). Moreover, whenk= 2 our quantum algorithm outperforms any classical one because of the classical lower bound Ω(n/ε2). All our quantum algorithms are fairly simple and time-efficient, using only basic quantum subroutines such as amplitude estimation.