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

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•43 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

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

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•1 citation

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

Adiabatic quantum unstructured search in parallel

Sean A. Adamson, Petros Wallden

We present an optimized adiabatic quantum schedule for unstructured search building on the original approach of Roland and Cerf [Phys. Rev. A 65, 042308 (2002)]. Our schedule adiabatically varies the Hamiltonian even more rapidly at the endpoints of its evolution, preserving Grover's well-known quadratic quantum speedup. In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time, suggesting efficient parallelization. Numerical simulations of an appropriate reduced two-dimensional Schrödinger system confirm adiabaticity while demonstrating superior performance in terms of probability compared to existing adiabatic algorithms and Grover's algorithm, benefiting applications with possible premature termination. We introduce a protocol that ensures a marked-state probability at least $p$ in time of order $\sqrt{N}(1+p/\varepsilon)$, and analyze its implications for realistic bounded-resource scenarios. Our findings suggest that quantum advantage may still be achievable under constrained coherence times (where other algorithms fail), provided the hardware allows for them to be sufficiently long.

arXiv:2502.08594•Feb 12, 2025•3 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.
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.
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 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).
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).
We present an optimized adiabatic quantum schedule for unstructured search building on the original approach of Roland and Cerf [Phys. Rev. A 65, 042308 (2002)]. Our schedule adiabatically varies the Hamiltonian even more rapidly at the endpoints of its evolution, preserving Grover's well-known quadratic quantum speedup. In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time, suggesting efficient parallelization. Numerical simulations of an appropriate reduced two-dimensional Schrödinger system confirm adiabaticity while demonstrating superior performance in terms of probability compared to existing adiabatic algorithms and Grover's algorithm, benefiting applications with possible premature termination. We introduce a protocol that ensures a marked-state probability at least ppp in time of order N(1+p/ε)\sqrt{N}(1+p/\varepsilon)N​(1+p/ε), and analyze its implications for realistic bounded-resource scenarios. Our findings suggest that quantum advantage may still be achievable under constrained coherence times (where other algorithms fail), provided the hardware allows for them to be sufficiently long.