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

An intuitive Hamiltonian for quantum search

Stephen Fenner

Published Apr 24, 2000• 7 citations
arXivHTMLPDF

Abstract

We present new intuition behind Grover's quantum search algorithm by means of a Hamiltonian. Given a black-box Boolean function f mapping strings of length n into {0,1} such that f(w) = 1 for exactly one string w, L. K. Grover describes a quantum algorithm that finds w in O(2^{n/2}) time. Farhi & Gutmann show that w can also be found in the same amount time by letting the quantum system evolve according to a simple Hamiltonian depending only on f. Their system evolves along a path far from that taken by Grover's original algorithm, however. The current paper presents an equally simple Hamiltonian matching Grover's algorithm step for step. The new Hamiltonian is similar in appearance from that of Farhi & Gutmann, but has some important differences, and provides new intuition for Grover's algorithm itself. This intuition both contrasts with and supplements other explanations of Grover's algorithm as a rotation in two dimensions, and suggests that the Hamiltonian-based approach to quantum algorithms can provide a useful heuristic for discovering new quantum algorithms.

DOI
10.48550/arxiv.quant-ph/0004091

Related papers

Driving Hamiltonian in a Quantum Search Problem

Kazuto Oshima

We examine the driving Hamiltonian in the analog analogue of Grover's algorithm by Farhi and Gutmann. For a quantum system with a given Hamiltonian $E|w> < w|$, we explicitly show that while the driving Hamiltonian $E|s> < s|$ optimally produces the state $|w>$ from an initial state $|s>$, the driving Hamiltonian $E^{\prime}|s> < s|(E^{\prime} \ne E)$ does not provide any speedup compared even with a classical computation.

arXiv:quant-ph/0111021•Nov 4, 2001•1 citation

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

An adiabatic oracle for Grover's algorithm

Bin Yan, Nikolai A. Sinitsyn

Grover's search algorithm was originally proposed for circuit-based quantum computers. A crucial part of it is to query an oracle -- a black-box unitary operation. Generation of this oracle is formally beyond the original algorithm design. Here, we propose a realization of Grover's oracle for a large class of searching problems using a quantum annealing step. The time of this step grows only logarithmically with the size of the database. This suggests an efficient path to application of Grover's algorithm to practically important problems, such as finding the ground state of a Hamiltonian with a spectral gap over its ground state.

arXiv:2207.05665•Jul 12, 2022•1 citation

Continuous-time Quantum Algorithms: Searching and Adiabatic Computation

Lawrence M. Ioannou

One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.

•Jan 1, 2002•4 citations

The Analysis on the Running Time of the Generalized Quantum Search Hamiltonian : $O(N^{1/4})$ and O(1) Time Resources

Joonwoo Bae, Younghun Kwon

Farhi et al. suggested the analogue quantum search Hamiltonian and Fenner also proposed the intuitive quantum search Hamiltonian. Recently the generalized quantum search Hamiltonian containning hamiltonians of Farhi et al. and Fenner was presented in quant-ph/0110020. In this letter, we analyze the running time of the generalized quantum search Hamiltonian. Our analysis displays two surprising results. The first is the exponential speedup(T = O(N 1/4)), and the next O(1) time resource. In 1996, Farhi et al. suggested the analogue quantum search algorithm based on Hamiltonian evolution.[1] The Hamiltonian to solve the search problem is Haf = Ed(|w〉〈w|+|ψ〉〈ψ|). In the Hamiltonian Haf, |w 〉 is the target state that we have to find, |ψ 〉 is the initial state that is a superposition of N states, E is a constant in unit of energy, and d is a constant. Fenner [2] also proposed the quantum search Hamiltonian Hif = −2iEx(|w〉〈ψ | − |ψ〉〈w|), where x = 〈w|ψ 〉 ≈ 1 √. The Hamiltonian Hif is called the intuitive quantum search Hamil-N tonian. Recently, the generalized quantum search Hamiltonian including hamiltonians of Farhi et al. and Fenner was presented.[3] The Hamiltonian is as follows: Hyj = E[d(|w〉〈w | + |ψ〉〈ψ|) + r(e iφ |w〉〈ψ | + e −iφ |ψ〉〈w|)] (1) where, r is a constant, and φ is a phase. The initial state can be written as |ψ 〉 = x|w 〉 + √ 1 − x 2 |β〉, where |β 〉 is the orthogonal complement of the state |w〉. If the phase is given by φ = nπ(n is an integer), then the Hamiltonian finds the target state with probability one, but if not, the probability to find the target becomes 1 − O(x 2) ≈ 1 − O(1/N).

•Apr 16, 2002•0 citations

Quantum-circuit model of Hamiltonian search algorithms

Jérémie Roland, Nicolas J. Cerf

We analyze three different quantum search algorithms, namely, the traditional circuit-based Grover's algorithm, its continuous-time analog by Hamiltonian evolution, and the quantum search by local adiabatic evolution. We show that these algorithms are closely related in the sense that they all perform a rotation, at a constant angular velocity, from a uniform superposition of all states to the solution state. This makes it possible to implement the two Hamiltonian-evolution algorithms on a conventional quantum circuit, while keeping the quadratic speedup of Grover's original algorithm. It also clarifies the link between the adiabatic search algorithm and Grover's algorithm.

arXiv:quant-ph/0302138•Physical Review A•Dec 15, 2003•45 citations
We present new intuition behind Grover's quantum search algorithm by means of a Hamiltonian. Given a black-box Boolean function f mapping strings of length n into {0,1} such that f(w) = 1 for exactly one string w, L. K. Grover describes a quantum algorithm that finds w in O(2^{n/2}) time. Farhi & Gutmann show that w can also be found in the same amount time by letting the quantum system evolve according to a simple Hamiltonian depending only on f. Their system evolves along a path far from that taken by Grover's original algorithm, however. The current paper presents an equally simple Hamiltonian matching Grover's algorithm step for step. The new Hamiltonian is similar in appearance from that of Farhi & Gutmann, but has some important differences, and provides new intuition for Grover's algorithm itself. This intuition both contrasts with and supplements other explanations of Grover's algorithm as a rotation in two dimensions, and suggests that the Hamiltonian-based approach to quantum algorithms can provide a useful heuristic for discovering new quantum algorithms.
We examine the driving Hamiltonian in the analog analogue of Grover's algorithm by Farhi and Gutmann. For a quantum system with a given Hamiltonian E∣w><w∣E|w> < w|E∣w><w∣, we explicitly show that while the driving Hamiltonian E∣s><s∣E|s> < s|E∣s><s∣ optimally produces the state ∣w>|w>∣w> from an initial state ∣s>|s>∣s>, the driving Hamiltonian E′∣s><s∣(E′≠E)E^{\prime}|s> < s|(E^{\prime} \ne E)E′∣s><s∣(E′=E) does not provide any speedup compared even with a classical computation.
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.
Grover's search algorithm was originally proposed for circuit-based quantum computers. A crucial part of it is to query an oracle -- a black-box unitary operation. Generation of this oracle is formally beyond the original algorithm design. Here, we propose a realization of Grover's oracle for a large class of searching problems using a quantum annealing step. The time of this step grows only logarithmically with the size of the database. This suggests an efficient path to application of Grover's algorithm to practically important problems, such as finding the ground state of a Hamiltonian with a spectral gap over its ground state.
One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.
The Analysis on the Running Time of the Generalized Quantum Search Hamiltonian : O(N1/4)O(N^{1/4})O(N1/4) and O(1) Time Resources
Farhi et al. suggested the analogue quantum search Hamiltonian and Fenner also proposed the intuitive quantum search Hamiltonian. Recently the generalized quantum search Hamiltonian containning hamiltonians of Farhi et al. and Fenner was presented in quant-ph/0110020. In this letter, we analyze the running time of the generalized quantum search Hamiltonian. Our analysis displays two surprising results. The first is the exponential speedup(T = O(N 1/4)), and the next O(1) time resource. In 1996, Farhi et al. suggested the analogue quantum search algorithm based on Hamiltonian evolution.[1] The Hamiltonian to solve the search problem is Haf = Ed(|w〉〈w|+|ψ〉〈ψ|). In the Hamiltonian Haf, |w 〉 is the target state that we have to find, |ψ 〉 is the initial state that is a superposition of N states, E is a constant in unit of energy, and d is a constant. Fenner [2] also proposed the quantum search Hamiltonian Hif = −2iEx(|w〉〈ψ | − |ψ〉〈w|), where x = 〈w|ψ 〉 ≈ 1 √. The Hamiltonian Hif is called the intuitive quantum search Hamil-N tonian. Recently, the generalized quantum search Hamiltonian including hamiltonians of Farhi et al. and Fenner was presented.[3] The Hamiltonian is as follows: Hyj = E[d(|w〉〈w | + |ψ〉〈ψ|) + r(e iφ |w〉〈ψ | + e −iφ |ψ〉〈w|)] (1) where, r is a constant, and φ is a phase. The initial state can be written as |ψ 〉 = x|w 〉 + √ 1 − x 2 |β〉, where |β 〉 is the orthogonal complement of the state |w〉. If the phase is given by φ = nπ(n is an integer), then the Hamiltonian finds the target state with probability one, but if not, the probability to find the target becomes 1 − O(x 2) ≈ 1 − O(1/N).
We analyze three different quantum search algorithms, namely, the traditional circuit-based Grover's algorithm, its continuous-time analog by Hamiltonian evolution, and the quantum search by local adiabatic evolution. We show that these algorithms are closely related in the sense that they all perform a rotation, at a constant angular velocity, from a uniform superposition of all states to the solution state. This makes it possible to implement the two Hamiltonian-evolution algorithms on a conventional quantum circuit, while keeping the quadratic speedup of Grover's original algorithm. It also clarifies the link between the adiabatic search algorithm and Grover's algorithm.