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:1311.5752 · Physical Review A

Comment on “Adiabatic quantum computation with a one-dimensional projector Hamiltonian”

Alastair Kay

Published Oct 31, 2013• 6 citations
arXivHTMLPDF

Abstract

The partial adiabatic search algorithm was introduced in Tulsi's paper [Phys. Rev. A 80, 052328 (2009)] as a modification of the usual adiabatic algorithm for a quantum search with the idea that most of the interesting computation only happens over a very short range of the adiabatic path. By focusing on that restricted range, one can potentially gain an advantage by reducing the control requirements on the system, enabling a uniform rate of evolution. In this Comment, we point out an oversight in Tulsi's paper [Phys. Rev. A 80, 052328 (2009)] that invalidates its proof. However, the argument can be corrected, and the calculations in Tulsi's paper [Phys. Rev. A 80, 052328 (2009)] are then sufficient to show that the scheme still works. Nevertheless, subsequent works [Phys. Rev. A 82, 034304 (2010), Chin. Phys. B 20, 040309 (2011), Chin. Phys. B 21, 010306 (2012), AASRI Procedia 1, 5862 (2012), and Quantum Inf. Process. 12, 2689 (2013)] cannot all be recovered in the same way.

DOI
10.1103/physreva.88.046301

Related papers

Quantum search by partial adiabatic evolution

Yingyu Zhang, Songfeng Lu

A quantum search algorithm based on the partial adiabatic evolution [Phys. Rev. A 80, 052328 (2009)] is provided. We calculate its time complexity and find that the algorithm improves the time complexity, which is $O(\sqrt{N/M})$, of the local adiabatic search algorithm [Phys. Rev. A 65, 042308 (2002)] to $O(\sqrt{N}/M)$.

arXiv:1007.1528•Physical Review A•Sep 22, 2010•16 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

Optimizing the quantum adiabatic algorithm

Hong-Ye Hu, Biao Wu

In the quantum adiabatic algorithm, as the adiabatic parameter $s(t)$ changes slowly from zero to one with finite rate, a transition to excited states inevitably occurs and this induces an intrinsic computational error. We show that this computational error depends not only on the total computation time $T$ but also on the time derivatives of the adiabatic parameter $s(t)$ at the beginning and the end of evolution. Previous work [A. T. Rezakhani, A. K. Pimachev, and D. A. Lidar, Phys. Rev. A 82, 052305 (2010)] also suggested this result. With six typical paths, we systematically demonstrate how to optimally design an adiabatic path to reduce the computational errors. Our method has a clear physical picture and also explains the pattern of computational error. In this paper we focus on the quantum adiabatic search algorithm although our results are general.

arXiv:1508.05089•Physical Review A•Jan 27, 2016•10 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

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

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
The partial adiabatic search algorithm was introduced in Tulsi's paper [Phys. Rev. A 80, 052328 (2009)] as a modification of the usual adiabatic algorithm for a quantum search with the idea that most of the interesting computation only happens over a very short range of the adiabatic path. By focusing on that restricted range, one can potentially gain an advantage by reducing the control requirements on the system, enabling a uniform rate of evolution. In this Comment, we point out an oversight in Tulsi's paper [Phys. Rev. A 80, 052328 (2009)] that invalidates its proof. However, the argument can be corrected, and the calculations in Tulsi's paper [Phys. Rev. A 80, 052328 (2009)] are then sufficient to show that the scheme still works. Nevertheless, subsequent works [Phys. Rev. A 82, 034304 (2010), Chin. Phys. B 20, 040309 (2011), Chin. Phys. B 21, 010306 (2012), AASRI Procedia 1, 5862 (2012), and Quantum Inf. Process. 12, 2689 (2013)] cannot all be recovered in the same way.
A quantum search algorithm based on the partial adiabatic evolution [Phys. Rev. A 80, 052328 (2009)] is provided. We calculate its time complexity and find that the algorithm improves the time complexity, which is O(N/M)O(\sqrt{N/M})O(N/M​), of the local adiabatic search algorithm [Phys. Rev. A 65, 042308 (2002)] to O(N/M)O(\sqrt{N}/M)O(N​/M).
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.
In the quantum adiabatic algorithm, as the adiabatic parameter s(t)s(t)s(t) changes slowly from zero to one with finite rate, a transition to excited states inevitably occurs and this induces an intrinsic computational error. We show that this computational error depends not only on the total computation time TTT but also on the time derivatives of the adiabatic parameter s(t)s(t)s(t) at the beginning and the end of evolution. Previous work [A. T. Rezakhani, A. K. Pimachev, and D. A. Lidar, Phys. Rev. A 82, 052305 (2010)] also suggested this result. With six typical paths, we systematically demonstrate how to optimally design an adiabatic path to reduce the computational errors. Our method has a clear physical picture and also explains the pattern of computational error. In this paper we focus on the quantum adiabatic search algorithm although our results are general.
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.
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.
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.