Quantum Algorithms and Complexity for Certain Continuous and Related Discrete Problems

Title:

Quantum Algorithms and Complexity for Certain Continuous and Related Discrete Problems

Author(s):

Kwas, Marek

Date:

2005

Type:

Technical reports

Department:

Computer Science

Permanent URL:

http://hdl.handle.net/10022/AC:P:29387

Series:

Columbia University Computer Science Technical Reports

Part Number:

CUCS02605

Abstract:

The thesis contains an analysis of two computational problems. The first problem is discrete quantum Boolean summation. This problem 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 FeynmanKac 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, Híyer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean function. We improve the error bound of Brassard et al. for the worstprobabilistic setting. Our error bound is sharp. We also present new sharp error bounds in the averageprobabilistic and worstaverage settings. Our averageprobabilistic error bounds prove the optimality of the QS algorithm for a certain choice of its parameters. The study of the worstaverage error shows that the QS algorithm is not optimal in this setting; we need to use a certain number of repetitions to regain its optimality. The multivariate FeynmanKac path integration problem for smooth multivariate functions suffers from the provable curse of dimensionality in the worstcase deterministic setting, i.e., the minimal number of function evaluations needed to compute an approximation depends exponentially on the number of variables. We show 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. Hence, the quantum setting yields exponential speedup over the worstcase deterministic setting, and quadratic speedup over the randomized setting.

Subject(s):

Computer science
 Item views:

122
 Metadata:

text  xml