We give an algorithm which, given $n = O(d^2 \cdot (\log\log(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 $Θ(d^2)$ needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses $n = Θ(d^2)$ 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\rangle$ scales with $\langle w | ρ|w\rangle$ 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 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 the problem of quantum state tomography, one is given n copies of an unknown rank-r mixed state ρ ∈ ℂd × d and asked to produce an estimator of ρ. In this work, we present the debiased Keyl’s algorithm, the first estimator for full state tomography which is both unbiased and sample-optimal. We derive an explicit formula for the second moment of our estimator, with which we show the following five applications. First, we give a new proof that n = O(rd/ε2) copies are sufficient to learn a rank-r mixed state to trace distance error ε, which is optimal. Second, we show that n = O(rd/ε2) copies are sufficient to learn to error ε in the more challenging Bures distance, which is also optimal. Third, we consider full state tomography when one is only allowed to measure k copies at once. We show that n =O(max(d3/√kε2, d2/ε2 ) ) copies suffice to learn in trace distance. This improves on the prior work of Chen et al. and matches their lower bound. Fourth, for shadow tomography, we show that O(log(m)/ε2) copies are sufficient to learn m given observables O1, …, Om in the ”high accuracy regime”, when ε = O(1/d), improving on a result of Chen et al. More generally, we show that if tr(Oi2) ≤ F for all i, then n = O(log(m) · (min{√r F/ε, F2/3/ε4/3}+ 1/ε2)) copies suffice, improving on existing work. Finally, for quantum metrology, we give a locally unbiased algorithm whose mean squared error matrix is upper bounded by twice the inverse of the quantum Fisher information matrix in the asymptotic limit of large n, which is optimal.
How many copies of a mixed state ρ∈Cd×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(d3⋅(loglog(d)/log(d))4) copies of ρ, which is asymptotically fewer than the n=Ω(d3) 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.
We initiate the study of weak Schur sampling (WSS) under noisy inputs. Many optimal quantum learning algorithms rely on this measurement, for instance in quantum spectrum estimation (QSE) and quantum state tomography (QST). The standard analysis of WSS, QSE and QST assumes that the n input copies of the target state ρ are identical, i.e. ρ⊗n. We study what happens when they are not, a more realistic noisy scenario that breaks the very permutation symmetry on which WSS is built. In the simplest model the input is a noisy product state: the copies are independent but not necessarily identical and each is ε-close in trace distance to the d-dimensional target state ρ. A naive argument via the data-processing inequality allows the per-copy errors to accumulate to nε on the measurement outcome. We show that for QSE via WSS this does not happen: the expected estimation error in total variation is at most ε+η(n,d), where η(n,d)=O(d/n) is the noiseless error, and the additive noise term ε is optimal. The output error does not grow with n even though the input error does; in this sense WSS is robust. Beyond noisy product states, for arbitrary input ω we show that the error is at most η(n,d)+n1∥ω−ρ⊗n∥W1, where W1 is the quantum Wasserstein distance of De Palma et al. In particular, our results imply, for the first time, noise-robustness of Keyl and Werner's seminal algorithm for QSE, more than two decades after its introduction. Finally, we show that the noise cannot be too bad: within our model of robustness the promise on the input cannot be weakened to closeness of single-copy marginals or to a global trace-distance budget alone, as in both cases some inputs defeat every measurement and estimator.
We show that n=Ω(rd/ε2) copies are necessary to learn a rank r mixed state ρ∈Cd×d up to error ε in trace distance. This matches the upper bound of n=O(rd/ε2) from prior work, and therefore settles the sample complexity of mixed state tomography. We prove this lower bound by studying a special case of full state tomography that we refer to as projector tomography, in which ρ is promised to be of the form ρ=P/r, where P∈Cd×d is a rank r projector. A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error ε in trace distance to an algorithm which learns to error O(ε) in the more stringent Bures distance.
We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For d-dimensional states, and for every γ>0, we prove a sample complexity lower bound of Ω(d2−γ) for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an f-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.