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.
- Received 20 February 1998
DOI:https://doi.org/10.1103/PhysRevA.60.2746
©1999 American Physical Society