dorsal/arxiv
View SchemaImproved Bounds on the Randomized and Quantum Complexity of Initial-Value Problems
| Authors | Boleslaw Kacewicz |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0405018 |
| URL | https://arxiv.org/abs/quant-ph/0405018 |
| Journal | Journal of Complexity 21 (2005), 740-756 |
Abstract
We deal with the problem, initiated in [8], of finding randomized and quantum complexity of initial-value problems. We showed in [8] that a speed-up in both settings over the worst-case deterministic complexity is possible. In the present paper we prove, by defining new algorithms, that further improvement in upper bounds on the randomized and quantum complexity can be achieved. In the H\"older class of right-hand side functions with r continuous bounded partial derivatives, with r-th derivative being a H\"older function with exponent \rho, the \epsilon-complexity is shown to be O((1/\epsilon)^{1/(r+\rho+1/3)}) in the randomized setting, and O((1/\epsilon)^{1/(r+\rho+1/2)}) on a quantum computer (up to logarithmic factors). This is an improvement for the general problem over the results from [8]. The gap still remaining between upper and lower bounds on the complexity is further discussed for a special problem. We consider scalar autonomous problems, with the aim of computing the solution at the end point of the interval of integration. For this problem, we fill up the gap by establishing (essentially) matching upper and lower complexity bounds. We show that the complexity in this case is of order (1/\epsilon)^{1/(r+\rho+1/2)} in the randomized setting, and (1/\epsilon)^{1/(r+\rho+1)} in the quantum setting (again up to logarithmic factors).
{
"annotation_id": "d093dc13-c51a-4107-9d9a-fa8944df14de",
"date_created": "2026-03-02T18:02:07.053000Z",
"date_modified": "2026-03-02T18:02:07.053000Z",
"file_hash": "3a26acefee396e210560361ee8bc8720725edf4ce2c168e10f5ce392c6080c16",
"private": false,
"record": {
"abstract": "We deal with the problem, initiated in [8], of finding randomized and quantum\ncomplexity of initial-value problems. We showed in [8] that a speed-up in both\nsettings over the worst-case deterministic complexity is possible. In the\npresent paper we prove, by defining new algorithms, that further improvement in\nupper bounds on the randomized and quantum complexity can be achieved. In the\nH\\\"older class of right-hand side functions with r continuous bounded partial\nderivatives, with r-th derivative being a H\\\"older function with exponent \\rho,\nthe \\epsilon-complexity is shown to be O((1/\\epsilon)^{1/(r+\\rho+1/3)}) in the\nrandomized setting, and O((1/\\epsilon)^{1/(r+\\rho+1/2)}) on a quantum computer\n(up to logarithmic factors). This is an improvement for the general problem\nover the results from [8]. The gap still remaining between upper and lower\nbounds on the complexity is further discussed for a special problem. We\nconsider scalar autonomous problems, with the aim of computing the solution at\nthe end point of the interval of integration. For this problem, we fill up the\ngap by establishing (essentially) matching upper and lower complexity bounds.\nWe show that the complexity in this case is of order\n(1/\\epsilon)^{1/(r+\\rho+1/2)} in the randomized setting, and\n(1/\\epsilon)^{1/(r+\\rho+1)} in the quantum setting (again up to logarithmic\nfactors).",
"arxiv_id": "quant-ph/0405018",
"authors": [
"Boleslaw Kacewicz"
],
"categories": [
"quant-ph"
],
"journal_ref": "Journal of Complexity 21 (2005), 740-756",
"title": "Improved Bounds on the Randomized and Quantum Complexity of Initial-Value Problems",
"url": "https://arxiv.org/abs/quant-ph/0405018"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cde4fdf4-e331-4259-85a4-59be86db91fb",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}