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/0510045 · Journal of Complexity

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

Boleslaw Z. Kacewicz

Published May 12, 2006• 81 citations
arXivHTMLPDF
DOI
10.1016/j.jco.2006.03.001

Related papers

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

Boleslaw Z. Kacewicz

arXiv:quant-ph/0311148•Journal of Complexity•Dec 1, 2004•29 citations

A retrocausal model of the quantum computational speedup

Giuseppe Castagnoli

We extend the representation of quantum algorithms to the preparation of the problem setting. An initial measurement serves to set the problem, the final one as usual to read the solution. This extension highlights the possibility of ascribing the selection of a variable fraction R of the information that specifies the random outcome of the initial measurement to the final measurement. The input state of the quantum algorithm to the problem solver (Alice), of maximal ignorance of the problem setting that to her should be hidden, would consequently be projected on a state of lower entropy where she knows in advance an R-th part of the setting (i. e. of the information that specifies it). Given the appropriate value of R, the quantum algorithm turns out to be a sum over classical histories in each of which Alice knows in advance one of the possible R-th parts of the problem setting and performs the Q(R) computations (oracle queries) still needed to find the solution. Grover's search problem can be solved with any value of R from 0 to about 1/2, when the solution algorithm becomes the optimal Grover algorithm. In all the optimal quantum algorithms examined, R is close to 1/2 and Q(1/2) yields the order of magnitude of the number of queries. If this held in general, as it seems to be plausible, given any oracle problem we would know the order of magnitude of the number of queries needed for its optimal quantum solution.

arXiv:1603.02246•Mar 7, 2016•1 citation

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

An Improved Quantum Evolutionary Algorithm for High Dimension Knapsack Problem

Hao Li, Lei Ma, Na Qin

Knapsack problem is a typical combinatorial optimization problem, which has attracted wide attention because of its simple description, difficult solution and wide application background. For the knapsack problem, we proposed an improved quantum evolutionary algorithm. In this algorithm, the qubits are initialized according to the value densities of their corresponding items, the angle of Q-gate is determinated through direct comparison between the quantum chromosome and the optimal solution, random crossover method is taken to share information among chromosomes, and Hϵ gate is used to prevent from premature convergence. Finally, experiment demonstrates the effectiveness of the algorithm.

Frontiers in artificial intelligence and applications•Jan 1, 2017•0 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

The randomized complexity of initial value problems

Stefan Heinrich, Bernhard Milla

Journal of Complexity•Sep 26, 2007•38 citations
We extend the representation of quantum algorithms to the preparation of the problem setting. An initial measurement serves to set the problem, the final one as usual to read the solution. This extension highlights the possibility of ascribing the selection of a variable fraction R of the information that specifies the random outcome of the initial measurement to the final measurement. The input state of the quantum algorithm to the problem solver (Alice), of maximal ignorance of the problem setting that to her should be hidden, would consequently be projected on a state of lower entropy where she knows in advance an R-th part of the setting (i. e. of the information that specifies it). Given the appropriate value of R, the quantum algorithm turns out to be a sum over classical histories in each of which Alice knows in advance one of the possible R-th parts of the problem setting and performs the Q(R) computations (oracle queries) still needed to find the solution. Grover's search problem can be solved with any value of R from 0 to about 1/2, when the solution algorithm becomes the optimal Grover algorithm. In all the optimal quantum algorithms examined, R is close to 1/2 and Q(1/2) yields the order of magnitude of the number of queries. If this held in general, as it seems to be plausible, given any oracle problem we would know the order of magnitude of the number of queries needed for its optimal quantum solution.
Knapsack problem is a typical combinatorial optimization problem, which has attracted wide attention because of its simple description, difficult solution and wide application background. For the knapsack problem, we proposed an improved quantum evolutionary algorithm. In this algorithm, the qubits are initialized according to the value densities of their corresponding items, the angle of Q-gate is determinated through direct comparison between the quantum chromosome and the optimal solution, random crossover method is taken to share information among chromosomes, and Hϵ gate is used to prevent from premature convergence. Finally, experiment demonstrates the effectiveness of the algorithm.
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.