dorsal/arxiv
View SchemaRandomized and Quantum Algorithms Yield a Speed-Up for Initial-Value Problems
| Authors | Boleslaw Kacewicz |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0311148 |
| URL | https://arxiv.org/abs/quant-ph/0311148 |
| Journal | Journal of Complexity 20 (2004) 821-834 |
Abstract
Quantum algorithms and complexity have recently been studied not only for discrete, but also for some numerical problems. Most attention has been paid so far to the integration problem, for which a speed-up is shown by quantum computers with respect to deterministic and randomized algorithms on a classical computer. In this paper we deal with the randomized and quantum complexity of initial-value problems. For this nonlinear problem, we show that both randomized and quantum algorithms yield a speed-up over deterministic algorithms. Upper bounds on the complexity in the randomized and quantum settings are shown by constructing algorithms with a suitable cost, where the construction is based on integral information. Lower bounds result from the respective bounds for the integration problem.
{
"annotation_id": "b3b45fe4-9a21-448d-a662-7c93927b9d3d",
"date_created": "2026-03-02T18:02:02.868000Z",
"date_modified": "2026-03-02T18:02:02.868000Z",
"file_hash": "c351d815c666553ce198d25d1418014af5b9a3fe6a52524d60c0651ce44c51e7",
"private": false,
"record": {
"abstract": "Quantum algorithms and complexity have recently been studied not only for\ndiscrete, but also for some numerical problems. Most attention has been paid so\nfar to the integration problem, for which a speed-up is shown by quantum\ncomputers with respect to deterministic and randomized algorithms on a\nclassical computer. In this paper we deal with the randomized and quantum\ncomplexity of initial-value problems. For this nonlinear problem, we show that\nboth randomized and quantum algorithms yield a speed-up over deterministic\nalgorithms. Upper bounds on the complexity in the randomized and quantum\nsettings are shown by constructing algorithms with a suitable cost, where the\nconstruction is based on integral information. Lower bounds result from the\nrespective bounds for the integration problem.",
"arxiv_id": "quant-ph/0311148",
"authors": [
"Boleslaw Kacewicz"
],
"categories": [
"quant-ph"
],
"journal_ref": "Journal of Complexity 20 (2004) 821-834",
"title": "Randomized and Quantum Algorithms Yield a Speed-Up for Initial-Value Problems",
"url": "https://arxiv.org/abs/quant-ph/0311148"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5b9bce10-31cd-40d1-96ff-f078ea6502a2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}