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

Open Systems & Information Dynamics

A Modified Adiabatic Quantum Algorithm for Evaluation of Boolean Functions

Jie Sun, Songfeng Lu, Fang Liu

Published Sep 1, 2015• 2 citations
Publisher

Abstract

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].

DOI
10.1142/s1230161215500183

Related papers

Lower bound on the time complexity of local adiabatic evolution

Zhenghao Chen, Pang Wei Koh, Yan Zhao

The adiabatic theorem of quantum physics has been, in recent times, utilized in the design of local search quantum algorithms, and has been proven to be equivalent to standard quantum computation, that is, the use of unitary operators [D. Aharonov et al. in Proceedings of the 45th Annual Symposium on the Foundations of Computer Science, 2004, Rome, Italy (IEEE Computer Society Press, New York, 2004), pp. 42--51]. Hence, the study of the time complexity of adiabatic evolution algorithms gives insight into the computational power of quantum algorithms. In this paper, we present two different approaches of evaluating the time complexity for local adiabatic evolution using time-independent parameters, thus providing effective tests (not requiring the evaluation of the entire time-dependent gap function) for the time complexity of newly developed algorithms. We further illustrate our tests by displaying results from the numerical simulation of some problems, viz. specially modified instances of the Hamming weight problem.

Physical Review A•Nov 9, 2006•2 citations

Can adiabatic algorithms with extra items always be efficient in quantum computation?

Zhigang Zhang, Songfeng Lu, Xin Cong Zhou

It has been known that when an assisted driving item is added to the Hamiltonian of the main system, the efficiency of the resultant adiabatic evolution can be significantly improved. In some special cases, it can be seen that, only by adding an assisted driving Hamiltonian can the resultant adiaba tic evolution work. So it seems that, the additional driving Hamiltonian plays an important role in adiabatic computing. In this paper, we show five kinds of possible forms of the driving Hamiltonian, and analyses the performance of the algorithms. We find that the former fourth kinds of driving Hamiltonian may still cause the adiabatic algorithm lose their efficiency when the overlap of the initial and final states equals some special value. More importantly, we find that only the final kinds of the driving Hamiltonian can be extended. By modifying its interpolating functions, the final kind of adiabatic algorithm can suit any fidelity of the systems to keep the adiabatic evolution always be valid. Finally, the time complexity of the extended algorithm is better than the original adiabatic algorithm, which owns a constant running time complexity. Although the time complexity is shifted to the complexity of implementing the driving Hamiltonian added.

Journal of Intelligent & Fuzzy Systems•Feb 27, 2018•1 citation

Quantum Adiabatic Evolution for Pattern Recognition Problem

E. Rezaei Fard, Korosh Aghayar

Quantum pattern recognition algorithm for two-qubit systems has been implemented by quantum adiabatic evolution. We will estimate required running time for this algorithm by means of an analytical solution of time-dependent Hamiltonian since the time complexity of adiabatic quantum evolution is a limitation on the quantum computing. These results can be useful for experimental implementation .

Chinese Physics Letters•Dec 1, 2017•2 citations

Adiabatic quantum gates and Boolean functions

M. Andrecut, Mazhar Ali

We discuss the logical implementation of quantum gates and Boolean functions in the framework of quantum adiabatic method, which uses the language of ground states, spectral gaps and Hamiltonians instead of the standard unitary transformation language.

Journal of Physics A Mathematical and General•Jun 9, 2004•8 citations

Adiabatic quantum computation and Deutsch’s algorithm

Saurya Das, Randy Kobes, G. Kunstatter

We show that by a suitable choice of a time-dependent Hamiltonian, Deutsch's algorithm can be implemented by an adiabatic quantum computer. We extend our analysis to the Deutsch-Jozsa problem and estimate the required running time for both global and local adiabatic evolutions.

arXiv:quant-ph/0111032•Physical Review A•Jun 5, 2002•48 citations

Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm

Hongye Yu, Yuliang Huang, Biao Wu

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 .

arXiv:1706.07646•Chinese Physics Letters•Oct 1, 2018•21 citations
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].
The adiabatic theorem of quantum physics has been, in recent times, utilized in the design of local search quantum algorithms, and has been proven to be equivalent to standard quantum computation, that is, the use of unitary operators [D. Aharonov et al. in Proceedings of the 45th Annual Symposium on the Foundations of Computer Science, 2004, Rome, Italy (IEEE Computer Society Press, New York, 2004), pp. 42--51]. Hence, the study of the time complexity of adiabatic evolution algorithms gives insight into the computational power of quantum algorithms. In this paper, we present two different approaches of evaluating the time complexity for local adiabatic evolution using time-independent parameters, thus providing effective tests (not requiring the evaluation of the entire time-dependent gap function) for the time complexity of newly developed algorithms. We further illustrate our tests by displaying results from the numerical simulation of some problems, viz. specially modified instances of the Hamming weight problem.
It has been known that when an assisted driving item is added to the Hamiltonian of the main system, the efficiency of the resultant adiabatic evolution can be significantly improved. In some special cases, it can be seen that, only by adding an assisted driving Hamiltonian can the resultant adiaba tic evolution work. So it seems that, the additional driving Hamiltonian plays an important role in adiabatic computing. In this paper, we show five kinds of possible forms of the driving Hamiltonian, and analyses the performance of the algorithms. We find that the former fourth kinds of driving Hamiltonian may still cause the adiabatic algorithm lose their efficiency when the overlap of the initial and final states equals some special value. More importantly, we find that only the final kinds of the driving Hamiltonian can be extended. By modifying its interpolating functions, the final kind of adiabatic algorithm can suit any fidelity of the systems to keep the adiabatic evolution always be valid. Finally, the time complexity of the extended algorithm is better than the original adiabatic algorithm, which owns a constant running time complexity. Although the time complexity is shifted to the complexity of implementing the driving Hamiltonian added.