Imagine you have a jar of mixed paint and you want to figure out the exact recipe—how much red, blue, yellow—without being allowed to unmix it. You can only dip a brush, look at the color on the bristle, and repeat. The question isn't whether you can recover the recipe. It's how many dips you need before your guess is as good as it gets. That's spectrum estimation: given copies of an unknown quantum state, determine the distribution of its eigenvalues to within ε in total variation distance. Bakshi, Singh, and Tan prove you need O(d²/ε⁴) copies in the best case, and this number is tight—it matches the lower bound Wang recently established. The core claim is clean and absolute: this is an optimal algorithm, not an approximation to optimality. The paper closes the gap between upper and lower bounds for quantum spectrum estimation in the general (entangled measurement) setting, achieving O(d² · min{1/(ε log d)⁴, 1/(ε log d)²}) copy complexity. The min of two regimes reflects a phase transition: for large ε the 1/ε² term dominates; for small ε, the 1/ε⁴ term takes over. Both are tight. The mechanism is beautiful in its indirection. Rather than estimating eigenvalues directly, the authors estimate Chebyshev moments of the spectrum—projections of the eigenvalue distribution onto Chebyshev polynomials. This is the same trick that makes signal processing work: represent a complicated shape through a basis of well-behaved oscillating functions, then recover the shape from the coefficients. The key technical challenge is bounding the variance of each moment estimate. They do this using Efron–Stein inequalities—both the classical version and a quantum generalization—which decompose variance into contributions from individual copies of the state. Different rescalings of the Chebyshev polynomials trade off approximation error against estimation variance, producing the two regimes visible in the copy complexity. For unentangled measurements—where you measure each copy of the state independently rather than performing joint measurements across copies—the paper gives an algorithm costing an additional factor of d, yielding O(d³/ε⁴). The authors conjecture this is optimal but don't prove a matching lower bound. This gap is the honest loose end, and they flag it explicitly. On the ladder, this result directly engages with and resolves the question posed by Wang's recent lower bound. Prior upper bounds from Keyl (2006) and O'Donnell–Wright (2016) had copy complexity Θ(d²/ε²) for the large-ε regime, but the small-ε regime was open. The authors' algorithm matches the Θ(d²/ε⁴) lower bound there, completing the picture. Against classical analogs—distribution estimation over d items requires Θ(d/ε²) samples—the quantum problem has a quadratic overhead in dimension, which is known to be necessary. Integrity here is as strong as it gets in theoretical computer science: the results are proved, not simulated. The upper bound is a constructive algorithm with a rigorous analysis; the matching lower bound is Wang's. There are no benchmarks to cherry-pick, no hyperparameters to tune, no training runs to report. The paper is 37 pages of mathematics. The validation is the proof. The practical horizon is measured not in engineering milestones but in whether quantum tomography protocols adopt this as the baseline sample-complexity target. Any experimentalist doing spectrum estimation on a d-dimensional system now knows the information-theoretic floor: you cannot do better than d²/ε⁴ copies, full stop. The unentangled gap—d² vs d³—is where the next theoretical fight lives.
