Continuous quantum computation: Difference between revisions

Revision as of 15:40, 7 July 2007

Revision as of 15:41, 7 July 2007

Line 7:

* In their standard monograph Nielsen and Chuang state "Of particular interest is a decisive answer to the problem whether quantum computers are more powerful than classical computers." To answer this question one must know the classical and quantum computational complexities

We discuss the second motivation. By computational complexity (complexity for brevity) is meant the '''minimal''' computational resources needed to solve a problem. Two of the most important resources for quantum computing are [[qubit]]s and queries. Classical complexity has been extensively studied in [[Informationinformation-Basedbased Complexity| Information-Based Complexitycomplexity]]. The classical complexity of many continuous problems is known. Therefore, when the quantum complexity of these problems is obtained, the question as to whether quantum computers are more powerful than classical can be answered. Furthermore, it can be established how much more powerful. In contrast, the complexity of discrete problems is typically unknown; one has to settle for the complexity hierarchy. For example, the classical complexity of integrer factorization is unknown.

==An example: path integration==

Path integration has numerous applications including [[quantum mechanics]], [[quantum chemistry]], [[statistical mechanics]], and [[computational finance]]. We want to compute an approximation to within error at most <math>\scriptstyle\varepsilon</math> with probability, say, at least 3/4. Then the following was [http://arXiv.org/quant-ph/0109113 shown] by Traub and Woźniakowski:

* A quantum computer enjoys exponential speedup over the classical worst case and quadratic speedup over the classical randomized case.

* The query complexity is of order <math>\scriptstyle\varepsilon^{-1}</math>.