Continuous quantum computation

Continuous-variable quantum computation, also called continuous quantum computation, is the area of quantum computation that makes use of physical observables, like the strength of an electromagnetic field, whose numerical values belong to continuous intervals. In a sense, continuous-variable quantum computation is "analogue," while quantum computation using qubits is "digital." In more technical terms, the former makes use of Hilbert spaces that are infinite-dimensional, while the Hilbert spaces for systems comprising collections of qubits are finite-dimensional. One major motivation for studying continuous-variable quantum computation is that many scientific problems have mathematical formulations that are naturally continuous in character. Another motivation is to understand in what ways quantum computers are more capable or more powerful than classical computers.

Applications

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 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, Woźniakowski introduced the idea of a quantum setting with randomized queries. He showed that in this setting the qubit complexity is of order $\scriptstyle \log \varepsilon ^{-1}$, thus achieving an exponential improvement over the qubit complexity in the standard quantum computing setting.

Besides path integration there have been numerous recent papers studying algorithms and quantum speedups for continuous problems. These include finding matrix eigenvalues, phase estimation, the Sturm–Liouville eigenvalue problem, solving differential equations with the Feynman–Kac formula, initial value problems, function approximation and high-dimensional integration.

External links

• http://quantum.cs.columbia.edu – Continuous quantum computing web page at Columbia University

References

• Bessen, A. J. (2005), A lower bound for phase estimation, Physical Review A, 71(4), 042313. Also arXiv:quant-ph/0412008.
• Heinrich, S. (2002), Quantum Summation with an Application to Integration, J. Complexity, 18(1), 1–50. Also 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 $L_{p}$ Spaces, J. Complexity, 20, 5–26. Also arXiv:quant-ph/0305030.
• Heinrich, S. (2004), Quantum Approximation II. Sobolev Embeddings, J. Complexity, 20, 27–45. Also arXiv: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 arXiv:quant-ph/0308016.
• Kacewicz, B. Z. (2005), Randomized and quantum solution of initial value problems, J. Complexity, 21, 740–756.
• Kwas, M., Complexity of multivariate Feynman–Kac Path Integration in Randomized and Quantum settings, 2004. Also arXiv:quant-ph/0410134.
• Novak, E. (2001), Quantum complexity of integration, J. Complexity, 17, 2–16. Also arXiv:quant-ph/0008124.
• Novak, E., Sloan, I. H., and Wozniakowski, H., Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers, J. Foundations of Computational Mathematics, 4, 121-156, 2004. Also arXiv:quant-ph/0206023
• Papageorgiou, A. and Wo´zniakowski, H. (2005), Classical and Quantum Complexity of the Sturm–Liouville Eigenvalue Problem, Quantum Information Processing, 4(2), 87–127. Also arXiv:quant-ph/0502054.
• 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 arXiv:quant-ph/0504194.
• Traub, J. F. and Woźniakowski, H. (2002), Path integration on a quantum computer, Quantum Information Processing, 1(5), 365–388, 2002. Also arXiv:quant-ph/0109113.
• Woźniakowski, H. (2006), The Quantum Setting with Randomized Queries for Continuous Problems, Quantum Information Processing, 5(2), 83–130. Also arXiv:quant-ph/0601196.