Abstract
We study path integration on a quantum computer that performs quantum summation. We assume that the measure of path integration is Gaussian, with the eigenvalues of its covariance operator of order j^\{-k\} with k>1. For the Wiener measure occurring in many applications we have k=2. We want to compute an -approximation to path integrals whose integrands are at least Lipschitz. We prove: 1. Path integration on a quantum computer is tractable. 2. Path integration on a quantum computer can be solved roughly times faster than on a classical computer using randomization, and exponentially faster than on a classical computer with a worst case assurance. 3.The number of quantum queries is the square root of the number of function values needed on a classical computer using randomization. More precisely, the number of quantum queries is at most . Furthermore, a lower bound is obtained for the minimal number of quantum queries which shows that this bo