文档介绍：A fast quantum mechanical algorithm for database search
Lov K. Grover
3C-404A, Bell Labs
600 Mountain Avenue
Murray Hill NJ 07974
******@bell-
Summary This paper applies puting to a
Imagine a phone directory containing N names mundane problem in information processing and pre-
arranged pletely random order. In order to find sents an algorithm that is significantly faster than any
classical algorithm can be. The problem is this: there is
1
someone's phone number with a probability of -- , any an unsorted database containing N items out of which
2 just one item satisfies a given condition - that one item
classical algorithm (whether deterministic or probabilis- has to be retrieved. Once an item is examined, it is pos-
N
tic) will need to look at a minimum of ---- names. Quan- sible to tell whether or not it satisfies the condition in
2 one step. However, there does not exist any sorting on
tum mechanical systems can be in a superposition of the database that would aid its selection. The most effi-
states and simultaneously examine multiple names. By cient classical algorithm for this is to examine the items
properly adjusting the phases of various operations, suc- in the database one by one. If an item satisfies the
putations reinforce each other while others required condition stop; if it does not, keep track of this
interfere randomly. As a result,