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:1004.5409

Adiabatic quantum computation: Enthusiast and Sceptic's perspectives

Zhenwei Cao, Alexander Elgart

Published Apr 29, 2010• 1 citation
arXivHTMLPDF

Abstract

Enthusiast's perspective: We analyze the effectiveness of AQC for a small rank problem Hamiltonian $H_F$ with the arbitrary initial Hamiltonian $H_I$. We prove that for the generic $H_I$ the running time cannot be smaller than $O(\sqrt N)$, where $N$ is a dimension of the Hilbert space. We also construct an explicit $H_I$ for which the running time is indeed $O(\sqrt N)$. Our algorithm can be used to solve the unstructured search problem with the unknown number of marked items. Sceptic's perspective: We show that for a robust device, the running time for such $H_F$ cannot be much smaller than $O(N/\ln N)$.

DOI
10.48550/arxiv.1004.5409

Related papers

On the efficiency of Hamiltonian-based quantum computation for low-rank matrices

Zhenwei Cao, Alexander Elgart

We present an extension of adiabatic quantum computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.

arXiv:1004.4911•Journal of Mathematical Physics•Mar 1, 2012•8 citations

Quantum search by local adiabatic evolution

Jérémie Roland, Nicolas J. Cerf

The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the quantum computer evolves slowly enough so that it remains near its instantaneous ground state, which tends to the solution. We apply this time-dependent Hamiltonian approach to Grover's problem, i.e., searching a marked item in an unstructured database. We find that by adjusting the evolution rate of the Hamiltonian so as to keep the evolution adiabatic on each infinitesimal time interval, the total running time is of order $\sqrt{N},$ where N is the number of items in the database. We thus recover the advantage of Grover's standard algorithm as compared to a classical search, scaling as N. This is in contrast with the constant-rate adiabatic approach of Farhi et al. (e-print quant-ph/0001106), where the requirement of adiabaticity is expressed only globally, resulting in a time of order N.

arXiv:quant-ph/0107015•Physical Review A•Mar 26, 2002•664 citations

Rapid Data Search using Adiabatic Quantum Computation

Daria Ahrensmeier, Saurya Das, Randy Kobes +2 more

We show that by a suitable choice of time-dependent Hamiltonian, the search for a marked item in an unstructured database can be achieved in unit time, using Adiabatic Quantum Computation. This is a considerable improvement over the O(sqrt(N)) time required in previous algorithms. The trade-off is that in the intermediate stages of the computation process, the ground state energy of the computer increases to a maximum of O(sqrt(N)), before returning to zero at the end of the process.

arXiv:quant-ph/0208107•Aug 15, 2002•1 citation

Unstructured Adiabatic Quantum Optimization: Optimality with Limitations

Arthur Braida, Shantanav Chakraborty, Alapan Chaudhuri +4 more

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n -bits in time poly(n)2n/2 . In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2n/2) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

arXiv:2411.05736•Quantum•Jul 11, 2025•10 citations

How fast can quantum annealers count?

Itay Hen

We outline an algorithm for the quantum counting problem using adiabatic quantum computation (AQC). We show that the mechanism of quantum-adiabatic evolution may be utilized toward estimating the number of solutions to a problem, and not only to find them. Using local adiabatic evolution, a process in which the adiabatic procedure is performed at a variable rate, the problem of counting the number of marked items in an unstructured database is solved quadratically faster than the corresponding classical algorithm. The above algorithm provides further evidence for the potentially powerful capabilities of AQC as a paradigm for more efficient problem solving on a quantum computer, and may be used as the basis for solving more sophisticated problems.

arXiv:1301.4956•Journal of Physics A Mathematical and Theoretical•May 27, 2014•11 citations

An Alternative Approach to Construct the Initial Hamiltonian of the Adiabatic Quantum Computation

Qian-Heng Duan, Shuo Zhang, Wei Wu +1 more

The adiabatic quantum computation (AQC) has been proven to be equivalent to the standard circuit model. Conventionally, AQC evolves from the initial Hamiltonian which has a uniform equal superposition of the computational basis to the final Hamiltonian whose ground state encodes the solution to a computation problem. We propose an alternative approach to construct the initial Hamiltonian of the AQC which has an unequal superposition of the possible solutions to the problem and show that an educated guess can improve the performance of AQC.

Chinese Physics Letters•Jan 1, 2013•19 citations
Enthusiast's perspective: We analyze the effectiveness of AQC for a small rank problem Hamiltonian HFH_FHF​ with the arbitrary initial Hamiltonian HIH_IHI​. We prove that for the generic HIH_IHI​ the running time cannot be smaller than O(N)O(\sqrt N)O(N​), where NNN is a dimension of the Hilbert space. We also construct an explicit HIH_IHI​ for which the running time is indeed O(N)O(\sqrt N)O(N​). Our algorithm can be used to solve the unstructured search problem with the unknown number of marked items. Sceptic's perspective: We show that for a robust device, the running time for such HFH_FHF​ cannot be much smaller than O(N/ln⁡N)O(N/\ln N)O(N/lnN).
We present an extension of adiabatic quantum computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.
The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the quantum computer evolves slowly enough so that it remains near its instantaneous ground state, which tends to the solution. We apply this time-dependent Hamiltonian approach to Grover's problem, i.e., searching a marked item in an unstructured database. We find that by adjusting the evolution rate of the Hamiltonian so as to keep the evolution adiabatic on each infinitesimal time interval, the total running time is of order N,\sqrt{N},N​, where N is the number of items in the database. We thus recover the advantage of Grover's standard algorithm as compared to a classical search, scaling as N. This is in contrast with the constant-rate adiabatic approach of Farhi et al. (e-print quant-ph/0001106), where the requirement of adiabaticity is expressed only globally, resulting in a time of order N.
In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n -bits in time poly(n)2n/2 . In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2n/2) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.
We outline an algorithm for the quantum counting problem using adiabatic quantum computation (AQC). We show that the mechanism of quantum-adiabatic evolution may be utilized toward estimating the number of solutions to a problem, and not only to find them. Using local adiabatic evolution, a process in which the adiabatic procedure is performed at a variable rate, the problem of counting the number of marked items in an unstructured database is solved quadratically faster than the corresponding classical algorithm. The above algorithm provides further evidence for the potentially powerful capabilities of AQC as a paradigm for more efficient problem solving on a quantum computer, and may be used as the basis for solving more sophisticated problems.
The adiabatic quantum computation (AQC) has been proven to be equivalent to the standard circuit model. Conventionally, AQC evolves from the initial Hamiltonian which has a uniform equal superposition of the computational basis to the final Hamiltonian whose ground state encodes the solution to a computation problem. We propose an alternative approach to construct the initial Hamiltonian of the AQC which has an unequal superposition of the possible solutions to the problem and show that an educated guess can improve the performance of AQC.