dorsal/arxiv
View SchemaPath Integration on a Quantum Computer
| Authors | J. F. Traub, H. Wozniakowski |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0109113 |
| URL | https://arxiv.org/abs/quant-ph/0109113 |
| Journal | Quantum Information Processing 1(5), 365-388, Oct. 2002 |
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. More precisely, the number of quantum queries is at most $4.22 \e^{-1}$. Furthermore, a lower bound is obtained for the minimal number of quantum queries which shows that this bound cannot be significantly improved. 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.
{
"annotation_id": "d7b89ae6-bad4-4f64-8901-066d692fb478",
"date_created": "2026-03-02T18:01:46.029000Z",
"date_modified": "2026-03-02T18:01:46.029000Z",
"file_hash": "23fbc314e31ba1c0c1b85c46d699c498fd6a2aaa82a897a9639d0da761a97578",
"private": false,
"record": {
"abstract": "We study path integration on a quantum computer that performs quantum\nsummation. We assume that the measure of path integration is Gaussian, with the\neigenvalues of its covariance operator of order j^{-k} with k\u003e1. For the Wiener\nmeasure occurring in many applications we have k=2. We want to compute an\n$\\e$-approximation to path integrals whose integrands are at least Lipschitz.\nWe prove:\n 1. Path integration on a quantum computer is tractable.\n 2. Path integration on a quantum computer can be solved roughly $\\e^{-1}$\ntimes faster than on a classical computer using randomization, and\nexponentially faster than on a classical computer with a worst case assurance.\n 3.The number of quantum queries is the square root of the number of function\nvalues needed on a classical computer using randomization. More precisely, the\nnumber of quantum queries is at most $4.22 \\e^{-1}$. Furthermore, a lower bound\nis obtained for the minimal number of quantum queries which shows that this\nbound cannot be significantly improved.\n 4.The number of qubits is polynomial in $\\e^{-1}$. Furthermore, for the\nWiener measure the degree is 2 for Lipschitz functions, and the degree is 1 for\nsmoother integrands.",
"arxiv_id": "quant-ph/0109113",
"authors": [
"J. F. Traub",
"H. Wozniakowski"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quantum Information Processing 1(5), 365-388, Oct. 2002",
"title": "Path Integration on a Quantum Computer",
"url": "https://arxiv.org/abs/quant-ph/0109113"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "36412ef5-4df0-4052-82de-94555f4dfb25",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}