dorsal/arxiv
View SchemaRandomized and Quantum Solution of Initial-Value Problems for Ordinary Differential Equations of Order k
| Authors | Marek Szczesny |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0612085 |
| URL | https://arxiv.org/abs/quant-ph/0612085 |
Abstract
We study possible advantages of randomized and quantum computing over deterministic computing for scalar initial-value problems for ordinary differential equations of order k. For systems of equations of the first order this question has been settled modulo some details in \cite{Kacewicz05}. A speed-up over deterministic computing shown in \cite{Kacewicz05} is related to the increased regularity of the solution with respect to that of the right-hand side function. For a scalar equation of order k (which can be transformed into a special system of the first order), the regularity of the solution is increased by k orders of magnitude. This leads to improved complexity bounds depending on k for linear information in the deterministic setting, see \cite{Szczesny05}. This may suggest that in the randomized and quantum settings a speed-up can also be achieved depending on k. We show in this paper that a speed-up dependent on k is not possible in the randomized and quantum settings. We establish lower complexity bounds, showing that the randomized and quantum complexities remain at the some level as for systems of the first order, no matter how large k is. Thus, the algorithms from \cite{Kacewicz05} remain (almost) optimal, even if we restrict ourselves to a subclass of systems arising from scalar equations of order k.
{
"annotation_id": "a6d11f7e-bb45-44fc-8786-897b7fbb9d3c",
"date_created": "2026-03-02T18:02:34.500000Z",
"date_modified": "2026-03-02T18:02:34.500000Z",
"file_hash": "2b68445822737c84311986ab9e70bd79aebcbc4b08e16094a22a0dc9d90397ba",
"private": false,
"record": {
"abstract": "We study possible advantages of randomized and quantum computing over\ndeterministic computing for scalar initial-value problems for ordinary\ndifferential equations of order k. For systems of equations of the first order\nthis question has been settled modulo some details in \\cite{Kacewicz05}. A\nspeed-up over deterministic computing shown in \\cite{Kacewicz05} is related to\nthe increased regularity of the solution with respect to that of the right-hand\nside function. For a scalar equation of order k (which can be transformed into\na special system of the first order), the regularity of the solution is\nincreased by k orders of magnitude. This leads to improved complexity bounds\ndepending on k for linear information in the deterministic setting, see\n\\cite{Szczesny05}. This may suggest that in the randomized and quantum settings\na speed-up can also be achieved depending on k.\n We show in this paper that a speed-up dependent on k is not possible in the\nrandomized and quantum settings. We establish lower complexity bounds, showing\nthat the randomized and quantum complexities remain at the some level as for\nsystems of the first order, no matter how large k is. Thus, the algorithms from\n\\cite{Kacewicz05} remain (almost) optimal, even if we restrict ourselves to a\nsubclass of systems arising from scalar equations of order k.",
"arxiv_id": "quant-ph/0612085",
"authors": [
"Marek Szczesny"
],
"categories": [
"quant-ph"
],
"title": "Randomized and Quantum Solution of Initial-Value Problems for Ordinary Differential Equations of Order k",
"url": "https://arxiv.org/abs/quant-ph/0612085"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "ca3824a3-5ba4-45f7-a1cb-9b3511aeea61",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}