Continuous quantum computation: Difference between revisions

Revision as of 20:05, 7 March 2007

Revision as of 22:57, 7 March 2007

Line 1:

'''Continuous Quantum Computation''' Two major motivations for studying continuous quantum computation are:

* Many scientific problems have continuous mathematical formulations. ExaplesExamples of such formulations are

** [[Path Integral Formulation|Path integration]]

** [[Feynman-Kac]] path integration

** [[Schrödinger]] equation

* 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 computationslcomputational complexities

InWe the section An Example: Path Integration solving a continuous problem on a quantum computer will be discussed. Herediscuss 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| informationsInformation-basedBased 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 complexityfinance. 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.

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

* The qubit complexity is of order <math>\epsilon^{-2}\log\epsilon^{-1}</math>.

Thus the qubit complexity of path integration is a second degree polynomial in <math>\epsilon^{-1}</math> That seems pretty good but we probably won't have enough qubits for a long time to do new science especially with error correction. Since this is a complexity result we can't do better by inventing a clever new algorithm. But perhaps we can do better by changingmodifying the formalrulesrules of quantum computation. THE LAST SENTENCE DOES NOT SOUND GOOD. IT'S BETTER TO SAY "BY MODIFYING THE WAY THE FUNCTIONS ARE SAMPLED.

In the standard model of quantum computation the only probabilistic nature of quantum computation enters only enters through measurement; the queries are deterministic. As anIn analogy towith classicaclassical 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.

==Applications==

overBesides thepath last few yearsintegration there have been numerous recent papers studying the complexityalgorithms ofand quantum algorithmsspeedups solvingfor continuous problems. TheThese approximationinclude ofmatrix multivariateeigenvalues, integralsphase andestimation, the Sturm-Liouville functionseigenvalue problem, Feynman-Kac path integration, the solution of initial value problems, thefunction Sturm-Liouvilleapproximation eigenvalueand problemhigh aredimensional just a few examplesinetgration. More details can be found inSee the papers listed below and the references therein:.

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:

*Bessen, A. J. (2005), A lower bound for phase estimation, Physical Review A, 71(4), 042313. Also http://arXiv.org/quant-ph/0412008.

Line 29 ⟶ 28:

*Heinrich, S. (2004), Quantum Approximation II. Sobolev Embeddings, J. Complexity, 20, 27–45. Also http://arXiv.org/quant-ph/0305031.

*Jaksch, P. and Papageorgiou, A. (2003), Eigenvector approximation leading to exponential speedup of quantum eigenvalue calculation, Phys. Rev. Lett., 91, 257902. Also http://arXiv.org/quant-ph/0308016.

*Kacewicz, B. Z. (20042005), Randomized and quantum solution of initial value problems, to appear in J. Complexity, 21, 740-756.

*Kwas, M., Complexity of multivariate Feynman-Kac Path Integration in Randomized and Quantum settings, 2004,. LANL preprintAlso http://arXiv.org/quant-ph/0410134.

*Novak, E. (2001), Quantum complexity of integration, J. Complexity, 17, 2–16. Also http://arXiv.org/quant-ph/0008124.

*Novak, E., Sloan, I. H., and Wozniakowski, H., Tractability of Approximation for Weighted orobov Spaces on Classical and Quantum Computers, Journal ofJ. Foundations of Computational Mathematics, 4, 121-156, 2004. Also http://arXiv.org/quant-ph/0206023

*Papageorgiou, A. and Wo´zniakowski, H. (2005), Classical and Quantum Complexity of the Sturm-Liouville Eigenvalue Problem, Quantum Information Processing, 4, 87–127. Also http://arXiv.org/quant-ph/0502054.

*TraubPapageorgiou, J. FA. and Wo´zniakowski, H. (20022007), PathThe integrationSturm-Liouville onEigenvalue aProblem quantumand NP-Complete Problems in the Quantum Setting with computerQueries, Quantum Information Processing, 1(5), 365–3886, 2002101-120. Also http://arXiv.org/quantphquant-ph/01091130504194.

*Traub, J. F. and Wo´zniakowski, H. (2002), Path integration on a quantum computer, Quantum Information Processing, 1(5), 365–388, 2002. Also http://arXiv.org/quant-ph/0109113.

*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.