PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal spectrum estimation

Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan

arXiv:2609.30171v1quant-phcs.CCcs.DS

TL;DR

The optimal copy complexity of spectrum estimation remains unresolved in its dimension and accuracy dependence. The paper estimates small eigenvalues by matching Chebyshev moments, with variance analysis based on polynomial derivatives. At constant accuracy, its entangled algorithm matches Wang's lower bound, and its unentangled guarantee is conjectured optimal.

  • Problem

    Existing bounds leave the optimal dimension dependence and how the rate changes with accuracy unresolved.

    Source: §1 · p. 3

  • Method

    The paper estimates large eigenvalues first, then reconstructs small eigenvalues by matching approximate Chebyshev moments with variance bounds derived from polynomial derivatives.

    Source: §1.1 · p. 4, §2.2 · p. 8

  • Results

    At constant accuracy, entangled estimation uses O(d^2/log^4 d) copies and matches Wang's lower bound, while the unentangled guarantee uses O(d^3/log^4 d) copies.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The entangled bound matches the lower bound up to constant factors, while optimality of the unentangled copy complexity remains a conjecture.

    Source: §1.1 · p. 4

    Whether the unentangled copy bound can be achieved without adaptively choosing measurements remains unclear.

    Source: §3 · p. 13

Abstract

from arXiv · show

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.

1 Introduction

A quantum state's spectrum captures basis-invariant information and supports the study of quantities including entropy and entanglement. This work addresses optimal copy complexity for estimating that spectrum, giving entangled and unentangled algorithms and a Chebyshev-moment framework for recovering small eigenvalues.

1 Introduction

  • The central question is how many copies are needed for spectrum estimation, since existing bounds leave optimal dimension and accuracy dependence unresolved.With a known eigenbasis, constant-accuracy estimation reduces to classical sorted distribution estimation requiring Θ(d/log d) samples.Source: §1 · p. 3

1.1 Our results

  • At constant accuracy, entangled spectrum estimation uses O(d^2/log^4 d) copies, matching Wang's lower bound up to constant factors.The bound also refutes the conjectured Θ(d^2/(ε^2 log^2 d)) rate.Source: §1.1 · p. 4
  • For states promised to have rank at most r, the copy-complexity bound replaces d with r, and the matching lower bound makes this setting optimal as well.The algorithm first applies a random dimension reduction that returns r-dimensional copies with the same nonzero eigenvalues.Source: §1.1 · p. 4
  • At constant accuracy, the unentangled guarantee uses O(d^3/log^4 d) copies, improves the prior bound's (log log d)^4 factor, and is conjectured optimal.The accuracy dependence improves from ε^-6 to ε^-4 or ε^-2, depending on the regime.Source: §1.1 · p. 4
  • The algorithms estimate large eigenvalues and approximately separate them from small ones, then recover the small eigenvalues by matching Chebyshev moments.The moment-matching framework controls how errors in estimated moments affect the recovered eigenvalues.Source: §1.1 · p. 4
  • Classical and quantum Efron–Stein decompositions reduce moment-variance analysis to scalar polynomial derivatives; rescalings balance variance and approximation error across two accuracy regimes.Mapping the spectrum to [−1, 1] yields the (ε log d)^-4 dependence, while mapping it to [−1/2, 1/2] yields (ε log d)^-2.Source: §1.1 · p. 4

2 Technical overview

The technical overview describes recovering the small spectrum by matching Chebyshev moments after estimating large eigenvalues. It bounds moment-estimator variance using scalar polynomial derivatives and tunes Chebyshev rescalings to obtain two copy-complexity regimes.

2 Technical overview

  • Bucketing estimates eigenvalues above threshold B and reduces the remaining task to recovering a state whose spectrum lies in [0, 1.1B].The bucketing step uses O(d/(Bε^2)) copies, estimates the large eigenvalues to O(ε) total variation error, and constructs a large-bucket projector of rank O(1/B).Source: §2 · p. 5

Measurements on the small-bucket state.

  • A joint measurement on fresh copies gives unbiased monomial-moment estimates, allowing unbiased estimates of polynomial traces from the same, potentially correlated, outcome.The procedure measures the bucket projector on each copy and applies weak Schur sampling to the retained copies.Source: Measurements on the small-bucket state · p. 5

2.1 Chebyshev moment matching

  • Chebyshev moment matching controls spectrum error through polynomial approximation and moment discrepancies, while avoiding potentially exponential monomial coefficients.The shifted, scaled Chebyshev basis is used because bounded polynomials can have exponentially large monomial coefficients; the standard coefficient bound of [MMRS25] yields O(d^2(ε log(d))^-4) copy complexity.Source: §2.1 · pp. 5–6
  • A tailored Lipschitz witness sharpens the Chebyshev coefficient bound: it scales with the integral of the squared derivative, which is at most 2dTV(α, z) for this witness.The witness has slope −sgn(F(x)) where the true and candidate eigenvalue counts differ, making its derivative bound depend on the spectrum distance.Source: §2.1 · pp. 6–7
  • The reconstruction chooses a feasible spectrum minimizing weighted squared Chebyshev-moment discrepancies, so its fitting error is bounded by the estimation error.Because moment estimates are unbiased but correlated, expected squared estimation error reduces to the sum of their variances without requiring independence.Source: §2.1 · p. 7

2.2 Variance bounds from polynomial derivatives

  • A quantum Efron–Stein decomposition retains cancellations among correlated errors and bounds the polynomial-estimator variance through derivatives of the polynomial on [0, L].Its orthogonal components act on subsets of input copies, so their second moments add; the analysis relates these components to derivatives of the estimator's mean.Source: §2.2 · pp. 8–9
  • The variance of each polynomial moment estimate is controlled by scalar derivatives on [0, L], combining monomial contributions before squaring and retaining error cancellations.Source: §2.2 · p. 11

2.3 Choosing the polynomials

  • O(d^2/(ε^4(log d)^4)) copies suffice using the full spectral interval, where finer approximation near zero is balanced against larger endpoint derivatives.The construction takes K = (log d)^2.Source: §2.3 · p. 12
  • O(d^2/(ε^2(log d)^2)) copies suffice with an interior Chebyshev interval, whose smaller derivatives permit higher degree despite larger approximation error.The construction uses L = (log d)^2/d and K = (log d)^2/ε.Source: §2.3 · p. 12

3 Discussion and outlook

The discussion identifies open questions about applying the method to other spectral properties and about the need for adaptive measurements. It also highlights unresolved sample-complexity questions for classical sorted distributions and unentangled quantum measurements.

Applications to learning other symmetric properties

  • Extending the framework to trace distance or fidelity would require estimating information beyond the two spectra separately.The authors also suggest applications to von Neumann entropy and rank testing, whose sharp rates remain unresolved.Source: §3 · p. 12

Optimal two-bucket algorithms for learning sorted distributions?

  • For sorted-distribution learning, optimal sample complexity remains unsettled between the regimes ε ⩾1/d^(1−γ) and ε ⩽1/d.The cited bounds are Θ(d/(ε^2 log d)) in the first regime and Θ(d/ε^2) in the second.Source: §3 · pp. 12–13

Is adaptivity necessary for spectrum estimation?

  • Whether unentangled spectrum estimation can achieve its copy bound with measurements fixed in advance remains open; the entangled case has an optimal weak-Schur-sampling measurement.The authors also conjecture their adaptive unentangled sample complexity is optimal, while noting that the best lower bound is inherited from the entangled setting.Source: §3 · p. 13

4 Preliminaries

The preliminaries specify the measurement models and the distances used to compare spectra. They also introduce Chebyshev polynomials and Jackson approximation as tools for the paper’s analysis.

Notation

  • The notation retains zero eigenvalues in spectra and uses D(H) for density operators on a Hilbert space.Source: §4 · p. 13

Quantum measurement models

  • Entangled measurements allow an arbitrary joint POVM on all copies, whereas unentangled measurements act separately on each copy and may adapt to prior outcomes.Only classical information is retained between copies in the unentangled model.Source: §4 · p. 13

Wasserstein-1 distance

  • The paper uses unnormalized Wasserstein-1 distance for sorted spectra and its Kantorovich–Rubinstein duality.The dual characterization is stated for counting measures associated with the spectra.Source: §4 · p. 13

Chebyshev polynomials and Jackson’s theorem

  • Chebyshev polynomials are degree-k polynomials, and Jackson’s theorem supplies damped Chebyshev approximations to Lipschitz functions with error bounded by ℓ/K.The paper uses a refined version of the theorem later.Source: §4 · p. 14

5 Bucketing algorithms

The algorithms first separate large and small eigenvalues using a bucketing procedure, then estimate the spectrum of the small-bucket state. The paper reuses prior bucketing guarantees and improves the second-stage recovery method.

Bucketing framework

  • The two-stage method estimates large eigenvalues and constructs a small-bucket projector before recovering the small eigenvalues of ΠρΠ.The same bucketing framework was used in prior entangled and unentangled algorithms; the improvement comes from changing the second stage.Source: §5 · p. 14

Bucketing guarantees

  • Bucketing guarantees low error on large eigenvalues, low misclassification of small eigenvalues, and low alignment error in the full spectrum.The bucketing procedure returns a projector and a sorted list of estimated large eigenvalues.Source: §5 · p. 14

Recovering the small eigenvalues

  • The remaining task is to estimate the small-bucket state’s spectrum using polynomial-trace estimates, with measurement procedures and variance bounds developed for both measurement models.The small-bucket state is σ = ΠρΠ.Source: §5 · p. 15

6 Spectrum recovery from Chebyshev moments

This section recovers a spectrum by fitting estimated Chebyshev moments, with error controlled by approximation quality and moment-estimation variance. Two rescalings trade approximation accuracy against derivative-based variance control.

6 Spectrum recovery from Chebyshev moments

  • Chebyshev moment matching reconstructs a feasible spectrum from unbiased moment estimates, bounding expected total-variation error by approximation error plus weighted moment variances.The fitting guarantees apply to both rescalings and do not require independent moment estimates.Source: §6 · pp. 15–16

6.2 Controlling the approximation error

  • Mapping the spectral interval to the full Chebyshev interval improves approximation near endpoints, while an interior rescaling does not provide that endpoint improvement.The interior choice instead offers smaller Chebyshev derivatives for variance control; any fixed interior rescaling has the same asymptotic guarantees, with constants depending on the rescaling.Source: §6 · p. 16, §6.2 · p. 18

6.1 Proof idea

  • Jackson approximations in the Chebyshev basis separate spectral error into approximation error and a coefficient-weighted moment discrepancy.Large polynomial coefficients can amplify noisy moment differences, so approximation accuracy alone is insufficient.Source: §6.1 · p. 17

6.3 Controlling the moment discrepancy

  • Damped Chebyshev coefficients control weighted moment discrepancy through coefficient energy bounded using the squared derivative of the approximated Lipschitz function.The least-squares objective makes the expected weighted moment discrepancies depend on the estimated moment variances.Source: §6.2 · p. 17, §6.3 · p. 19

6.4 A common proof of the recovery guarantees

  • The common recovery proof combines the approximation and moment-discrepancy bounds to give expected-error guarantees for the least-squares estimators.Given moment estimates, recovery can be implemented in poly(d, K, 1/η) time while preserving the guarantees up to universal constants and an arbitrarily small additive tolerance.Source: §6.4 · pp. 20–21

7 Variance of the estimated Chebyshev moments

This section bounds the variance of polynomial moment estimators, including the Chebyshev moments used for recovery, by reducing classical and quantum Efron–Stein analyses to derivative operators and bounding them with matrix analysis. It closes the variance-bound proofs using Eq. (51) and gives the proof step for Lemma 7.1.

7 Variance of the estimated Chebyshev moments

  • The polynomial variance bound and its Chebyshev-moment corollary control estimator variance through derivatives of the underlying scalar polynomial.The authors apply the polynomial bound to the Chebyshev polynomials ϕ_k and ψ_k; the measurement-scheme coefficients are independent of the polynomial, so their variance bounds differ through their derivatives.Source: §7 · pp. 21–22

7.1 Measurements on the small-bucket state

  • Both measurement schemes first project fresh copies onto the small-bucket subspace and produce unbiased estimates of tr(σ^m) for m = 1,…,K.The complementary measurement outcome is discarded; the monomial estimates are then combined to estimate tr(p(σ)).Source: §7.1 · p. 22

7.1.1 Unentangled measurements

  • The unentangled scheme uses a conditioned uniform POVM on retained copies and constructs monomial moment estimates from independent matrix-valued outcomes.The resulting polynomial estimator is real, symmetric, and affine in each input.Source: §7.1.1 · pp. 22–23

7.1.2 Entangled measurements

  • The entangled scheme simultaneously measures permutation-invariant observables on retained copies, yielding an unbiased estimate of tr(p(σ)).Its measured observables can be jointly measured via weak Schur sampling.Source: §7.1.2 · p. 23

7.2 Reducing the variance to derivative operators

  • Variance analysis is reduced to derivative operators that encode how tr(p(A)) changes around A = σ.The derivatives are represented by Hermitian operators so their Hilbert–Schmidt norms can be used to bound variance.Source: §7.2 · pp. 23–24

7.2.1 Unentangled measurements

  • For unentangled measurements, a classical Efron–Stein decomposition splits the symmetric multiaffine estimator into orthogonal variance contributions.The argument applies to the moment estimator because its inputs are independent and its function is symmetric and affine in every argument.Source: §7.2.1 · p. 24

7.2.2 Entangled measurements

  • For entangled measurements, a quantum Efron–Stein decomposition bounds the variance of a permutation-invariant observable measured on multiple copies.The decomposition is applied to the observable whose measured value estimates tr(p(σ)).Source: §7.2.2 · p. 26

7.3 Bounding the derivative operators

  • Matrix analysis bounds the derivative operators for any 0 ⪯ σ ⪯ L I_d with tr(σ) ⩽ 1, independently of the measurement scheme.A trace-derivative formula expresses derivatives using symmetric coefficients determined by scalar derivatives of p.Source: §7.3 · p. 27
  • The proof combines these estimates with Eq. (51) to establish both bounds, and proves Lemma 7.1 by substituting Lemma 7.9 into Lemma 7.3.Source: §7.3 · p. 28

8 Algorithms and analysis

Algorithm 8.1 buckets the spectrum, estimates small-bucket moments, and reconstructs the small spectrum; measurement model and accuracy regime determine its parameters. The proof establishes an O(ε) conditional total-variation error and amplifies success probability to 0.99.

8 Algorithms and analysis

  • The algorithm’s parameter choices vary with the measurement model and accuracy regime, as organized in Tables 2 and 3.Table 2 covers measurement-model choices; Table 3 covers accuracy-regime choices and the polynomials ϕk and ψk.Source: Table 2 · p. 28, Table 3 · p. 28, §8 · p. 28
  • Algorithm 8.1 buckets the spectrum, estimates moments on fresh copies, reconstructs the small spectrum, and returns it with the large eigenvalues.The measurement model selects the bucketing algorithm and small-bucket measurements; the accuracy regime sets threshold B, degree K, and the moment polynomials.Source: §8 · pp. 28–29

8.1 Proof of Theorems 1.1 and 1.3

  • O(ε) conditional total-variation error and success probability 0.99 after amplification establish the algorithm’s accuracy guarantee.Bucketing succeeds with probability at least 0.99, and the initial combined success probability exceeds 0.8.Source: §8.1 · p. 30
  • The bucketing cost is O(n) for entangled measurements and O(n/(dB)) = O(n) for unentangled measurements.Taking D = 1 and D = d, respectively, gives the bounds in Theorems 1.1 and 1.3.Source: §8.1 · p. 30

A Chebyshev derivative bounds for the variance analysis

The variance analysis uses derivative bounds for Chebyshev polynomials and their rescalings. An interior bound follows by applying a polynomial derivative estimate after rescaling the interval.

A Chebyshev derivative bounds for the variance analysis

B Jackson approximation and rescaling

The appendix constructs Jackson-kernel polynomial approximations and rescales them to control approximation error. It also gives an endpoint-anchored version and bounds moments of the normalized kernel.

B Jackson approximation and rescaling

  • The Jackson-kernel convolution produces a polynomial Qf of degree at most K by truncating its cosine coefficients.The normalized kernel multiplies the kth cosine coefficient by b̂k/b̂0, and b̂k vanishes for k > 2m − 2.Source: B Jackson approximation and rescaling · p. 33
  • The normalized Jackson kernel is nonnegative and integrates to one, giving M1 ≤ √M2 ≤ C/K.The kernel moments are defined using integrals of |u|^j b(u) for j = 1, 2.Source: B Jackson approximation and rescaling · p. 33
  • The pointwise approximation estimate uses the Lipschitz property to bound changes in h by sin θ |u| + u² before integrating against the normalized kernel.The passage describes this as a refinement of the convolution estimate.Source: B Jackson approximation and rescaling · p. 34
  • When f(−1) = 0, subtracting Qf(−1) anchors the approximant at the endpoint and gives an estimate that vanishes as δ → 0.The construction compares convolution integrands near the anchored endpoint using the Lipschitz property.Source: B Jackson approximation and rescaling · p. 34

C Proof of the trace derivative formula

The proof derives the trace derivative formula by induction on the number of derivatives, then bounds its coefficients using interpolation and Rolle’s theorem.

C Proof of the trace derivative formula

  • Product-rule induction differentiates the matrix powers one block at a time, with cyclicity of trace keeping the first direction matrix fixed.The induction extends the formula by summing over insertion positions and relabeling the resulting orders.Source: C Proof of the trace derivative formula · p. 35
  • When n < r, the rth derivative vanishes because A^n has total degree at most n in the perturbation variables.The resulting trace derivative formula has symmetric real coefficients for a real polynomial of degree at most k.Source: C Proof of the trace derivative formula · pp. 34–35
  • Evaluating at t = 0 sets A = σ, so diagonal σ converts matrix products in the trace into scalar eigenvalue factors.The proof sums over exponents after separating scalar entries of the direction matrices from powers of the eigenvalues.Source: C Proof of the trace derivative formula · pp. 35–36
  • The coefficient weights are bounded by a scalar derivative of p, using interpolation at the eigenvalue points and repeated applications of Rolle’s theorem.For coincident points, the proof perturbs them to distinct values and passes to the limit by continuity.Source: C Proof of the trace derivative formula · pp. 36–37
Loading 2609.30171v1…