Path Integration on a Quantum Computer

Joseph F. Traub and Henryk Wozniakowski

Working Papers from Santa Fe Institute

Abstract: We study path integration on a quantum computer that performs quantum summation. We assume that the measure of path integration is Gaussian, with the eigenvalues of its covariance operator of order j^{-k} with k>1. For the Wiener measure occurring in many applications we have k=2. We want to compute an e-approximation to path integrals whose integrands are at least Lipschitz. We prove: 1. Path integration on a quantum computer is tractable. 2. Path integration on a quantum computer can be solved roughly e^{-1} times faster than on a classical computer using randomization, and exponentially faster than on a classical computer with a worst case assurance. 3. The number of quantum queries is the square root of the number of function values needed on a classical computer using randomization. 4.The number of qubits is polynomial in e^{-1}. Furthermore, for the Wiener measure the degree is 2 for Lipschitz functions, and the degree is 1 for smoother integrands.

Keywords: Quantum computation; path integration; quantum summation; qubits; computational complexity (search for similar items in EconPapers)
Date: 2001-10
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:01-10-055

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().