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•69 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•629 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•44 citations

A quantum partial adiabatic evolution and its application to quantum search problem

Jie Sun, Hui Zheng, Songfeng Lu

This paper presents a framework for quantum partial adiabatic evolution and applies it to re-examine the well-known quantum search problem. We particularly focus on a detailed analysis of the algorithm’s success probability, which serves as a clear criterion for differentiating valid implementations from invalid ones. Specifically, when the time complexity aligns with the optimal quantum computation, the algorithm achieves a substantially high success probability. Conversely, so-called “improved” versions that exceed the quadratic speedup characteristic of quantum computing exhibit a negligibly low success probability with the increase of target elements. These findings underscore the critical importance of selecting the appropriate evolution interval and the correct method for calculating the success probability in studies of quantum partial adiabatic evolution.

Frontiers in Physics•Jan 8, 2026•2 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.
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.
This paper presents a framework for quantum partial adiabatic evolution and applies it to re-examine the well-known quantum search problem. We particularly focus on a detailed analysis of the algorithm’s success probability, which serves as a clear criterion for differentiating valid implementations from invalid ones. Specifically, when the time complexity aligns with the optimal quantum computation, the algorithm achieves a substantially high success probability. Conversely, so-called “improved” versions that exceed the quadratic speedup characteristic of quantum computing exhibit a negligibly low success probability with the increase of target elements. These findings underscore the critical importance of selecting the appropriate evolution interval and the correct method for calculating the success probability in studies of quantum partial adiabatic evolution.