Quantum Algorithms and Complexity for Certain Continuous and Related Discrete Problems

摘要

This thesis contains an analysis of two computational problems. The first problem is discrete quantum Boolean summation, which is a building block of quantum algorithms for many continuous problems, such as integration, approximation, differential equations, and path integration. The second problem is continuous multivariate Feynman-Kac path integration, which is a special case of path integration. The quantum Boolean summation problem can be solved by the quantum summation (QS) algorithm of Brassard, Hoyer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean function. The author improves the error bound of Brassard et al. for the worst-probabilistic setting. The error bound is sharp. He also presents new sharp error bounds in the average-probabilistic and worst-average settings. His average-probabilistic error bounds prove the optimality of the QS algorithm for a certain choice of its parameters. The study of the worst-average error shows that the QS algorithm is not optimal in this setting; one needs to use a certain number of repetitions to regain its optimality. The multivariate Feynman-Kac path integration problem for smooth multivariate functions suffers from the provable curse of dimensionality in the worst-case deterministic setting (i.e., the minimal number of function evaluations needed to compute an approximation depends exponentially on the number of variables). He shows that, in both the randomized and quantum settings, the curse of dimensionality is vanquished (i.e., the minimal number of function evaluations and/or quantum queries required to compute an approximation depends only polynomially on the reciprocal of the desired accuracy and has a bound independent of the number of variables). The exponents of these polynomials are 2 in the randomized setting and 1 in the quantum setting. These exponents can be lowered at the expense of the dependence on the number of variables.