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:quant-ph/0208107

Rapid Data Search using Adiabatic Quantum Computation

Daria Ahrensmeier, Saurya Das, Randy Kobes, G. Kunstatter, Haitham Zaraket

Published Aug 15, 2002• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0208107

Related papers

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•629 citations

Energy and efficiency of adiabatic quantum search algorithms

Saurya Das, Randy Kobes, G. Kunstatter

We present the results of a detailed analysis of a general, unstructured adiabatic quantum search of a database of N items. In particular, we examine the effects on the computation time of adding energy to the system. We find that by increasing the lowest eigenvalue of the time-dependent Hamiltonian temporarily to a maximum of ∝√ N , it is possible to do the calculation in constant time. This leads us to derive the general theorem which provides the adiabatic analogue of the √ N bound of conventional quantum searches. The result suggests that the action associated with the oracle term in the time-dependent Hamiltonian is a direct measure of the resources required by the adiabatic quantum search.

arXiv:quant-ph/0204044•Journal of Physics A Mathematical and General•Mar 6, 2003•34 citations

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•6 citations

Adiabatic quantum computation: Enthusiast and Sceptic's perspectives

Zhenwei Cao, Alexander Elgart

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)$.

arXiv:1004.5409•Apr 29, 2010•0 citations

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.

•Jan 1, 2012•6 citations

Dissipative search of an unstructured database

ARMEN E. ALLAHVERDYAN, David Petrosyan

The search of an unstructured database amounts to finding one element having a certain property out of $N$ elements. The classical search with an oracle checking one element at a time requires on average $N/2$ steps. The Grover algorithm for the quantum search and its unitary Hamiltonian evolution analog accomplish the search asymptotically optimally in $O(\sqrt{N})$ time steps. We reformulate the search problem as a dissipative, incoherent Markov process acting on an $N$-level system weakly coupled to a thermal bath. Assuming that the energy levels of the system represent the database elements, we show that, with a proper choice of the spectrum and long-range but bounded transition rates between the energy levels, the system relaxes to the ground state, corresponding to the sought element, in time $O(lnN)$.

arXiv:2106.02703•Physical Review A•Mar 25, 2022•8 citations
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.
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.
We present the results of a detailed analysis of a general, unstructured adiabatic quantum search of a database of N items. In particular, we examine the effects on the computation time of adding energy to the system. We find that by increasing the lowest eigenvalue of the time-dependent Hamiltonian temporarily to a maximum of ∝√ N , it is possible to do the calculation in constant time. This leads us to derive the general theorem which provides the adiabatic analogue of the √ N bound of conventional quantum searches. The result suggests that the action associated with the oracle term in the time-dependent Hamiltonian is a direct measure of the resources required by the adiabatic quantum search.
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.
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 search of an unstructured database amounts to finding one element having a certain property out of NNN elements. The classical search with an oracle checking one element at a time requires on average N/2N/2N/2 steps. The Grover algorithm for the quantum search and its unitary Hamiltonian evolution analog accomplish the search asymptotically optimally in O(N)O(\sqrt{N})O(N​) time steps. We reformulate the search problem as a dissipative, incoherent Markov process acting on an NNN-level system weakly coupled to a thermal bath. Assuming that the energy levels of the system represent the database elements, we show that, with a proper choice of the spectrum and long-range but bounded transition rates between the energy levels, the system relaxes to the ground state, corresponding to the sought element, in time O(lnN)O(lnN)O(lnN).