On tractability of path integration

Many applications require approximate values of path integrals. A typical approach is to approximate the path integral by a high dimensional integral and apply a Monte Carlo (randomized) algorithm. However, Monte Carlo algorithm requires roughly ∈^-2 integrand evaluations to provide an ∈ approximation. Moreover, the error bound of ∈ is guaranteed only in a stochastic sense. Do we really need to use randomized algorithms for path integrals? Perhaps, we can find a deterministic algorithm that is more effective even in the worst case setting. To answer this question, we study the worst case complexity of path integration, which, roughly speaking, is defined as the minimal number of the integrand evaluations needed to compute an approximation with error at most ∈. We consider path integration with respect to a Gaussian measure, and for various classes of integrands. Tractability of path integration means that the complexity depends polynomially on 1/∈. We show that for the class of r times Frechet differentiable integrands, tractability of path integration holds iff the covariance operator of the Gaussian measure has finite rank. Hence, if the Gaussian measure is supported on an infinite dimensional space then path integration is intractable. In this case, there exists no effective deterministic algorithm, and the use of randomized algorithms is justified. In fact, for this class of integrands, the classical Monte Carlo algorithm is (almost) optimal and the complexity in the randomized setting is proportional to ∈^-2. On the other hand, for a particular class of entire integrands, the worst case complexity of path integration is at most of order ∈^-p with p depending on the Gaussian measure. Hence, path integration is now tractable. Furthermore, for any Gaussian measure, the exponent p is less than or equal to 2. For the Wiener measure, p = 2/3. For this class, we provide effective deterministic algorithms which solve the path integration problem with (worst case) cost that is usually much less than the (randomized) cost of the classical Monte Carlo algorithm.