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

Wiley eBooks

Searching in an Unsorted Database

Sándor Imre, Ferenc Balázs

Published Nov 19, 2004• 0 citations
Publisher

Abstract

This chapter contains sections titled: The Basic Grover Algorithm Quantum Counting Quantum Existence Testing Finding Extreme Values in an Unsorted Database The Generalized Grover Algorithm Further Reading
DOI
10.1002/9780470869048.ch7

Related papers

Grover's Algorithm

Richard J. Lipton, Kenneth W. Regan

This chapter contains sections titled: 13.1 Two Vectors, 13.2 The Algorithm, 13.3 The Analysis, 13.4 The General Case, with k Unknown, 13.5 Grover Approximate Counting, 13.6 Problems, 13.7 Summary and Notes

•Jan 1, 2014•0 citations

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

Tight Bounds on Quantum Searching

Michel Boyer, Gilles Brassard, Peter Høyer +1 more

This chapter contains sections titled: Abstract 1 Introduction 2 Overview of Grover's Algorithm 3 Finding a Unique Solution 4 The Case of Multiple Solutions 5 The Case t = N/4 6 Unknown Number of Solutions 7 An Improved Lower Bound 8 Conclusions and Future Directions Acknowledgements References

Wiley eBooks•Oct 12, 1999•153 citations

Quantum Algorithms

Julia Kempe

This chapter contains sections titled: Introduction Precursors Shor's Factoring Algorithm Grover's Algorithm Other Algorithms Recent Developments

Wiley eBooks•Nov 6, 2006•1 citation

A Modification of Grover's Algorithm as a Fast Database Search

Douglas Alan Ross

A modification of Grover's algorithm is proposed, which can be used directly as a fast database search. An explicit two q-bit example is displayed in detail. We discuss the case where the database has multiple entries corresponding to the same target value.

arXiv:quant-ph/9807078•Jul 28, 1998•4 citations

Quantum Walk Search Algorithms

Richard J. Lipton, Kenneth W. Regan

This chapter contains sections titled: 15.1 Search in Big Graphs, 15.2 General Quantum Walk for Graph Search, 15.3 Specifying the Generic Walk, 15.4 Adding the Data, 15.5 Toolkit Theorem for Quantum Walk Search, 15.6 Grover Search as Generic Walk, 15.7 Element Distinctness, 15.8 Subgraph Triangle Incidence, 15.9 Finding a Triangle, 15.10 Evaluating Formulas and Playing Chess, 15.11 Problems, 15.12 Summary and Notes

•Jan 1, 2014•0 citations
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.