Quantum Computers Can Search Arbitrarily Large Databases by a Single Query

Lov K. Grover
Phys. Rev. Lett. 79, 4709 – Published 8 December 1997
PDFExport Citation

Abstract

This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database can search a database for a unique item satisfying a given condition, in a single query [a query is defined as any question to the database to which the database has to return a (yes/no answer]. A classical algorithm will be limited to the information theoretic bound of at least log2N queries, which it would achieve by using a binary search.

  • Received 16 June 1997

DOI:https://doi.org/10.1103/PhysRevLett.79.4709

©1997 American Physical Society

Authors & Affiliations

Lov K. Grover

  • 3C-404A Bell Labs, 600 Mountain Avenue, Murray Hill, New Jersey 07974

References (Subscription Required)

Click to Expand
Issue

Vol. 79, Iss. 23 — 8 December 1997

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 Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×