Effects of a random noisy oracle on search algorithm complexity

Published

Journal Article

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 [Formula Presented] neither the discrete- nor the continuous-time implementation of Grover’s algorithm is scalably robust to this error in the absence of error correction. © 2003 The American Physical Society.

Full Text

Duke Authors

Cited Authors

  • Shenvi, N; Brown, KR; Whaley, KB

Published Date

  • January 1, 2003

Published In

Volume / Issue

  • 68 / 5

Start / End Page

  • 11 -

Electronic International Standard Serial Number (EISSN)

  • 1094-1622

International Standard Serial Number (ISSN)

  • 1050-2947

Digital Object Identifier (DOI)

  • 10.1103/PhysRevA.68.052313

Citation Source

  • Scopus