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

A new adiabatic quantum search algorithm

Haitham Zaraket, V. Bagnulo, Jakub Kettner, R. Kobes, G. Kunstatter

Published Aug 11, 2003• 0 citations
arXivHTMLPDF

Abstract

We present a new adiabatic quantum algorithm for searching over structured databases. The new algorithm is optimized using a simplified complexity analysis.
DOI
10.48550/arxiv.quant-ph/0308060

Related papers

Complete Adiabatic Quantum Search in Unsorted Databases

Nanyang Xu, Xinhua Peng, Mingjun Shi +1 more

We propose a new adiabatic algorithm for the unsorted database search problem. This algorithm saves two thirds of qubits than Grover's algorithm in realizations. Meanwhile, we analyze the time complexity of the algorithm by both perturbative method and numerical simulation. The results show it provides a better speedup than the previous adiabatic search algorithm.

arXiv:0811.0663•Nov 5, 2008•0 citations

A Non-Oracle Quantum Search Algorithm and Its Experimental Implementation

Nanyang Xu, Zhu Jin, Xinhua Peng +2 more

Grover's algorithm has achieved great success. But quantum search algorithms still are not complete algorithms because of Grover's Oracle. We concerned on this problem and present a new quantum search algorithm in adiabatic model without Oracle. We analyze the general difficulties in quantum search algorithms and show how to solve them in the present algorithm. As well this algorithm could deal with both single-solution and multi-solution searches without modification. We also implement this algorithm on NMR quantum computer. It is the first experiment which perform a real quantum database search rather than a marked-state search.

arXiv:0809.0664•Sep 3, 2008•2 citations

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

Quantum search by partial adiabatic evolution

Yingyu Zhang, Songfeng Lu

A quantum search algorithm based on the partial adiabatic evolution [Phys. Rev. A 80, 052328 (2009)] is provided. We calculate its time complexity and find that the algorithm improves the time complexity, which is $O(\sqrt{N/M})$, of the local adiabatic search algorithm [Phys. Rev. A 65, 042308 (2002)] to $O(\sqrt{N}/M)$.

arXiv:1007.1528•Physical Review A•Sep 22, 2010•16 citations

Quantum search in structured database using local adiabatic evolution and spectral methods

Rahime Sufiani, N. Bahari

arXiv:1208.0262•Quantum Information Processing•Mar 19, 2013•2 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
Grover's algorithm has achieved great success. But quantum search algorithms still are not complete algorithms because of Grover's Oracle. We concerned on this problem and present a new quantum search algorithm in adiabatic model without Oracle. We analyze the general difficulties in quantum search algorithms and show how to solve them in the present algorithm. As well this algorithm could deal with both single-solution and multi-solution searches without modification. We also implement this algorithm on NMR quantum computer. It is the first experiment which perform a real quantum database search rather than a marked-state search.
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.
A quantum search algorithm based on the partial adiabatic evolution [Phys. Rev. A 80, 052328 (2009)] is provided. We calculate its time complexity and find that the algorithm improves the time complexity, which is O(N/M)O(\sqrt{N/M})O(N/M​), of the local adiabatic search algorithm [Phys. Rev. A 65, 042308 (2002)] to O(N/M)O(\sqrt{N}/M)O(N​/M).
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.