Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0311148 · Journal of Complexity

Randomized and quantum algorithms yield a speed-up for initial-value problems

Boleslaw Z. Kacewicz

Published Dec 1, 2004• 29 citations
arXivHTMLPDF
DOI
10.1016/j.jco.2004.05.002

Related papers

Almost optimal solution of initial-value problems by randomized and quantum algorithms

Boleslaw Z. Kacewicz

arXiv:quant-ph/0510045•Journal of Complexity•May 12, 2006•81 citations

Improved bounds on the randomized and quantum complexity of initial-value problems

Boleslaw Z. Kacewicz

arXiv:quant-ph/0405018•Journal of Complexity•Aug 27, 2005•18 citations

The randomized complexity of initial value problems

Stefan Heinrich, Bernhard Milla

Journal of Complexity•Sep 26, 2007•38 citations

Randomized and quantum algorithms for solving initial-value problems in ordinary differential equations of order k

Maciej Goćwin, Marek Szczęsny

The complexity of initial-value problems is well studied for systems of equations of first order. In this paper, we study the \(\varepsilon\)-complexity for initial-value problems for scalar equations of higher order. We consider two models of computation, the randomized model and the quantum model. We construct almost optimal algorithms adjusted to scalar equations of higher order, without passing to systems of first order equations. The analysis of these algorithms allows us to establish upper complexity bounds. We also show (almost) matching lower complexity bounds. The \(\varepsilon\)-complexity in the randomized and quantum setting depends on the regularity of the right-hand side function, but is independent of the order of equation. Comparing the obtained bounds with results known in the deterministic case, we see that randomized algorithms give us a speed-up by \(1/2\), and quantum algorithms by \(1\) in the exponent. Hence, the speed-up does not depend on the order of equation, and is the same as for the systems of equations of first order. We also include results of some numerical experiments which confirm theoretical results.

Opuscula Mathematica•Jan 1, 2008•4 citations

Randomized and Quantum Solution of Initial-Value Problems for Ordinary Differential Equations of Order k

Marek Szczęsny

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.

arXiv:quant-ph/0612085•Dec 13, 2006•0 citations

On the Relation Between Quantum Computational Speedup and Retrocausality

Giuseppe Castagnoli

We investigate the reason for the quantum speedup (quantum algorithms require fewer computation steps than their classical counterparts). We extend the representation of the quantum algorithm to the process of setting the problem, namely choosing the function computed by the black box. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. With reference to the observer dependent quantum states of relational quantum mechanics, this representation is with respect to Bob and any external observer, it cannot be with respect to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action, so that the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. Mathematically, we can ascribe to the final measurement the selection of any fraction R of the random outcome of the initial measurement. This projects the input state to Alice on one of lower entropy where she knows the corresponding fraction of the problem setting. Given the appropriate value of R, the quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given a quantum algorithm, this retrocausality model provides the value of R that explains its speed up; in the major quantum algorithms, R is 1/2 or slightly above it. Conversely, given the problem, R=1/2 always yields the order of magnitude of the number of black box computations required to solve it in an optimal quantum way. Quanta 2016; 5: 34–52.

Quanta•Jan 10, 2016•8 citations
The complexity of initial-value problems is well studied for systems of equations of first order. In this paper, we study the ε\varepsilonε-complexity for initial-value problems for scalar equations of higher order. We consider two models of computation, the randomized model and the quantum model. We construct almost optimal algorithms adjusted to scalar equations of higher order, without passing to systems of first order equations. The analysis of these algorithms allows us to establish upper complexity bounds. We also show (almost) matching lower complexity bounds. The ε\varepsilonε-complexity in the randomized and quantum setting depends on the regularity of the right-hand side function, but is independent of the order of equation. Comparing the obtained bounds with results known in the deterministic case, we see that randomized algorithms give us a speed-up by 1/21/21/2, and quantum algorithms by 111 in the exponent. Hence, the speed-up does not depend on the order of equation, and is the same as for the systems of equations of first order. We also include results of some numerical experiments which confirm theoretical results.
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.
We investigate the reason for the quantum speedup (quantum algorithms require fewer computation steps than their classical counterparts). We extend the representation of the quantum algorithm to the process of setting the problem, namely choosing the function computed by the black box. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. With reference to the observer dependent quantum states of relational quantum mechanics, this representation is with respect to Bob and any external observer, it cannot be with respect to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action, so that the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. Mathematically, we can ascribe to the final measurement the selection of any fraction R of the random outcome of the initial measurement. This projects the input state to Alice on one of lower entropy where she knows the corresponding fraction of the problem setting. Given the appropriate value of R, the quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given a quantum algorithm, this retrocausality model provides the value of R that explains its speed up; in the major quantum algorithms, R is 1/2 or slightly above it. Conversely, given the problem, R=1/2 always yields the order of magnitude of the number of black box computations required to solve it in an optimal quantum way. Quanta 2016; 5: 34–52.