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

International Journal of Quantum Information

On the circuit model of two quantum adiabatic search algorithms

Jie Sun

Published Apr 15, 2024• 2 citations
Publisher

Abstract

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.

DOI
10.1142/s0219749924500230

Related papers

Optimality of Quantum Adiabatic Search Algorithm and Its Circuit Model

Jie Sun, Zhimin Zhang, Songfeng Lu

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.

Quantum Reports•Mar 26, 2026•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

On the General Class of Models of Adiabatic Evolution

Jie Sun, Songfeng Lu, Fang Liu

The general class of models of adiabatic evolution was proposed to speed up the usual adiabatic computation in the case of quantum search problem. It was shown [8] that, by temporarily increasing the ground state energy of a time-dependent Hamiltonian to a suitable quantity, the quantum computation can perform the calculation in time complexity O(1). But it is also known that if the overlap between the initial and final states of the system is zero, then the computation based on the generalized models of adiabatic evolution can break down completely. In this paper, we find another severe limitation for this class of adiabatic evolution-based algorithms, which should be taken into account in applications. That is, it is still possible that this kind of evolution designed to deal with the quantum search problem fails completely if the interpolating paths in the system Hamiltonian are chosen inappropriately, while the usual adiabatic evolutions can do the same job relatively effectively. This implies that it is not always recommendable to use nonlinear paths in adiabatic computation. On the contrary, the usual simple adiabatic evolution may be sufficient for effective use.

Open Systems & Information Dynamics•Sep 1, 2016•3 citations

On Models of Nonlinear Evolution Paths in Adiabatic Quantum Algorithms

Jie Sun, Songfeng Lu, Samuel L. Braunstein

In this paper, we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state. If the overlap between the initial state and final state of the quantum system is not equal to zero, both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding "complexity". But when the initial state has a zero overlap with the solution state in the problem, the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time. However, inspired by a related reference, a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the "intrinsic" fault of the second model — an increase in energy. Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above. These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.

arXiv:1301.1115•Communications in Theoretical Physics•Jan 1, 2013•8 citations

On Models of Nonlinear Evolution Paths in Adiabatic Quantum Algorithms4

孙杰, 路松峰

In this paper,we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state.If the overlap between the initial state and final state of the quantum system is not equal to zero,both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding complexity.But when the initial state has a zero overlap with the solution state in the problem,the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time.However,inspired by a related reference,a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the intrinsic fault of the second model - an increase in energy.Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above.These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.

理论物理通讯：英文版•Jan 1, 2013•0 citations

The Constant Speedup Mechanism on Adiabatic Quantum Computation

Zhigang Zhang, Songfeng Lu, Jie Sun +1 more

In the adiabatic quantum computation model, a computational procedure is described by the continuous time evolution of a time dependent Hamiltonian. Classically, the unstructured search problem can be solved only in a running time of order O(G). However, by modifying the structure of local Hamiltonian or using specific interpolating functions, it is possible to do the calculation in constant time for a quantum computer. This paper reveals the cause that lead to the speedup. We analyze two kinds of specific adiabatic quantum models, and conclude that the value of relevant elements in back-diagonal of the local Hamiltonian is the main factors affecting the time complexity of adiabatic quantum algorithms. According to the speedup mechanism, we have proposed two kinds of adiabatic quantum algorithms to make a constant time complexity.

Journal of Computational and Theoretical Nanoscience•Oct 1, 2016•0 citations
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.
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.
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.
The general class of models of adiabatic evolution was proposed to speed up the usual adiabatic computation in the case of quantum search problem. It was shown [8] that, by temporarily increasing the ground state energy of a time-dependent Hamiltonian to a suitable quantity, the quantum computation can perform the calculation in time complexity O(1). But it is also known that if the overlap between the initial and final states of the system is zero, then the computation based on the generalized models of adiabatic evolution can break down completely. In this paper, we find another severe limitation for this class of adiabatic evolution-based algorithms, which should be taken into account in applications. That is, it is still possible that this kind of evolution designed to deal with the quantum search problem fails completely if the interpolating paths in the system Hamiltonian are chosen inappropriately, while the usual adiabatic evolutions can do the same job relatively effectively. This implies that it is not always recommendable to use nonlinear paths in adiabatic computation. On the contrary, the usual simple adiabatic evolution may be sufficient for effective use.
In this paper, we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state. If the overlap between the initial state and final state of the quantum system is not equal to zero, both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding "complexity". But when the initial state has a zero overlap with the solution state in the problem, the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time. However, inspired by a related reference, a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the "intrinsic" fault of the second model — an increase in energy. Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above. These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.
In this paper,we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state.If the overlap between the initial state and final state of the quantum system is not equal to zero,both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding complexity.But when the initial state has a zero overlap with the solution state in the problem,the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time.However,inspired by a related reference,a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the intrinsic fault of the second model - an increase in energy.Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above.These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.
In the adiabatic quantum computation model, a computational procedure is described by the continuous time evolution of a time dependent Hamiltonian. Classically, the unstructured search problem can be solved only in a running time of order O(G). However, by modifying the structure of local Hamiltonian or using specific interpolating functions, it is possible to do the calculation in constant time for a quantum computer. This paper reveals the cause that lead to the speedup. We analyze two kinds of specific adiabatic quantum models, and conclude that the value of relevant elements in back-diagonal of the local Hamiltonian is the main factors affecting the time complexity of adiabatic quantum algorithms. According to the speedup mechanism, we have proposed two kinds of adiabatic quantum algorithms to make a constant time complexity.