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:1706.07646 · Chinese Physics Letters

Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm

Hongye Yu, Yuliang Huang, Biao Wu

Published Oct 1, 2018• 21 citations
arXivHTMLPDF

Abstract

We present a rigorous proof that quantum circuit algorithm can be transformed into quantum adiabatic algorithm with the exact same time complexity. This means that from a quantum circuit algorithm of L gates we can construct a quantum adiabatic algorithm with time complexity of O(L). Additionally, our construction shows that one may exponentially speed up some quantum adiabatic algorithms by properly choosing an evolution path .

DOI
10.1088/0256-307x/35/11/110303

Related papers

Direct mapping of quantum circuits to adiabatic algorithms

M. Stewart Siu

We give a method of mapping any arbitrary circuit in the standard quantum computing model to an adiabatic algorithm of the same depth. It is a direct mapping as we use the same initial, intermediate and final states as in the circuit. Hence we show constructively the existence of efficient adiabatic evolution paths for a class of problems. Since the physical implementation of unitary gates in the circuit model requires precise timing control, the equivalent adiabatic construction may also provide a more realizable alternative.

•Sep 3, 2004•0 citations

Quantum gates with controlled adiabatic evolutions

Itay Hen

We introduce a class of quantum adiabatic evolutions that we claim may be interpreted as the equivalents of the unitary gates of the quantum gate model. We argue that these gates form a universal set and may therefore be used as building blocks in the construction of arbitrary ``adiabatic circuits,'' analogously to the manner in which gates are used in the circuit model. One implication of the above construction is that arbitrary classical boolean circuits as well as gate model circuits may be directly translated to adiabatic algorithms with no additional resources or complexities. We show that while these adiabatic algorithms fail to exhibit certain aspects of the inherent fault tolerance of traditional quantum adiabatic algorithms, they may have certain other experimental advantages acting as quantum gates.

arXiv:1401.5172•Physical Review A•Feb 12, 2015•37 citations

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

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

Different Approaches for Implementing Quantum Search by Adiabatic Evolution

Jie Sun, Songfeng Lu, Yu Zhang

Abstract In this paper, three different approaches for implementing a quantum search algorithm by adiabatic evolution are shown. As expected, either one of them can provide a quadratic speed up as opposed to the classical search algorithm. This implies that adiabatic evolution based quantum computation gives more feasibilities than the quantum circuit model, although the equivalence between them has already been proven in the corresponding literature.

AASRI Procedia•Jan 1, 2012•6 citations

A Modified Adiabatic Quantum Algorithm for Evaluation of Boolean Functions

Jie Sun, Songfeng Lu, Fang Liu

In this paper, we propose a modified construction of the quantum adiabatic algorithm for Boolean functions studied by M. Andrecut et al. [13, 14]. Our algorithm has the time complexity [Formula: see text] for the evaluation of Boolean functions, without additional computational cost of implementing the driving Hamiltonian, which is required by the adiabatic evolution described in [13, 14].

Open Systems & Information Dynamics•Sep 1, 2015•2 citations
We present a rigorous proof that quantum circuit algorithm can be transformed into quantum adiabatic algorithm with the exact same time complexity. This means that from a quantum circuit algorithm of L gates we can construct a quantum adiabatic algorithm with time complexity of O(L). Additionally, our construction shows that one may exponentially speed up some quantum adiabatic algorithms by properly choosing an evolution path .
We give a method of mapping any arbitrary circuit in the standard quantum computing model to an adiabatic algorithm of the same depth. It is a direct mapping as we use the same initial, intermediate and final states as in the circuit. Hence we show constructively the existence of efficient adiabatic evolution paths for a class of problems. Since the physical implementation of unitary gates in the circuit model requires precise timing control, the equivalent adiabatic construction may also provide a more realizable alternative.
We introduce a class of quantum adiabatic evolutions that we claim may be interpreted as the equivalents of the unitary gates of the quantum gate model. We argue that these gates form a universal set and may therefore be used as building blocks in the construction of arbitrary ``adiabatic circuits,'' analogously to the manner in which gates are used in the circuit model. One implication of the above construction is that arbitrary classical boolean circuits as well as gate model circuits may be directly translated to adiabatic algorithms with no additional resources or complexities. We show that while these adiabatic algorithms fail to exhibit certain aspects of the inherent fault tolerance of traditional quantum adiabatic algorithms, they may have certain other experimental advantages acting as quantum gates.
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.