Trade-offs in the quantum search algorithm

Lov K. Grover
Phys. Rev. A 66, 052314 – Published 21 November 2002
PDFExport Citation

Abstract

Quantum search has been proved to be the best possible algorithm for the exhaustive search problem in the sense that the number of queries it requires cannot be reduced. However, the number of nonquery operations, and thus the total number of operations, can be reduced. The number of nonquery unitary operations can be reduced by a factor of logN/αlog(logN) while increasing the number of queries by a factor of only [1+(logN)α]. For example, by choosing α to be O(logN/log(logN)), the number of nonquery unitary operations can be reduced by 40% while increasing the number of queries by just two.

  • Received 19 December 2001

DOI:https://doi.org/10.1103/PhysRevA.66.052314

©2002 American Physical Society

Authors & Affiliations

Lov K. Grover*

  • 1D435 Bell Laboratories, Lucent Technologies, 600-700 Mountain Avenue, Murray Hill, New Jersey 07974

  • *Email address: lkgrover@bell-labs.com

References (Subscription Required)

Click to Expand
Issue

Vol. 66, Iss. 5 — November 2002

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×