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 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