Abstract
Grover’s algorithm provides a quadratic speed-up over classical algorithms for unstructured database or library searches. This paper examines the robustness of Grover’s search algorithm to a random phase error in the oracle and analyzes the complexity of the search process as a function of the scaling of the oracle error with database or library size. Both the discrete- and continuous-time implementations of the search algorithm are investigated. It is shown that unless the oracle phase error scales as neither the discrete- nor the continuous-time implementation of Grover’s algorithm is scalably robust to this error in the absence of error correction.
- Received 3 April 2003
DOI:https://doi.org/10.1103/PhysRevA.68.052313
©2003 American Physical Society