Continuous quantum computation: Difference between revisions

Revision as of 23:02, 7 March 2007

Revision as of 18:54, 8 March 2007

Line 15:

* 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 slightly modifying the rules of quantum computation. THE LAST SENTENCE DOES NOT SOUND GOOD. IT'S BETTER TO SAY "BY MODIFYING THE WAY THE FUNCTIONS ARE SAMPLEDqueries.

In the standard model of quantum computation the only probabilistic nature of quantum computation enters only through measurement; the queries are deterministic. In analogy with classical Monte Carlo Woźniakowski introduced the idea of a quantum setting with [http://arXiv.org/quant-ph/0601196 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==

Besides path integration there have been numerous recent papers studying the algorithms and quantum speedups for continuous problems. These include matrix eigenvalues, phase estimation, the Sturm-Liouville eigenvalue problem, Feynman-Kac path integration, initial value problems, function approximation and high dimensional inetgrationintegration. See the papers listed 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 35:

*Papageorgiou, A. and Wo´zniakowski, H. (2007), The Sturm-Liouville Eigenvalue Problem and NP-Complete Problems in the Quantum Setting with Queries, Quantum Information Processing, 6(2), 101-120. Also http://arXiv.org/quant-ph/0504194.

*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´zniakowskiWoźniakowski, H. (2006), The Quantum Setting with Randomized Queries for Continuous Problems, Quantum Information Processing, 5(2), 83–130. Also http://arXiv.org/quant-ph/0601196.

==External links==