Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values

Many quantum algorithms involve the evaluation of expectation values with respect to some pure state. Optimal strategies for estimating a single expectation value to within a precision ε are known, requiring a number of calls to a state preparation oracle proportional to ε^-1 in the asymptotic limit. In this paper, we address the task of evaluating the expectation values of M different observables with the same ε^-1 scaling in the desired precision. We provide an approach that requires a number of calls to oracle calls that scales as M^1/2ε^-1(neglecting logarithmic factors). Furthermore, we show that this scaling is optimal, even in the special case when the operators in question commute.