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:2106.02703 · Physical Review A

Dissipative search of an unstructured database

ARMEN E. ALLAHVERDYAN, David Petrosyan

Published Mar 25, 2022• 8 citations
arXivHTMLPDF

Abstract

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

DOI
10.1103/physreva.105.032447

Related papers

Quantum search algorithm in unstructured database

A. D. Kozhukhivskyi

Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.

Scientific Notes of the State University of Telecommunications•Jan 1, 2022•1 citation

Classical dissipative search of unstructured database

A. E. Allahverdyan, Y. Bisharyan

We propose a physical realization of the unstructured database search that works via classical, dissipative model of spherical spins. The database is implemented via spin-spin couplings, where the selected coupling refers to a larger ferromagnetic interaction between two selected spins. The low-temperature equilibrium of this model leads to magnetization strongly concentrated on the selected spins, which means that the search is complete. The search time refers to the relaxation time to equilibrium from a homogeneous initial state, and is described via Langevin equations. This time scales as ${\cal O}(M^a)$ with $a<1/2$, where $M$ is the database volume. This is faster than Grover's search, showing how a dissipative, classical analog computer can overcome the quantum unitary computer.

cond-mat.stat-mechCross-listedarXiv:2606.18835•Jun 18, 2026•0 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

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

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooks•Apr 26, 2011•0 citations

Grover’s Search Algorithm

Mikio Nakahara

Suppose there is a stack of N unstructured files and we want to find a particular file (or files) out of the N files. To find someone’s phone number in a telephone directory is an easy structured datebase search problem, while to find a person’s name who has a particular phone number is a more difficult unstructured database seach problem, with which we are concerned in this chapter. It is required to take O(N) steps on average if a classical algorithm is employed. If we check the files one by one, we will hit the right file with probability 1/2 after N/2 files are examined. It turns out that this takes only O( √ N) steps with a quantum algorithm, first discovered by Grover [1, 2, 3]. Our presentation in this chapter closely follows [4] and [5].

CRC Press eBooks•Mar 11, 2008•0 citations
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).
Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.
We propose a physical realization of the unstructured database search that works via classical, dissipative model of spherical spins. The database is implemented via spin-spin couplings, where the selected coupling refers to a larger ferromagnetic interaction between two selected spins. The low-temperature equilibrium of this model leads to magnetization strongly concentrated on the selected spins, which means that the search is complete. The search time refers to the relaxation time to equilibrium from a homogeneous initial state, and is described via Langevin equations. This time scales as O(Ma){\cal O}(M^a)O(Ma) with a<1/2a<1/2a<1/2, where MMM is the database volume. This is faster than Grover's search, showing how a dissipative, classical analog computer can overcome the quantum unitary computer.
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.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
Suppose there is a stack of N unstructured files and we want to find a particular file (or files) out of the N files. To find someone’s phone number in a telephone directory is an easy structured datebase search problem, while to find a person’s name who has a particular phone number is a more difficult unstructured database seach problem, with which we are concerned in this chapter. It is required to take O(N) steps on average if a classical algorithm is employed. If we check the files one by one, we will hit the right file with probability 1/2 after N/2 files are examined. It turns out that this takes only O( √ N) steps with a quantum algorithm, first discovered by Grover [1, 2, 3]. Our presentation in this chapter closely follows [4] and [5].