We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[
O\!\left(d^2\min\left\{
\frac{1}{(\varepsilon\log d)^4},\;
\frac{1}{(\varepsilon\log d)^2}
\right\}\right) \] 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.
AI Summary
The paper asks how many copies of an unknown $d$-dimensional quantum state are needed to estimate its sorted eigenvalue vector to total-variation error $\varepsilon$, without learning its eigenbasis. It establishes an entangled-measurement copy complexity of $O(d^2\min\{(\varepsilon\log d)^{-4},(\varepsilon\log d)^{-2}\})$, matching a recent lower bound up to constants. At constant accuracy this is $\Theta(d^2/\log^4 d)$; the accuracy dependence changes at $\varepsilon\asymp1/\log d$. Under a rank-$r$ promise, $d$ can be replaced by $r$. For adaptive single-copy measurements, it gives an upper bound with an additional factor of $d$.
Both algorithms reuse a bucketing procedure to estimate large eigenvalues and isolate a small-eigenvalue subspace. The remaining spectrum is reconstructed by weighted least-squares matching of estimated Chebyshev moments. A Wasserstein-duality argument exploits the integer-valued cumulative counts of eigenvalues to sharpen reconstruction bounds. Classical and quantum Efron–Stein decompositions control correlated moment-estimation errors through matrix derivatives, which are then bounded using scalar polynomial derivatives. Two Chebyshev rescalings trade endpoint-sensitive approximation against variance, producing the two accuracy regimes.
Optimality for single-copy measurements remains conjectural: the available lower bound is only the entangled one. Although weak Schur sampling alone is sufficient in principle for sample-optimal entangled estimation, explicit optimal classical postprocessing without adaptive bucketing remains unresolved. It is also open whether nonadaptive single-copy measurements achieve the stated single-copy bound. Applications of the framework to entropy estimation and other symmetric properties are proposed but not established.
Little sign of AI-generated textAI use disclosed
The authors used GPT 5.6 Sol to assist with the technical proofs and GPT 6 Astra to assist with the technical writing.
Error found: The algorithm does not normalize its final nonnegative list to a probability vector as the theorems require, but adding normalization repairs the guarantee with at most a factor-two increase in error.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
We prove that the spectrum of an unknown d-dimensional quantum state can be estimated to error ε in total variation distance using [
O!\left(d^2\min\left{
\frac{1}{(\varepsilon\log d)^4},;
\frac{1}{(\varepsilon\log d)^2}
\right}\right) ] 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.
The paper asks how many copies of an unknown d-dimensional quantum state are needed to estimate its sorted eigenvalue vector to total-variation error ε, without learning its eigenbasis. It establishes an entangled-measurement copy complexity of O(d2min{(εlogd)−4,(εlogd)−2}), matching a recent lower bound up to constants. At constant accuracy this is Θ(d2/log4d); the accuracy dependence changes at ε≍1/logd. Under a rank-r promise, d can be replaced by r. For adaptive single-copy measurements, it gives an upper bound with an additional factor of d.
Both algorithms reuse a bucketing procedure to estimate large eigenvalues and isolate a small-eigenvalue subspace. The remaining spectrum is reconstructed by weighted least-squares matching of estimated Chebyshev moments. A Wasserstein-duality argument exploits the integer-valued cumulative counts of eigenvalues to sharpen reconstruction bounds. Classical and quantum Efron–Stein decompositions control correlated moment-estimation errors through matrix derivatives, which are then bounded using scalar polynomial derivatives. Two Chebyshev rescalings trade endpoint-sensitive approximation against variance, producing the two accuracy regimes.
Optimality for single-copy measurements remains conjectural: the available lower bound is only the entangled one. Although weak Schur sampling alone is sufficient in principle for sample-optimal entangled estimation, explicit optimal classical postprocessing without adaptive bucketing remains unresolved. It is also open whether nonadaptive single-copy measurements achieve the stated single-copy bound. Applications of the framework to entropy estimation and other symmetric properties are proposed but not established.
We show that the von Neumann entropy of an unknown d-dimensional quantum state ρ can be estimated to within additive error ε using Θ(εlog2(d)(1+εlog2(d))d2+ε2log2(d)) samples of ρ, matching the lower bound due to Wang (2026). Our estimator is based on a high-degree approximation polynomial and the main technical challenge is bounding its variance despite the large polynomial degree. We overcome this using a quantum Hoeffding decomposition, which preserves cancellations between different polynomial terms and reduces the analysis to derivative bounds for the approximation polynomial.
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. Source: http://arxiv.org/abs/2609.30171v1 (arXiv:2609.30171v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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.
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.
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.
We study the number of copies needed to estimate the root Uhlmann fidelity between an unknown quantum state and a classically known reference, under collective measurements. If the unknown state has rank at most s, we give an estimator using O(s2/ε2) copies, uniformly in the ambient dimension and reference rank. The estimator applies a random-purification channel and a covariant pure-state measurement, then rescales the observed amplitude before evaluating a weighted nuclear norm. Combined with the lower bound established independently in our first version and in concurrent work of Wang, this determines the worst-case complexity under rank bounds r,s as min{r,s}2/ε2 up to logarithmic factors in the smaller rank.
The same estimator gives the upper bound O(r(trσ)2/ε2) for a rank-r reference σ. We combine spectral truncation with lower bounds obtained by embedding hard instances for the maximally mixed reference into spectral subspaces. For spectra λi∝i−α with fixed 1<α≤2, as ε↓0 with r≥Cαε−2/(α−1), the bounds determine the complexity as Θα(ε−4/(α−1)). In particular, inverse-square spectra have accuracy exponent four. The lower-bound construction uses exact moment matching and an explicitly computable Schur measure.