Source-linked AI summary
Quantum state certification
Costin Bădescu, Ryan O'Donnell, John Wright
TL;DR
Quantum state certification tests whether an unknown state matches a target or is far from it, rather than estimating the entire state. The paper gives robust certification algorithms with copy bounds for fidelity and trace-distance testing. Its trace-distance guarantee also covers two unknown states.
Problem
Certification asks whether an unknown mixed state equals a target or is ε-far, while full tomography can require Ω(d²) copies.
Source: §1 · pp. 1–2Method
The paper uses measurement-based tests that report “close” or “far” under robust distance thresholds.
Source: §1.1 · p. 2Results
O(d/ε) copies suffice for fidelity certification against fixed σ, while O(d/ε²) copies of each suffice for trace-distance testing of two unknown states.
Source: §1.1 · pp. 2–3Takeaways & Limitations
The tests address certification directly, without requiring estimation of the entire unknown state.
Source: §1 · p. 2The estimator framework’s stated input family consists of product states ρ₁ ⊗ ··· ⊗ ρₙ, including identical-copy states ρ^⊗n.
Source: §4 · p. 14, §4.0.1 · p. 16
Abstract
from arXiv · showhide
We consider the problem of quantum state certification, where one is given $n$ copies of an unknown $d$-dimensional quantum mixed state $\rho$, and one wants to test whether $\rho$ is equal to some known mixed state $\sigma$ or else is $\epsilon$-far from $\sigma$. The goal is to use notably fewer copies than the $\Omega(d^2)$ needed for full tomography on $\rho$ (i.e., density estimation). We give two robust state certification algorithms: one with respect to fidelity using $n = O(d/\epsilon)$ copies, and one with respect to trace distance using $n = O(d/\epsilon^2)$ copies. The latter algorithm also applies when $\sigma$ is unknown as well. These copy complexities are optimal up to constant factors.
1 Introduction
Quantum state certification asks whether an unknown output state matches a target or is far from it, avoiding the full state estimation that can require quadratic scaling in dimension. The paper develops a framework for estimating polynomial functions of quantum states and gives robust certification results for fixed and unknown targets.
1.1 Our results
- The paper’s framework analyzes the number of copies needed to estimate polynomial functions of unknown quantum states for certification tasks.Source: §1.1 · p. 2
- With O(d/ε) copies, a measurement robustly certifies a fixed target: “close” guarantees F(ρ, σ) ≥ 1 − ε, while “far” guarantees Dχ2(ρ ∥ σ) > .49ε.The paper also gives the simpler test distinguishing ρ = σ from F(ρ, σ) < 1 − ε with high probability.Source: §1.1 · p. 2
- For targets with smallest eigenvalue at least cε²/d, O(d/ε²) copies distinguish Dχ2(ρ ∥ σ) ≤ .99ε² from Dχ2(ρ ∥ σ) > ε²..Source: §1.1 · p. 2
- For two unknown states, O(1/ε²) copies of each distinguish Hilbert–Schmidt distance at most .99ε from distance greater than ε.Source: §1.1 · p. 2
- For two unknown mixed states, O(d/ε²) copies of each distinguish equality from trace distance greater than ε.Source: §1.1 · p. 3
- If one unknown state has at least 1 − δ of its eigenvalue mass among its largest k eigenvalues, the trace-distance test uses O(k/ε²) copies per state.It distinguishes DHS(ρ, σ) ≤ .58ε from Dtr(ρ, σ) > δ + ε.Source: §1.1 · p. 3
- The simplest fidelity and trace-distance results have optimal sample complexity up to constants, even when the target is maximally mixed.The cited lower bound requires more than .15d/ε² copies for its specified maximally-mixed-state testing promise.Source: §1.1 · p. 3
1.2 Outline of the remainder of the paper
- The paper reviews prior work, develops quantum-probability and representation-theory background, presents estimators and certification proofs, and gives efficient implementations.Source: §1.2 · p. 3
2 Prior work on classical and quantum density testing/estimation
The section surveys quantum and classical density estimation and testing, distinguishing full-state estimation from testing and finite-copy guarantees from asymptotic error-rate results.
2.1.1 Tomography (density estimation)
- General tomography estimates an unknown density matrix, with best-known copy bounds depending on rank and distance; general cases require eΘ(d^2) copies.The section motivates restricted testing tasks as potentially achievable with O(d) or fewer copies.Source: §2.1.2 · p. 4, §2.1.1 · p. 4
2.1.2 Density testing
- Quantum state certification is a property-testing task: distinguish a target state from states in a disjoint far class using few copies.For a fixed target σ, the classes are {σ} and states whose distance from σ exceeds ε.Source: §2.1.2 · p. 4
- For pure known σ, certification uses O(1/ε) copies for infidelity; for maximally mixed σ, trace-distance certification requires Θ(d/ε^2) copies.The maximally mixed-state upper bound estimates purity; the cited work also establishes a matching lower bound.Source: §2.1.2 · p. 4
2.1.3 The asymptotic regime for state discrimination
- In the non-asymptotic regime, state discrimination seeks a concrete copy bound for fixed error; asymptotic hypothesis testing instead studies exponential error rates as n grows.Asymptotic rate results do not by themselves specify when their error bounds become effective.Source: §2.1.3 · p. 5
2.2 Prior classical density estimation, testing, and certification
- Classical quantum problems have a special case when density matrices are diagonal, yielding estimation, certification, and identity testing for probability distributions.The section reviews prior work on these classical analogues.Source: §2.2 · p. 5
2.2.1 Density estimation
- For classical density estimation, O(d) samples suffice for natural distances at constant ε, so distribution certification seeks to use o(d) samples.The passage names total variation, Hellinger, and χ2 divergence among those distances.Source: §2.2.1 · p. 6
2.2.2 Identity testing
- Under q_i ≥ Ω(ε²/d) for all i, their robust tester distinguishes χ²(p ∥ q) ≤ ε²/10 from total variation distance d_TV(p, q) > ε.Source: §2.2.2 · p. 6
- Classical testing of two unknown distributions has optimal sample complexity for Hellinger distance; the analogous two-unknown-state quantum identity test remains open.The open quantum question asks for O(d/ε) samples to distinguish ρ = σ from F(ρ, σ) < 1 − ε.Source: §2.2.2 · p. 7
3 Preliminaries
The preliminaries define classical and quantum distances and introduce probability, operator, and representation-theoretic tools for the certification algorithms. They also establish that the operators Oκ form a basis for the real vector space of self-adjoint elements of Z(CSₙ).
3.1.1 Distances and divergences for classical probability distributions
- Total variation distance measures optimal classical discrimination, while squared Hellinger distance is bounded by total variation and by χ²-divergence; these f-divergences obey data processing.The section also notes that χ²-divergence is asymmetric but can be easier to compute when q is fixed.Source: §3.1.1 · pp. 8–9
3.1.2 Distances and divergences for quantum mixed states
- Quantum distances are unitary invariant, and measured quantum f-divergences maximize the corresponding classical divergence over a shared POVM; trace distance captures optimal state discrimination and contracts under quantum channels.For full-rank σ, the Bures χ²-divergence is a measured version of classical χ² and satisfies D²_B(ρ, σ) ≤ S(ρ ∥ σ) ≤ D_χ²(ρ ∥ σ).Source: §3.1.2 · pp. 9–11
3.2 Quantum probability
- Mean-preserving positive unital maps do not increase observable variance, supporting low-variance measurements in the certification analysis.The section defines state expectations by E_ρ[X] = tr(ρX) and notes that the algorithms measure observables and apply Chebyshev’s inequality.Source: §3.2 · pp. 11–13
3.3 Representation theory
- Partitions of n index conjugacy classes of S_n, whose normalized class indicators form a basis for the center of the symmetric group algebra.The section also defines the permutation action of S_n on (C^d)^⊗n.Source: §3.3 · pp. 13–14
- {Oκ | κ ⊢ n} is a basis for the real vector space of self-adjoint elements of Z(CSn).This follows from O†κ = Oκ for all κ ⊢ n; see [GW09, Proposition 4.3.7] for a proof.Source: §3.3 · p. 14
4 Efficient quantum estimators
The section develops a framework for finding minimum-variance unbiased quantum estimators, reducing unitarily invariant estimation problems to structured elements of the symmetric-group algebra. For identical copies, the efficient estimator is unique when it lies in the center; for two states, the framework yields efficient overlap and squared-distance estimators.
4 Efficient quantum estimators
- The framework defines an efficient estimator as an unbiased observable whose variance is no greater than that of any other estimator for the statistic.The state set S specifies the class of quantum states considered in the estimation problem.Source: §4 · p. 14
- For any unitarily invariant statistic, averaging an estimator over unitaries preserves its expectation and does not increase its variance.The resulting estimator lies in the image of Φ, a projection into P(CS_n).Source: §4 · p. 15
- Efficient estimators can be restricted to P(X) with X in the symmetric-group algebra and invariant under the permutation-invariant group Γ.Such X are constant on Γ-orbits, so they can be expressed as linear combinations of orbit indicators.Source: §4 · p. 16
4.0.1 Case:= ρ⊗n
- For n identical copies ρ⊗n, where ρ has spectrum α, each permutation π ∈ S_n of cycle type κ satisfies E_ρ[π] = p_κ(α), so its expectation depends only on κ.Source: §4.0.1 · p. 16
- For identical copies ρ⊗n, every central estimator is efficient, and any two central estimators for the same statistic are equal.In particular, O_(k) efficiently estimates tr(ρ^k).Source: §4.0.1 · p. 17
4.0.2 Case:= ρ⊗m ⊗σ⊗n
- For inputs ρ⊗m ⊗σ⊗n, the efficient estimator of tr(ρσ) is O_(ρ σ), while that of D²_HS(ρ,σ) is O_(ρ ρ)+O_(σ σ)−2O_(ρ σ).The stated estimator forms are supported by the corresponding corollaries.Source: §4.0.2 · pp. 18–19
5 Hilbert–Schmidt distance and related estimation
The section develops estimators based on purity, overlap, and squared Hilbert–Schmidt distance, then applies them to certification. Its testing consequence distinguishes two unknown states using O(1/ε²) copies of each.
5.1 Purity, and testing identity to the maximally mixed state
- For testing identity to the maximally mixed state, O(1/ε²) copies distinguish D_HS(ρ,1/d)≤.99ε from D_HS(ρ,1/d)>ε.The test uses purity, since D²_HS(ρ,1/d)=tr(ρ²)−1/d.Source: §5.1 · p. 19
5.2 Linear fidelity
- O_(ρσ) is an efficient estimator of the linear fidelity tr(ρσ) for copies of both states.The passage identifies tr(ρσ) as the overlap or linear fidelity.Source: §5.2 · p. 20
5.3 Squared Hilbert–Schmidt distance
- The efficient estimator of squared Hilbert–Schmidt distance is O_(ρρ)+O_(σσ)−2O_(ρσ), and the self-purity estimators have zero covariance.The variance calculation is used in the testing consequence for two unknown states.Source: §5.3 · p. 20, §5.4 · p. 21
5.4 Consequences for testing
- O(1/ε²) copies of each unknown state suffice to distinguish D_HS(ρ,σ)≤.99ε from D_HS(ρ,σ)>ε.The theorem follows from the squared Hilbert–Schmidt estimator's variance analysis.Source: §5.3 · p. 20, §5.4 · p. 21
6 Quantum chi-squared estimation
The section constructs an averaged χ² observable whose expectation estimates the Bures χ²-divergence and analyzes its variance. The resulting tester handles a fixed reference state without an eigenvalue lower-bound assumption, while the variance analysis for the underlying estimator assumes eigenvalues are bounded below.
6.1 A chi-squared observable
- For diagonal σ, the associated χ² observable acts on two copies, and its expectation is Dχ²(ρ∥σ)+1.The averaged observable subtracts 1 to give an unbiased estimate of the divergence.Source: §6.1 · pp. 23–24
- The averaged χ² observable is unbiased for Dχ²(ρ∥σ), and its variance equals that of the average of the pairwise Xσ observables.The construction averages over distinct ordered pairs of copies.Source: §6.1 · p. 24
6.2 Analyzing the variance of the average chi-squared observable
- The variance analysis and resulting sample bound require the smallest eigenvalue of σ to be at least δ.The section's variance bounds are stated under this eigenvalue condition.Source: §6.2 · p. 26, §6.3 · p. 26
6.3 Consequences for testing
- O(d/ε) copies suffice to output close when Dχ²(ρ∥σ)≤.49ε or far when squared Bures distance exceeds .5ε, for fixed σ without an eigenvalue assumption.The construction depolarizes the states before applying the well-conditioned tester.Source: §6.3 · pp. 26–27
- With O(d/ε) copies, one can distinguish a state diagonal in the standard basis from one whose infidelity to every diagonal state exceeds ε.The procedure estimates the diagonal distribution and then applies the fixed-state tester.Source: §6.3 · p. 27
7 Implementing the observables
The section gives efficient implementations of the purity and Hilbert–Schmidt observables, using Schur–Weyl duality and tableau-based measurements. An alternative Hilbert–Schmidt observable avoids preparing copies of the known reference state and has matching variance to the standard observable.
7.1 Implementing the purity observable
- The purity observable O(2) can be computed in time poly(n,d) using weak Schur sampling and the character ratio T_N(λ).The sampled partition λ determines the statistic output by the measurement.Source: §7.1 · p. 28
7.2 Implementing the Hilbert–Schmidt observable
- For equal copy counts of ρ and σ, the Hilbert–Schmidt observable can be computed in time poly(n,d) using weak Schur sampling on each state.The implementation measures the two sampled partitions and evaluates the observable from them.Source: §7.2 · pp. 29–30
7.3 An alternative Hilbert–Schmidt observable
- The alternative Hilbert–Schmidt observable avoids preparing copies of known σ and has variance matching the standard observable.It remains an unbiased estimator of squared Hilbert–Schmidt distance and yields the known-σ test with O(1/ε²) copies of ρ.Source: §7.3 · p. 30
- The alternative observable is measured using the Gelfand–Tsetlin basis or successive weak Schur sampling and type measurement, in time poly(n,d).The Schur transform implements the basis change in polynomial time.Source: §7.3 · p. 31