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

Communications in Theoretical Physics

Success Rate Versus Finite Run Time in Local Adiabatic Quantum Search Algorithm*

Feng‐Guang Li, Wan‐Su Bao, Xiang 翔 Wang 汪, Xiang-Qun Fu, Shuo Zhang, Yu-Tao 宇韬 Du 杜, Tan 坦 Li 李, Bo-wen Ma

Published Apr 1, 2017• 2 citations
Publisher

Abstract

Abstract In adiabatic quantum algorithm, the success rate is approximately equal to 1 while the run time satisfies the adiabatic condition. But the relation between the short run time and success rate for adiabatic quantum algorithm is poorly understood. In this paper, we study the success rate of local adiabatic quantum search algorithm with an arbitrary finite run time (non-adiabatic evolution). By solving the time-independent Schrödinger equation, we obtain differential equations to calculate the success rate. The differential equations show that the success rate is closely related to the adiabatic parameter s t . Utilize the differential equations, we give the function of success rate versus run time in local adiabatic search numerically. The result indirectly verifies that T ∼ O ( N ) is optimal in local adiabatic search.

DOI
10.1088/0253-6102/67/4/355

Related papers

Accuracy versus run time in an adiabatic quantum search

A. T. Rezakhani, Artem Pimachev, Daniel A. Lidar

Adiabatic quantum algorithms are characterized by their run time and accuracy. The relation between the two is essential for quantifying adiabatic algorithmic performance yet is often poorly understood. We study the dynamics of a continuous time, adiabatic quantum search algorithm and find rigorous results relating the accuracy and the run time. Proceeding with estimates, we show that under fairly general circumstances the adiabatic algorithmic error exhibits a behavior with two discernible regimes: The error decreases exponentially for short times and then decreases polynomially for longer times. We show that the well-known quadratic speedup over classical search is associated only with the exponential error regime. We illustrate the results through examples of evolution paths derived by minimization of the adiabatic error. We also discuss specific strategies for controlling the adiabatic error and run time.

arXiv:1008.0863•Physical Review A•Nov 9, 2010•73 citations

Transitionless driving on local adiabatic quantum search algorithm

Feng‐Guang Li, Wan‐Su Bao, Shuo Zhang +4 more

We apply the transitionless driving on the local adiabatic quantum search algorithm to speed up the adiabatic process. By studying quantum dynamics of the adiabatic search algorithm with the equivalent two-level system, we derive the transitionless driving Hamiltonian for the local adiabatic quantum search algorithm. We found that when adding a transitionless quantum driving term H D ( t ) on the local adiabatic quantum search algorithm, the success rate is 1 exactly with arbitrary evolution time by solving the time-dependent Schr¨odinger equation in eigen-picture. Moreover, we show the reason for the drastic decrease of the evolution time is that the driving Hamiltonian increases the lowest eigenvalues to a maximum of O ( N ) .

Chinese Physics B•Jan 1, 2018•3 citations

On the Success Probability of Quantum Partial Adiabatic Search

Jie Sun

ABSTRACT In this paper, we revisit the problem of success probability of quantum partial adiabatic search algorithms, which has been studied in a series of our prior works. The conclusions presented here can be divided into positive and negative aspects. On the one hand, for the quantum partial adiabatic evolution with time complexity of , where and denote the sizes of the total elements and the target elements in the search problem, respectively, our choice of narrow evolution paths in the related papers is in fact acceptable. This is reflected in the finite success probability of the quantum algorithm. On the other hand, for the quantum partial adiabatic computation (QPAC) with time complexity of , the choice of narrow evolution paths in the previous paper is indeed invalid, as evidenced by the low success probability. These findings demonstrate that previous criticisms of our work are not fully justified, and they highlight the necessity of a careful treatment of success probability calculations in quantum partial adiabatic evolutions.

Annalen der Physik•Oct 1, 2026•0 citations

Quantum search by local adiabatic evolution

Jérémie Roland, Nicolas J. Cerf

The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the quantum computer evolves slowly enough so that it remains near its instantaneous ground state, which tends to the solution. We apply this time-dependent Hamiltonian approach to Grover's problem, i.e., searching a marked item in an unstructured database. We find that by adjusting the evolution rate of the Hamiltonian so as to keep the evolution adiabatic on each infinitesimal time interval, the total running time is of order $\sqrt{N},$ where N is the number of items in the database. We thus recover the advantage of Grover's standard algorithm as compared to a classical search, scaling as N. This is in contrast with the constant-rate adiabatic approach of Farhi et al. (e-print quant-ph/0001106), where the requirement of adiabaticity is expressed only globally, resulting in a time of order N.

arXiv:quant-ph/0107015•Physical Review A•Mar 26, 2002•664 citations

Dynamics of adiabatic quantum search

Artem Pimachev

We describe a class of the Hamiltonians, for which the local adiabaticity condition is satisfied automatically. We consider the controllable adiabatic interpolations between the initial and final Hamiltonians. We show that the quantum search by the adiabatic quantum computation can be mapped into this class. Assuming that the interpolation is infinitely differentiable and the target adiabatic ground state is nondegenerate and separated by a gap from the rest of the spectrum, it is shown that one can obtain an exponentially small error in the algorithm run time T betweenthe finale adiabatic eigenstate and the actual state of the system. The optimal for quantum search scaling of T as square root of the system size is also satisfied.

•Jan 1, 2015•0 citations

A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.

arXiv:quant-ph/0007071•Jul 19, 2000•74 citations
Abstract In adiabatic quantum algorithm, the success rate is approximately equal to 1 while the run time satisfies the adiabatic condition. But the relation between the short run time and success rate for adiabatic quantum algorithm is poorly understood. In this paper, we study the success rate of local adiabatic quantum search algorithm with an arbitrary finite run time (non-adiabatic evolution). By solving the time-independent Schrödinger equation, we obtain differential equations to calculate the success rate. The differential equations show that the success rate is closely related to the adiabatic parameter s t . Utilize the differential equations, we give the function of success rate versus run time in local adiabatic search numerically. The result indirectly verifies that T ∼ O ( N ) is optimal in local adiabatic search.
Adiabatic quantum algorithms are characterized by their run time and accuracy. The relation between the two is essential for quantifying adiabatic algorithmic performance yet is often poorly understood. We study the dynamics of a continuous time, adiabatic quantum search algorithm and find rigorous results relating the accuracy and the run time. Proceeding with estimates, we show that under fairly general circumstances the adiabatic algorithmic error exhibits a behavior with two discernible regimes: The error decreases exponentially for short times and then decreases polynomially for longer times. We show that the well-known quadratic speedup over classical search is associated only with the exponential error regime. We illustrate the results through examples of evolution paths derived by minimization of the adiabatic error. We also discuss specific strategies for controlling the adiabatic error and run time.
We apply the transitionless driving on the local adiabatic quantum search algorithm to speed up the adiabatic process. By studying quantum dynamics of the adiabatic search algorithm with the equivalent two-level system, we derive the transitionless driving Hamiltonian for the local adiabatic quantum search algorithm. We found that when adding a transitionless quantum driving term H D ( t ) on the local adiabatic quantum search algorithm, the success rate is 1 exactly with arbitrary evolution time by solving the time-dependent Schr¨odinger equation in eigen-picture. Moreover, we show the reason for the drastic decrease of the evolution time is that the driving Hamiltonian increases the lowest eigenvalues to a maximum of O ( N ) .
ABSTRACT In this paper, we revisit the problem of success probability of quantum partial adiabatic search algorithms, which has been studied in a series of our prior works. The conclusions presented here can be divided into positive and negative aspects. On the one hand, for the quantum partial adiabatic evolution with time complexity of , where and denote the sizes of the total elements and the target elements in the search problem, respectively, our choice of narrow evolution paths in the related papers is in fact acceptable. This is reflected in the finite success probability of the quantum algorithm. On the other hand, for the quantum partial adiabatic computation (QPAC) with time complexity of , the choice of narrow evolution paths in the previous paper is indeed invalid, as evidenced by the low success probability. These findings demonstrate that previous criticisms of our work are not fully justified, and they highlight the necessity of a careful treatment of success probability calculations in quantum partial adiabatic evolutions.
The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the quantum computer evolves slowly enough so that it remains near its instantaneous ground state, which tends to the solution. We apply this time-dependent Hamiltonian approach to Grover's problem, i.e., searching a marked item in an unstructured database. We find that by adjusting the evolution rate of the Hamiltonian so as to keep the evolution adiabatic on each infinitesimal time interval, the total running time is of order N,\sqrt{N},N​, where N is the number of items in the database. We thus recover the advantage of Grover's standard algorithm as compared to a classical search, scaling as N. This is in contrast with the constant-rate adiabatic approach of Farhi et al. (e-print quant-ph/0001106), where the requirement of adiabaticity is expressed only globally, resulting in a time of order N.
We describe a class of the Hamiltonians, for which the local adiabaticity condition is satisfied automatically. We consider the controllable adiabatic interpolations between the initial and final Hamiltonians. We show that the quantum search by the adiabatic quantum computation can be mapped into this class. Assuming that the interpolation is infinitely differentiable and the target adiabatic ground state is nondegenerate and separated by a gap from the rest of the spectrum, it is shown that one can obtain an exponentially small error in the algorithm run time T betweenthe finale adiabatic eigenstate and the actual state of the system. The optimal for quantum search scaling of T as square root of the system size is also satisfied.
Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.