Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values

Many quantum algorithms involve the evaluation of expectation values. Optimal strategies for estimating a single expectation value are known, requiring a number of iterations that scales with the target error $\epsilon$ as $\mathcal{O}(\epsilon^{-1})$. In this paper we address the task of estimating the expectation values of \(M\) different observables, each to within an error \(\epsilon\), with the same \(\epsilon^{-1}\) dependence. We describe an approach that leverages Gily\'{e}n \emph{et al.}'s~quantum gradient estimation algorithm to achieve $\mathcal{O}\sqrt{M}\epsilon^{-1})$ scaling up to logarithmic factors, regardless of the commutation properties of the $M$ observables.
We prove that this scaling is optimal in the worst case, even when the operators are mutually commuting. We highlight the flexibility of our approach by presenting several generalizations, including a strategy for accelerating the estimation of a collection of dynamic correlation functions.

• Quantum Computing