Continuous quantum computation: Difference between revisions

Revision as of 16:23, 12 May 2017

Revision as of 16:31, 12 May 2017

Line 20:

In the standard model of quantum computation the probabilistic nature of quantum computation enters only through measurement; the queries are deterministic. In analogy with classical [[Monte Carlo method|Monte Carlo methods]], 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>\scriptstyle \log\varepsilon^{-1}</math>, thus achieving an exponential improvement over the qubit complexity in the standard quantum computing setting.<ref>{{Cite journal|last=Woźniakowski|first=H.|date=2006-04-01|title=The Quantum Setting with Randomized Queries for Continuous Problems|url=https://link.springer.com/article/10.1007/s11128-006-0013-6|journal=Quantum Information Processing|language=en|volume=5|issue=2|pages=83–130|arxiv=quant-ph/0601196|doi=10.1007/s11128-006-0013-6|issn=1570-0755}}</ref>

Besides path integration there have been numerous recent papers studying algorithms and quantum speedups for continuous problems. These include finding matrix [[Eigenvalues and eigenvectors|eigenvalues]],<ref>{{Cite journal|last=Jaksch|first=Peter|last2=Papageorgiou|first2=Anargyros|date=2003-12-19|title=Eigenvector Approximation Leading to Exponential Speedup of Quantum Eigenvalue Calculation|url=https://link.aps.org/doi/10.1103/PhysRevLett.91.257902|journal=Physical Review Letters|volume=91|issue=25|pages=257902|arxiv=quant-ph/0308016|doi=10.1103/PhysRevLett.91.257902}}</ref> phase estimation,<ref>{{Cite journal|last=Bessen|first=Arvid J.|date=2005-04-08|title=Lower bound for quantum phase estimation|url=https://link.aps.org/doi/10.1103/PhysRevA.71.042313|journal=Physical Review A|volume=71|issue=4|pages=042313|arxiv=quant-ph/0412008|doi=10.1103/PhysRevA.71.042313}}</ref> the Sturm–Liouville eigenvalue problem,<ref>{{Cite journal|last=Papageorgiou|first=A.|last2=Woźniakowski|first2=H|date=|title=Classical and Quantum Complexity of the Sturm–Liouville Eigenvalue Problem|url=http://link.springer.com/article/10.1007/s11128-005-4481-x|journal=Quantum Information Processing|language=en|volume=4|issue=2|pages=87–127|arxiv=quant-ph/0502054|doi=10.1007/s11128-005-4481-x}}</ref><ref>{{Cite journal|last=Papageorgiou|first=A.|last2=Woźniakowski|first2=H.|date=2007-04-01|title=The Sturm-Liouville Eigenvalue Problem and NP-Complete Problems in the Quantum Setting with Queries|url=https://link.springer.com/article/10.1007/s11128-006-0043-0|journal=Quantum Information Processing|language=en|volume=6|issue=2|pages=101–120|arxiv=quant-ph/0504191|doi=10.1007/s11128-006-0043-0|issn=1570-0755}}</ref> solving [[Differential equation|differential equations]] with the [[Feynman–Kac formula]],<ref>{{Cite journal|last=Kwas|first=Marek|date=2004-10-18|title=Complexity of multivariate Feynman-Kac path integration in randomized and quantum settings|url=http://arxiv.org/abs/quant-ph/0410134|journal=arXiv:quant-ph/0410134}}</ref> initial value problems,<ref>{{Cite journal|last=Kacewicz|first=Bolesław|title=Randomized and quantum algorithms yield a speed-up for initial-value problems|url=https://doi.org/10.1016/j.jco.2004.05.002|journal=Journal of Complexity|language=en|volume=20|issue=6|pages=821–834|doi=10.1016/j.jco.2004.05.002}}</ref><ref>{{Cite journal|last=Szczesny|first=Marek|date=2006-12-12|title=Randomized and Quantum Solution of Initial-Value Problems for Ordinary Differential Equations of Order k|url=http://arxiv.org/abs/quant-ph/0612085|journal=arXiv:quant-ph/0612085}}</ref><ref>{{Cite journal|last=Kacewicz|first=Bolesław|title=Improved bounds on the randomized and quantum complexity of initial-value problems|url=https://doi.org/10.1016/j.jco.2005.05.003|journal=Journal of Complexity|language=en|volume=21|issue=5|pages=740–756|doi=10.1016/j.jco.2005.05.003}}</ref> function approximation<ref>{{Cite journal|last=Novak|first=Erich|last2=Sloan|first2=Ian H.|last3=Wo’zniakowski|first3=Henryk|date=2004-04-01|title=Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers|url=https://link.springer.com/article/10.1007/s10208-002-0074-6|journal=Foundations of Computational Mathematics|language=en|volume=4|issue=2|pages=121–156|arxiv=quant-ph/0206023|doi=10.1007/s10208-002-0074-6|issn=1615-3375}}</ref><ref>{{Cite journal|last=Heinrich|first=Stefan|date=|title=Quantum approximation I. Embeddings of finite-dimensional Lp spaces|url=https://doi.org/10.1016/j.jco.2003.08.002|journal=Journal of Complexity|language=en|volume=20|issue=1|pages=5–26|arxiv=quant-ph/0305030|doi=10.1016/j.jco.2003.08.002}}</ref><ref>{{Cite journal|last=Heinrich|first=Stefan|date=|title=Quantum approximation II. Sobolev embeddings|url=https://doi.org/10.1016/j.jco.2003.08.003|journal=Journal of Complexity|language=en|volume=20|issue=1|pages=27–45|arxiv=quant-ph/0305031|doi=10.1016/j.jco.2003.08.003}}</ref> and high-dimensional integration.<ref>{{Cite journal|last=Heinrich|first=S.|date=|title=Quantum Summation with an Application to Integration|url=https://doi.org/10.1006/jcom.2001.0629|journal=Journal of Complexity|language=en|volume=18|issue=1|pages=1–50|arxiv=quant-ph/0105116|doi=10.1006/jcom.2001.0629}}</ref><ref>{{Cite journal|last=Heinrich|first=Stefan|date=2003-02-01|title=Quantum integration in Sobolev classes|url=http://www.sciencedirect.com/science/article/pii/S0885064X02000080|journal=Journal of Complexity|volume=19|issue=1|pages=19–42|arxiv=quant-ph/0112153|doi=10.1016/S0885-064X(02)00008-0}}</ref><ref>{{Cite journal|last=Novak|first=Erich|date=|title=Quantum Complexity of Integration|url=https://doi.org/10.1006/jcom.2000.0566|journal=Journal of Complexity|language=en|volume=17|issue=1|pages=2–16|arxiv=quant-ph/0008124|doi=10.1006/jcom.2000.0566}}</ref>

==External links==

Line 26:

==References==

*Heinrich, S. (2002), Quantum Summation with an Application to Integration, J. Complexity, 18(1), 1–50. Also [https://arXiv.org/abs/quant-ph/0105116 arXiv: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 <math>L_p</math> Spaces, J. Complexity, 20, 5–26. Also [https://arXiv.org/abs/quant-ph/0305030 arXiv:quant-ph/0305030].

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

{{Reflist}}