  The Feynman-Kac path integration problem was studied in the worst case
setting by Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate
case and by Kwas and Li (J. Comp. 19 (2003) 730) for the multivariate case with
d space variables. In this paper we consider the multivariate Feynman-Kac path
integration problem in the randomized and quantum settings. For smooth
multivariate functions, it was proven in Kwas and Li (2003) that the classical
worst case complexity suffers from the curse of dimensionality in d. We show
that in both the randomized and quantum settings the curse of dimensionality is
vanquished, i.e., the number of function evaluations and/or quantum queries
required to compute an e-approximation has a bound independent of d and
depending polynomially on 1/e. The exponents of these polynomials are at most 2
in the randomized setting and at most 1 in the quantum setting. Hence we have
exponential speedup over the classical worst case setting and quadratic speedup
of the quantum setting over the randomized setting. However, both the
randomized and quantum algorithms presented here still require extensive
precomputing, similar to the algorithms of Plaskota et al. (2000) and Kwas and
Li(2003).
