# Tight bounds on quantum searching

@article{Boyer1996TightBO, title={Tight bounds on quantum searching}, author={Michel Boyer and Gilles Brassard and Peter Hoeyer and Alain Tapp}, journal={Protein Science}, year={1996}, volume={46}, pages={493-505} }

We provide a tight analysis of Grover''s recent algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an… Expand

#### 1,013 Citations

0 v 2 2 D ec 1 99 9 Grover ’ s quantum searching algorithm is optimal

- 1999

I show that for any number of oracle lookups up to about π/4 √ N , Grover's quantum searching algorithm gives the maximal possible probability of finding the desired element. I explain why this is… Expand

From linear combination of quantum states to Grover's searching algorithm

- Mathematics, Physics
- 2018

Linear combination of unitaries (LCU for short) is one of the most important techniques in designing quantum algorithms. In this paper, we propose a new quantum algorithm in three different forms to… Expand

Stability of Grover’s algorithm in respect to perturbations in quantum circuit

- Mathematics
- 2017

Quantum computing uses a special kind of superposition, which allows exponentially many logical states simultaneously. This is a powerful feat, and no classical computer can achieve it. Quantum… Expand

Grover's Quantum Search Algorithm and Diophantine Approximation

- Physics, Computer Science
- ArXiv
- 2005

This work considers the following computational problem: A subset of marked elements is given whose number of elements is either M or K, and shows how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Expand

An Exact Quantum Search Algorithm with Arbitrary Database

- Mathematics
- 2014

In standard Grover’s algorithm for quantum searching, the probability of finding a marked state is not exactly 1, and some modified versions of Grover’s algorithm that search a marked state from an… Expand

Deriving Grover's lower bound from simple physical principles

- Mathematics, Physics
- 2016

Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms. Quantum interference between… Expand

Noise in Grover’s quantum search algorithm

- Physics
- 1999

Grover's quantum algorithm improves any classical search algorithm. We show how random Gaussian noise at each step of the algorithm can be modeled easily because of the exact recursion formulas… Expand

A panoply of quantum algorithms

- Computer Science, Mathematics
- 2006

A breadth-first search that is faster than Θ(edges) in a dense graph, maximum-points-on-a-line in O(N3/2 lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Expand

Asymptotic Quantum Search and a Quantum Algorithm for Calculation of a Lower Bound of the Probability of Finding a Diophantine Equation That Accepts Integer Solutions

- Mathematics, Physics
- 2008

Several mathematical problems can be modeled as a search in a database. An example is the problem of finding the minimum of a function. Quantum algorithms for solving this problem have been proposed… Expand

Quantum Rough Counting and Its Application to Grover's Search Algorithm

- Computer Science
- 2018 3rd International Conference on Computer and Communication Systems (ICCCS)
- 2018

An analysis of expected probability of the proposed algorithm taking into account the problem size, the number of satisfying items and the query complexity to show that the proposed modified Grover's search is optimal. Expand

#### References

SHOWING 1-10 OF 24 REFERENCES

Quantum cryptanalysis of hash and claw-free functions

- Mathematics, Computer Science
- SIGA
- 1997

A quantum algorithm that finds collisions in arbitrary functions after only O(3√N/τ) expected evaluations of the function, more efficient than the best possible classical algorithm, even allowing probabilism. Expand

A fast quantum mechanical algorithm for database search

- Computer Science, Physics
- STOC '96
- 1996

In early 1994, it was demonstrated that a quantum mechanical computer could efficiently solve a well-known problem for which there was no known efficient algorithm using classical computers, i.e. testing whether or not a given integer, N, is prime, in a time which is a finite power of o (logN) . Expand

Quantum Mechanics Helps in Searching for a Needle in a Haystack

- Physics
- 1997

Quantum mechanics can speed up a range of search applications over unsorted data. For example, imagine a phone directory containing $N$ names arranged in completely random order. To find someone's… Expand

Algorithms for quantum computation: discrete logarithms and factoring

- Mathematics, Computer Science
- Proceedings 35th Annual Symposium on Foundations of Computer Science
- 1994

Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored are given. Expand

Searching a Quantum Phone Book

- Physics
- Science
- 1997

Finding a phone number in a directory when one knows the name is easy; much harder is finding the name given the number. On average, a search algorithm will have to scan half the total number of… Expand

Strengths and Weaknesses of Quantum Computing

- Mathematics, Physics
- SIAM J. Comput.
- 1997

It is proved that relative to an oracle chosen uniformly at random with probability 1 the class $\NP$ cannot be solved on a quantum Turing machine (QTM) in time $o(2^{n/2})$. Expand

Elementary gates for quantum computation.

- Physics, Medicine
- Physical review. A, Atomic, molecular, and optical physics
- 1995

U(2) gates are derived, which derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and make some observations about the number of unitary operations on arbitrarily many bits. Expand

Computers and Intractability: A Guide to the Theory of NP-Completeness

- Computer Science, Mathematics
- 1978

Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the problem of optimal compression of propositional Horn production rule knowledge… Expand

Quantum measurements and the Abelian Stabilizer Problem

- Computer Science, Mathematics
- Electron. Colloquium Comput. Complex.
- 1996

A polynomial quantum algorithm for the Abelian stabilizer problem which includes both factoring and the discrete logarithm is presented, based on a procedure for measuring an eigenvalue of a unitary operator. Expand

Rapid solution of problems by quantum computation

- Mathematics
- Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences
- 1992

A class of problems is described which can be solved more efficiently by quantum computation than by any classical or stochastic method. The quantum computation solves the problem with certainty in… Expand