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

Quantum Reports

Optimality of Quantum Adiabatic Search Algorithm and Its Circuit Model

Jie Sun, Zhimin Zhang, Songfeng Lu

Published Mar 26, 2026• 2 citations
Publisher

Abstract

In this paper, we study two aspects of quantum adiabatic evolution for a prototypical search problem: the optimality of the corresponding algorithm and its relation to the quantum circuit model. Firstly, we propose a general framework for proving the square-root speedup of the quantum adiabatic algorithm to be optimal over classical computation, which is readily applicable to the case of multiple targets. Through this framework, we also find that it is possible to further reduce the time complexity by increasing the physical energy of the system, encompassing results from previous works. Secondly, we find that, on the one hand, when the quantum adiabatic algorithm that achieves quadratic speedup is implemented on a quantum circuit, the time slice needed is always consistent with its time complexity, which also encompasses previous results; on the other hand, however, if a further algorithmic improvement is considered, the time slice always remains invariant. This phenomenon represents a significant observation with potential applications. We anticipate that the main results of this paper will interest the quantum adiabatic computation community and may help us to design efficient quantum algorithms for practical problems in the future.

DOI
10.3390/quantum8020028

Related papers

On the circuit model of two quantum adiabatic search algorithms

Jie Sun

The early work of Wei et al. has shown that it is possible to do the computation in constant time for quantum search in quantum local adiabatic evolution framework if the system Hamiltonian has an extra enlarged factor proportional to the square-root of the size of the problem. Also in our prior work, we have shown that it is possible to apply a linear interpolating path in the system Hamiltonian to achieve an O(1) time complexity for a quantum global adiabatic computation. In this paper, we discuss the issues when implementing these two quantum algorithms on the quantum circuit model, and find that to our surprise, the time slices produced does not equal to the time complexity of the algorithm in each case. This is in contrast to the previous related results, because there these two quantities always coincide. When taking into account of the whole energy-level increase of the system compared with that of the usual quantum adiabatic evolutions and the corresponding time complexity simultaneously, we find that the time slices needed always consist of the two quantities multiplying together. This result is new, and may be hopeful to find application in designing quantum adiabatic algorithm for problems beyond quantum search.

International Journal of Quantum Information•Apr 15, 2024•2 citations

On validity of quantum partial adiabatic search

Jie Sun, Dunbo Cai, Songfeng Lu +2 more

Abstract In this paper, we further verify the validity of the quantum partial adiabatic search algorithm which was initialized in the previous related works by revisiting its quantum circuit model. The main results got here are as follows. When considering implementing quantum partial adiabatic evolution on a quantum circuit, a correction is given for the time slice estimation for the first stage during this approximation in the previous related works, new evidence is provided for a time complexity cost $O(\sqrt{N}/M)$ O ( N / M ) of quantum partial adiabatic algorithm is impossible, and the correct time complexity $O(\sqrt{N/M})$ O ( N / M ) of it is emphasized once more according to its circuit correspondence, in which N is the total number of elements in the search problem of which M of them are the marked ones. The findings exposed are hopeful for revisiting quantum partial adiabatic evolution and its connection with the quantum circuit model.

EPJ Quantum Technology•Jul 25, 2024•7 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

Adiabatic quantum search algorithm for structured problems

Jérémie Roland, Nicolas J. Cerf

The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.

arXiv:quant-ph/0304039•Physical Review A•Dec 15, 2003•29 citations

Speedup in Quantum Adiabatic Evolution Algorithm

Joonwoo Bae, Younghun Kwon

Quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving instances of NP-complete 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 through the evolution. In this letter, we show a way of speedup in quantum adiabatic evolution algorithm,using the extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides the new point of view to reduce the running time. It is generally expected that quantum computation may solve the problems which are hard in classical context. Shor’s quantum factorization algorithm[1] and Grover’s quantum search algorithm[2] are the preludes to such expectation. Factorization problem, which is to factorize a large number, needs exponential time resource when a known classical algorithm is applied. However, Shor’s algorithm solves the problem with exponential speedup. Grover algorithm finds a target with quadratic speedup, compared to any known classical search algorithms. Quantum adiabatic evolution algorithm was proposed by Farhi et al. and applied to solve instances of NPcomplete

•Jan 1, 2002•0 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
In this paper, we study two aspects of quantum adiabatic evolution for a prototypical search problem: the optimality of the corresponding algorithm and its relation to the quantum circuit model. Firstly, we propose a general framework for proving the square-root speedup of the quantum adiabatic algorithm to be optimal over classical computation, which is readily applicable to the case of multiple targets. Through this framework, we also find that it is possible to further reduce the time complexity by increasing the physical energy of the system, encompassing results from previous works. Secondly, we find that, on the one hand, when the quantum adiabatic algorithm that achieves quadratic speedup is implemented on a quantum circuit, the time slice needed is always consistent with its time complexity, which also encompasses previous results; on the other hand, however, if a further algorithmic improvement is considered, the time slice always remains invariant. This phenomenon represents a significant observation with potential applications. We anticipate that the main results of this paper will interest the quantum adiabatic computation community and may help us to design efficient quantum algorithms for practical problems in the future.
The early work of Wei et al. has shown that it is possible to do the computation in constant time for quantum search in quantum local adiabatic evolution framework if the system Hamiltonian has an extra enlarged factor proportional to the square-root of the size of the problem. Also in our prior work, we have shown that it is possible to apply a linear interpolating path in the system Hamiltonian to achieve an O(1) time complexity for a quantum global adiabatic computation. In this paper, we discuss the issues when implementing these two quantum algorithms on the quantum circuit model, and find that to our surprise, the time slices produced does not equal to the time complexity of the algorithm in each case. This is in contrast to the previous related results, because there these two quantities always coincide. When taking into account of the whole energy-level increase of the system compared with that of the usual quantum adiabatic evolutions and the corresponding time complexity simultaneously, we find that the time slices needed always consist of the two quantities multiplying together. This result is new, and may be hopeful to find application in designing quantum adiabatic algorithm for problems beyond quantum search.
Abstract In this paper, we further verify the validity of the quantum partial adiabatic search algorithm which was initialized in the previous related works by revisiting its quantum circuit model. The main results got here are as follows. When considering implementing quantum partial adiabatic evolution on a quantum circuit, a correction is given for the time slice estimation for the first stage during this approximation in the previous related works, new evidence is provided for a time complexity cost O(N/M)O(\sqrt{N}/M)O(N​/M) O ( N / M ) of quantum partial adiabatic algorithm is impossible, and the correct time complexity O(N/M)O(\sqrt{N/M})O(N/M​) O ( N / M ) of it is emphasized once more according to its circuit correspondence, in which N is the total number of elements in the search problem of which M of them are the marked ones. The findings exposed are hopeful for revisiting quantum partial adiabatic evolution and its connection with the quantum circuit model.
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.
The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.
Quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving instances of NP-complete 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 through the evolution. In this letter, we show a way of speedup in quantum adiabatic evolution algorithm,using the extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides the new point of view to reduce the running time. It is generally expected that quantum computation may solve the problems which are hard in classical context. Shor’s quantum factorization algorithm[1] and Grover’s quantum search algorithm[2] are the preludes to such expectation. Factorization problem, which is to factorize a large number, needs exponential time resource when a known classical algorithm is applied. However, Shor’s algorithm solves the problem with exponential speedup. Grover algorithm finds a target with quadratic speedup, compared to any known classical search algorithms. Quantum adiabatic evolution algorithm was proposed by Farhi et al. and applied to solve instances of NPcomplete
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.