Classical algorithms for quantum mean values

We consider the task of estimating the expectation value of an n-qubit tensor product observable in the output state of a shallow quantum circuit. This task is a cornerstone of variational quantum algorithms for optimization, machine learning, and the simulation of quantum many-body systems. Here we study its computational complexity for constant-depth quantum circuits and tensor products of single-qubit observables which are (a) close to the identity, (b) positive semidefinite, (c) arbitrary. We show that the mean value problem admits a classical approximation algorithm with polynomial runtime in case (a) and subexponential runtime in case (b). In case (c) we give a linear-time algorithm for geometrically local circuits on a two-dimensional grid, which is based on a Monte Carlo method combined with Matrix Product State techniques.