Continuous quantum computation: Difference between revisions

Revision as of 16:47, 9 May 2017

Revision as of 17:23, 9 May 2017

Line 15:

One example of a scientific problem that is naturally expressed in continuous terms is [[path integration]]. The general technique of path integration has numerous applications including [[quantum mechanics]], [[quantum chemistry]], [[statistical mechanics]], and [[computational finance]]. Because randomness is present throughout quantum theory, one typically requires that a quantum computational procedure yield the correct answer, not with certainty, but with high probability. For example, one might aim for a procedure that computes the correct answer with probability at least 3/4. In the case of continuous-variable quantum computation, one also specifies a degree of uncertainty, typically by setting the maximum acceptable error. Thus, the goal of a continuous-variable quantum computation could be to compute the numerical result of a path-integration problem to within an error of at most ε with probability 3/4 or more. In this context, it is known<ref>{{Cite journal|last=Traub|first=J. F.|last2=Woźniakowski|first2=H.|date=2002-10-01|title=Path Integration on a Quantum Computer|url=https://link.springer.com/article/10.1023/A:1023417813916|journal=Quantum Information Processing|language=en|volume=1|issue=5|pages=365–388|arxiv=quant-ph/0109113|doi=10.1023/A:1023417813916|issn=1570-0755}}</ref> that quantum algorithms can outperform their classical counterparts, and the computational complexity of the problem, as measured by the number of times one would expect to have to query a quantum computer to get a good answer, grows as the inverse of ε.

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 [http://arXiv.org/quant-ph/0601196 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]], phase estimation, the Sturm–Liouville eigenvalue problem, solving [[Differential equation|differential equations]] with the [[Feynman–Kac formula]], initial value problems, function approximation and high-dimensional integration.