How many copies of a mixed state \(\rho \in \mathbb{C}^{d \times d}\) are needed to learn its spectrum? To date, the best known algorithms for spectrum estimation require as many copies as full state tomography, suggesting the possibility that learning a state's spectrum might be as difficult as learning the entire state. We show that this is not the case in the setting of unentangled measurements, by giving a spectrum estimation algorithm that uses \(n = O\left(d^{3} \cdot (\log \log(d) / \log(d))^{4}\right)\) copies of \(\rho\), which is asymptotically fewer than the \(n = \Omega(d^{3})\) copies necessary for full state tomography. Our algorithm is inspired by the technique of local moment matching from classical statistics, and shows how it can be applied in the quantum setting.
How many copies of a mixed state (\rho \in \mathbb{C}^{d \times d}) are needed to learn its spectrum? To date, the best known algorithms for spectrum estimation require as many copies as full state tomography, suggesting the possibility that learning a state's spectrum might be as difficult as learning the entire state. We show that this is not the case in the setting of unentangled measurements, by giving a spectrum estimation algorithm that uses (n = O\left(d^{3} \cdot (\log \log(d) / \log(d))^{4}\right)) copies of (\rho), which is asymptotically fewer than the (n = \Omega(d^{3})) copies necessary for full state tomography. Our algorithm is inspired by the technique of local moment matching from classical statistics, and shows how it can be applied in the quantum setting.
There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.
In the quantum state tomography problem, one wishes to estimate an unknown d-dimensional mixed quantum state ρ, given few copies. We show that O(d/ε) copies suffice to obtain an estimate ρ that satisfies ||ρ − ρ||F2 ≤ ε (with high probability). An immediate consequence is that O((ρ) · d/ε2) ≤ O(d2/ε2) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O(d3/ε2) copies for full tomography, and even on the best known prior result of O(d2log(d/ε)/ε2) copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension.
We give an algorithm which, given n=O(d2⋅(loglog(d)/log(d))2) copies of ρ, estimates the eigenvalues of ρ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the Θ(d2) needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses n=Θ(d2) copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright.
Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction ∣w⟩ scales with ⟨w∣ρ∣w⟩ for all directions simultaneously. From this stronger "relative-error" bound, we recover better algorithms for principal component analysis in Bures distance and tomography in χ2-divergence as corollaries.
We prove that the spectrum of an unknown d-dimensional quantum state can be estimated to error ε in total variation distance using O(d2min{(εlogd)41,(εlogd)21}) copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of d in copy complexity, which we conjecture to be optimal.
We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound.
In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given n copies of a mixed state ρ∈Cd×d and the goal is to distinguish whether ρ's spectrum satisfies some property P or is at least ε-far in ℓ1-distance from satisfying P. This problem was promoted in the survey of Montanaro and de Wolf under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions. Here, the hope is for algorithms with subquadratic copy complexity in the dimension d. This is because the "empirical Young diagram (EYD) algorithm" can estimate the spectrum of a mixed state up to ε-accuracy using only O(d2/ε2) copies. In this work, we show that given a mixed state ρ∈Cd×d: (i) Θ(d/ε2) copies are necessary and sufficient to test whether ρ is the maximally mixed state, i.e., has spectrum (d1,...,d1); (ii) Θ(r2/ε) copies are necessary and sufficient to test with one-sided error whether ρ has rank r, i.e., has at most r nonzero eigenvalues; (iii) Θ(r2/Δ) copies are necessary and sufficient to distinguish whether ρ is maximally mixed on an r-dimensional or an (r+Δ)-dimensional subspace; and (iv) The EYD algorithm requires Ω(d2/ε2) copies to estimate the spectrum of ρ up to ε-accuracy, nearly matching the known upper bound. In addition, we simplify part of the proof of the upper bound. Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov's algebra of polynomial functions on Young diagrams.
Optimal single-copy estimation of quantum state moments: why Tr(ρ3) and Tr(ρ4) are equally hard
Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments Tr(ρt), allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity Θ(d) at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer t≥2: for any sufficiently small constant additive error, the optimal sample complexity is Θ(d1+⌈log2t⌉⌈log2t⌉) with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer h≥1, all moment orders 2h−1<t≤2h share the same exponent. In particular, the third and fourth moments both require Θ(d2/3) copies. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. We also establish an Ω(d1−1/t) lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every t≥4. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond d.