Content deleted Content added
No edit summary |
mNo edit summary |
||
Line 9:
In the section An Example: Path Integration solving a continuous problem on a quantum computer will be discussed. Here the second motivation will be amplified. 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 qubits and queries. Classical complexity has been extensively studied in [[Information-Based Complexity| informations-based complexity]]. 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.
Path integration has numerous applications including quantum mechanics, quantum chemistry, statistical mechanics, and computational complexity. We want to compute an approximation to within error at most <math>\epsilon</math> with probability, say, at least 3/4. Then the following was 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.
Line 19:
In the standard model of quantum computation the only probabilistic nature of quantum computation only enters through measurement; the queries are deterministic. As an analogy to classica Monte Carlo Woźniakowski introduced the idea of a quantum setting with randomized queries. He showed that in this setting the qubit complexity is of order <math> \log\epsilon^{-1}</math>, thus achieving an exponential improvement over the qubit complexity in the standard quantum computing setting.
Besides path integration,
over the last few years there have been numerous papers studying the complexity of quantum algorithms solving continuous problems. The approximation of multivariate integrals and functions, Feynman-Kac path integration, the solution of initial value problems, the Sturm-Liouville eigenvalue problem are just a few examples. More details can be found in the papers below and the references therein:
Line 36:
*Wo´zniakowski, H. (2006), The Quantum Setting with Randomized Queries for Continuous Problems, Quantum Information Processing, 5(2), 83–130. Also http://arXiv.org/quant-ph/060196.
*Continuous quantum computing web page at Columbia University http://quantum.cs.columbia.edu
| |||