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

Chinese Physics B

A quantum search algorithm based on partial adiabatic evolution

Yingyu Zhang, Heping Hu, Songfeng Lu

Published Apr 1, 2011• 13 citations
Publisher

Abstract

This paper presents and implements a specified partial adiabatic search algorithm on a quantum circuit. It studies the minimum energy gap between the first excited state and the ground state of the system Hamiltonian and it finds that, in the case of M = 1, the algorithm has the same performance as the local adiabatic algorithm. However, the algorithm evolves globally only within a small interval, which implies that it keeps the advantages of global adiabatic algorithms without losing the speedup of the local adiabatic search algorithm.

DOI
10.1088/1674-1056/20/4/040309

Related papers

Partial evolution based local adiabatic quantum search

Jie Sun, Songfeng Lu, Fang Liu +1 more

Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308 ], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original "global" one, this "new" algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M = 1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.

Chinese Physics B•Jan 1, 2012•12 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

Invalid quantum partial adiabatic search can be remedied

Jie Sun, Hui Zheng, Zhiming Zhang +1 more

This paper first demonstrates that by appropriately specifying the evolution interval in quantum partial adiabatic evolution, the time complexity of the resulting quantum search algorithm can achieve the well-known quadratic speedup bound of quantum computation. Then this result is used as a reference to remedy invalid quantum partial adiabatic search schemes, which means its time complexity doesn’t align with the optimal quantum speedup. And, it is found that the two versions of quantum partial adiabatic evolutions, i.e. “global” and “local” ones must be treated separately, despite previous studies indicating only minor differences in algorithmic performance between the two cases. Additionally, for the “local” variant of the quantum partial adiabatic search algorithm, it can be seen that there are other possible choices for the evolution interval besides the referred one. Our findings further show that significant variations in the resulting single-round success probabilities occur between valid and invalid quantum partial adiabatic evolutions.

International Journal of Quantum Information•Jan 14, 2026•1 citation

Quantum-circuit model of Hamiltonian search algorithms

Jérémie Roland, Nicolas J. Cerf

We analyze three different quantum search algorithms, namely, the traditional circuit-based Grover's algorithm, its continuous-time analog by Hamiltonian evolution, and the quantum search by local adiabatic evolution. We show that these algorithms are closely related in the sense that they all perform a rotation, at a constant angular velocity, from a uniform superposition of all states to the solution state. This makes it possible to implement the two Hamiltonian-evolution algorithms on a conventional quantum circuit, while keeping the quadratic speedup of Grover's original algorithm. It also clarifies the link between the adiabatic search algorithm and Grover's algorithm.

arXiv:quant-ph/0302138•Physical Review A•Dec 15, 2003•45 citations

Adiabatic quantum computation with a one-dimensional projector Hamiltonian

Avatar Tulsi

Adiabatic quantum computation is based on the adiabatic evolution of quantum systems. We analyze a particular class of quantum adiabatic evolutions where either the initial or final Hamiltonian is a one-dimensional projector Hamiltonian on the corresponding ground state. The minimum-energy gap, which governs the time required for a successful evolution, is shown to be proportional to the overlap of the ground states of the initial and final Hamiltonians. We show that such evolutions exhibit a rapid crossover as the ground state changes abruptly near the transition point where the energy gap is minimum. Furthermore, a faster evolution can be obtained by performing a partial adiabatic evolution within a narrow interval around the transition point. These results generalize and quantify earlier works.

arXiv:0806.0385•Physical Review A•Nov 23, 2009•27 citations

Speedup in Quantum Adiabatic Evolution Algorithm

Joonwoo Bae, Younghun Kwon

The quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving NPcomplete problems. The algorithm is governed by the adiabatic theorem. Therefore, in order to reduce the running time, it is essential to examine the minimum energy gap between the ground level and the next one in the evolution. In this paper we show a way of speedup in the quantum adiabatic evolution algorithm, using an extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides a new point of view to reduce the running time.

arXiv:quant-ph/0205048•Zeitschrift für Naturforschung A•Apr 1, 2003•0 citations
This paper presents and implements a specified partial adiabatic search algorithm on a quantum circuit. It studies the minimum energy gap between the first excited state and the ground state of the system Hamiltonian and it finds that, in the case of M = 1, the algorithm has the same performance as the local adiabatic algorithm. However, the algorithm evolves globally only within a small interval, which implies that it keeps the advantages of global adiabatic algorithms without losing the speedup of the local adiabatic search algorithm.
Recently, Zhang and Lu provided a quantum search algorithm based on partial adiabatic evolution, which beats the time bound of local adiabatic search when the number of marked items in the unsorted database is larger than one. Later, they found that the above two adiabatic search algorithms had the same time complexity when there is only one marked item in the database. In the present paper, following the idea of Roland and Cerf [Roland J and Cerf N J 2002 Phys. Rev. A 65 042308 ], if within the small symmetric evolution interval defined by Zhang et al., a local adiabatic evolution is performed instead of the original "global" one, this "new" algorithm exhibits slightly better performance, although they are progressively equivalent with M increasing. In addition, the proof of the optimality for this partial evolution based local adiabatic search when M = 1 is also presented. Two other special cases of the adiabatic algorithm obtained by appropriately tuning the evolution interval of partial adiabatic evolution based quantum search, which are found to have the same phenomenon above, are also discussed.
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.
This paper first demonstrates that by appropriately specifying the evolution interval in quantum partial adiabatic evolution, the time complexity of the resulting quantum search algorithm can achieve the well-known quadratic speedup bound of quantum computation. Then this result is used as a reference to remedy invalid quantum partial adiabatic search schemes, which means its time complexity doesn’t align with the optimal quantum speedup. And, it is found that the two versions of quantum partial adiabatic evolutions, i.e. “global” and “local” ones must be treated separately, despite previous studies indicating only minor differences in algorithmic performance between the two cases. Additionally, for the “local” variant of the quantum partial adiabatic search algorithm, it can be seen that there are other possible choices for the evolution interval besides the referred one. Our findings further show that significant variations in the resulting single-round success probabilities occur between valid and invalid quantum partial adiabatic evolutions.
We analyze three different quantum search algorithms, namely, the traditional circuit-based Grover's algorithm, its continuous-time analog by Hamiltonian evolution, and the quantum search by local adiabatic evolution. We show that these algorithms are closely related in the sense that they all perform a rotation, at a constant angular velocity, from a uniform superposition of all states to the solution state. This makes it possible to implement the two Hamiltonian-evolution algorithms on a conventional quantum circuit, while keeping the quadratic speedup of Grover's original algorithm. It also clarifies the link between the adiabatic search algorithm and Grover's algorithm.
Adiabatic quantum computation is based on the adiabatic evolution of quantum systems. We analyze a particular class of quantum adiabatic evolutions where either the initial or final Hamiltonian is a one-dimensional projector Hamiltonian on the corresponding ground state. The minimum-energy gap, which governs the time required for a successful evolution, is shown to be proportional to the overlap of the ground states of the initial and final Hamiltonians. We show that such evolutions exhibit a rapid crossover as the ground state changes abruptly near the transition point where the energy gap is minimum. Furthermore, a faster evolution can be obtained by performing a partial adiabatic evolution within a narrow interval around the transition point. These results generalize and quantify earlier works.
The quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving NPcomplete problems. The algorithm is governed by the adiabatic theorem. Therefore, in order to reduce the running time, it is essential to examine the minimum energy gap between the ground level and the next one in the evolution. In this paper we show a way of speedup in the quantum adiabatic evolution algorithm, using an extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides a new point of view to reduce the running time.