Content deleted Content added
No edit summary |
|||
Line 18:
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.
===Applications===
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, 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.
*Heinrich, S. (2002), Quantum Summation with an Application to Integration, J. Complexity,
18(1), 1–50. Also http://arXiv.org/quant-ph/0105116.
*Heinrich, S. (2003), Quantum integration in Sobolev spaces, J. Complexity, 19, 19–42.
*Heinrich, S. (2004), Quantum Approximation I. Embeddings of Finite Dimensional Lp
Spaces, J. Complexity, 20, 5–26. Also http://arXiv.org/quant-ph/0305030.
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. (2004), Randomized and quantum solution of initial value problems, to
appear in J. Complexity.
*Kwas, M., Complexity of multivariate Feynman-Kac Path Integration in Randomized and Quantum Settings, 2004, LANL preprint 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 Korobov Spaces on Classical and Quantum Computers, Journal of 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
teh Sturm-Liouville Eigenvalue Problem, Quantum Information Processing, 4, 87–127.
Also http://arXiv.org/quant-ph/0502054.
*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/quantph/
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.
| |||