dorsal/arxiv
View SchemaComplexity of multivariate Feynman-Kac path integration in randomized and quantum settings
| Authors | Marek Kwas |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0410134 |
| URL | https://arxiv.org/abs/quant-ph/0410134 |
Abstract
The Feynman-Kac path integration problem was studied in the worst case setting by Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate case and by Kwas and Li (J. Comp. 19 (2003) 730) for the multivariate case with d space variables. In this paper we consider the multivariate Feynman-Kac path integration problem in the randomized and quantum settings. For smooth multivariate functions, it was proven in Kwas and Li (2003) that the classical worst case complexity suffers from the curse of dimensionality in d. We show that in both the randomized and quantum settings the curse of dimensionality is vanquished, i.e., the number of function evaluations and/or quantum queries required to compute an e-approximation has a bound independent of d and depending polynomially on 1/e. The exponents of these polynomials are at most 2 in the randomized setting and at most 1 in the quantum setting. Hence we have exponential speedup over the classical worst case setting and quadratic speedup of the quantum setting over the randomized setting. However, both the randomized and quantum algorithms presented here still require extensive precomputing, similar to the algorithms of Plaskota et al. (2000) and Kwas and Li(2003).
{
"annotation_id": "d31cdb15-5601-4809-a2d6-e60c902f6941",
"date_created": "2026-03-02T18:02:10.339000Z",
"date_modified": "2026-03-02T18:02:10.339000Z",
"file_hash": "ebea538f0acfb785c6d8b0faf0db685865fa37c3bcba97026dea9e88b579fa86",
"private": false,
"record": {
"abstract": "The Feynman-Kac path integration problem was studied in the worst case\nsetting by Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate\ncase and by Kwas and Li (J. Comp. 19 (2003) 730) for the multivariate case with\nd space variables. In this paper we consider the multivariate Feynman-Kac path\nintegration problem in the randomized and quantum settings. For smooth\nmultivariate functions, it was proven in Kwas and Li (2003) that the classical\nworst case complexity suffers from the curse of dimensionality in d. We show\nthat in both the randomized and quantum settings the curse of dimensionality is\nvanquished, i.e., the number of function evaluations and/or quantum queries\nrequired to compute an e-approximation has a bound independent of d and\ndepending polynomially on 1/e. The exponents of these polynomials are at most 2\nin the randomized setting and at most 1 in the quantum setting. Hence we have\nexponential speedup over the classical worst case setting and quadratic speedup\nof the quantum setting over the randomized setting. However, both the\nrandomized and quantum algorithms presented here still require extensive\nprecomputing, similar to the algorithms of Plaskota et al. (2000) and Kwas and\nLi(2003).",
"arxiv_id": "quant-ph/0410134",
"authors": [
"Marek Kwas"
],
"categories": [
"quant-ph"
],
"title": "Complexity of multivariate Feynman-Kac path integration in randomized and quantum settings",
"url": "https://arxiv.org/abs/quant-ph/0410134"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1f328d0b-9200-4e94-b7e4-e470ba4e479b",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}