Grover’s quantum searching algorithm is optimal
- 1 October 1999
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 60 (4) , 2746-2751
- https://doi.org/10.1103/physreva.60.2746
Abstract
I show that for any number of oracle lookups up to about Grover’s quantum searching algorithm gives the maximal possible probability of finding the desired element. I explain why this is also true for quantum algorithms which use measurements during the computation. I also show that unfortunately quantum searching cannot be parallelized better than by assigning different parts of the search space to independent quantum computers.
Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Tight Bounds on Quantum SearchingFortschritte der Physik, 1998
- Strengths and Weaknesses of Quantum ComputingSIAM Journal on Computing, 1997
- Quantum Mechanics Helps in Searching for a Needle in a HaystackPhysical Review Letters, 1997