Minimax Optimal Estimation of Expectation Values

Abstract: Learning the expectation values of observables is an important task in quantum information, with applications to characterization of quantum devices and quantum optimization algorithms. We propose an estimation method called The Optimal Observable expectation value Learner, or TOOL, that can learn the expectation value of any given observable using the outcomes of any given measurement protocol. We prove that TOOL is minimax optimal for every observable and measurement protocol, and can dramatically outperform classical shadows for many observables of interest. Using experimental data from a trapped-ion quantum computer, we show that TOOL performs well in practice for fidelity estimation.