Improved methods estimate quantum state properties using fewer copies
Optimal spectrum estimation
Computational ComplexityData Structures and Algorithms
Summary
Figuring out the details of a quantum state—a kind of quantum information—requires making copies of that state and measuring them. The authors find the best way to estimate the spectrum, which is like a list of important numbers that describe the state, using fewer copies than before. They also provide a method that works without complex measurements that involve entanglement. Their approach uses special math tools called Chebyshev polynomials to carefully balance accuracy and the amount of effort needed.
What this means in practice
- •For quantum computing engineers: Design quantum state characterization procedures needing fewer quantum state copies for testing and quality control.
- •For quantum device calibration teams: Improve efficiency in estimating quantum device outputs without requiring complex entangled measurements.
A theory result. No direct application yet.
Authors
Ainesh Bakshi, Apoorv Vikram Singh, Xinyu Tan
Abstract
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.