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/0208065

Structured Adiabatic Quantum Search

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

Published Aug 9, 2002• 2 citations
arXivHTMLPDF

Abstract

We examine the use of adiabatic quantum algorithms to solve structured, or nested, search problems. We construct suitable time dependent Hamiltonians and derive the computation times for a general class of nested searches involving n qubits. As expected, we find that as additional structure is included, the Hamiltonians become more local and the computation times decrease.

DOI
10.48550/arxiv.quant-ph/0208065

Related papers

Adiabatic quantum search algorithm for structured problems

Jérémie Roland, Nicolas J. Cerf

The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.

arXiv:quant-ph/0304039•Physical Review A•Dec 15, 2003•29 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

Nested quantum search and structured problems

Nicolas J. Cerf, Lov K. Grover, Colin P. Williams

A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order $\sqrt{d},$ where d is the dimension of the search space, whereas any classical algorithm necessarily scales as $O(d).$ It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum search within another. The average number of iterations required to find the solution of a typical hard instance of a constraint satisfaction problem is found to scale as $\sqrt{{d}^{\ensuremath{\alpha}}},$ with the constant $\ensuremath{\alpha}<1$ depending on the nesting depth and the type of problem considered. This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, $\ensuremath{\alpha}$ is estimated to be around 0.62.

arXiv:quant-ph/9806078•Physical Review A•Feb 9, 2000•104 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•629 citations

Transitionless driving on local adiabatic quantum search algorithm

Feng‐Guang Li, Wan‐Su Bao, Shuo Zhang +4 more

We apply the transitionless driving on the local adiabatic quantum search algorithm to speed up the adiabatic process. By studying quantum dynamics of the adiabatic search algorithm with the equivalent two-level system, we derive the transitionless driving Hamiltonian for the local adiabatic quantum search algorithm. We found that when adding a transitionless quantum driving term H D ( t ) on the local adiabatic quantum search algorithm, the success rate is 1 exactly with arbitrary evolution time by solving the time-dependent Schr¨odinger equation in eigen-picture. Moreover, we show the reason for the drastic decrease of the evolution time is that the driving Hamiltonian increases the lowest eigenvalues to a maximum of O ( N ) .

Chinese Physics B•Jan 1, 2018•3 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
We examine the use of adiabatic quantum algorithms to solve structured, or nested, search problems. We construct suitable time dependent Hamiltonians and derive the computation times for a general class of nested searches involving n qubits. As expected, we find that as additional structure is included, the Hamiltonians become more local and the computation times decrease.
The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.
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.
A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order d,\sqrt{d},d​, where d is the dimension of the search space, whereas any classical algorithm necessarily scales as O(d).O(d).O(d). It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum search within another. The average number of iterations required to find the solution of a typical hard instance of a constraint satisfaction problem is found to scale as $\sqrt{{d}^{\ensuremath{\alpha}}},$ with the constant $\ensuremath{\alpha}<1$ depending on the nesting depth and the type of problem considered. This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, $\ensuremath{\alpha}$ is estimated to be around 0.62.
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 apply the transitionless driving on the local adiabatic quantum search algorithm to speed up the adiabatic process. By studying quantum dynamics of the adiabatic search algorithm with the equivalent two-level system, we derive the transitionless driving Hamiltonian for the local adiabatic quantum search algorithm. We found that when adding a transitionless quantum driving term H D ( t ) on the local adiabatic quantum search algorithm, the success rate is 1 exactly with arbitrary evolution time by solving the time-dependent Schr¨odinger equation in eigen-picture. Moreover, we show the reason for the drastic decrease of the evolution time is that the driving Hamiltonian increases the lowest eigenvalues to a maximum of O ( N ) .