Optimal spectrum estimation
Norah Tan | MIT
We prove that the spectrum of an unknown d-dimensional quantum state can be estimated to error ε in total variation distance using O(d2min{1(εlogd)4,1(εlogd)2}) 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.
Location
- QNC 1201
- Online on Zoom
-
Meeting ID: 912 8146 6256
Passcode: 494237
-
Add event to calendar
