In this paper, we give a quantum circuit for calculating the mean value of a function A(xn)∈C, where xn∈{0,1}n. Known classical algorithms for calculating the mean value of a structureless function A(xn) take O(2n) steps. Our quantum algorithm is based on a Grover-like algorithm and it takes O(2n) steps. Our algorithm differs significantly from previously proposed quantum algorithms for calculating the mean value of a function via Grover's algorithm.
The quantum mean value (QMV) problem is a classically difficult problem that is the central part of many quantum algorithms. We show that using an approximation instead of the exact expectation results in a quadratic improvement in the efficiency of QMV and thus the underlying quantum algorithm. Together with efficient classical sampling algorithms, a quantum algorithm with minimal gate count can thus improve the efficiency of algorithms to solve general integer-value problems, such as the shortest vector problem investigated in this work.
Simulating physical systems has been an important application of classical and quantum computers. In this article we present an efficient classical algorithm for simulating time-dependent quantum mechanical Hamiltonians over constant periods of time. The algorithm presented here computes the mean value of an observable over the output state of such short-time Hamiltonian evolutions. In proving the performance of this algorithm we use Lieb-Robinson type bounds to limit the evolution of local operators within a lightcone. This allows us to divide the task of simulating a large quantum system into smaller systems that can be handled on normal classical computers.