Quantum Mechanics Helps in Searching for a Needle in a Haystack

Abstract

Quantum mechanics can speed up a range of search applications over unsorted data. For example, imagine a phone directory containing $N$ names arranged in completely random order. To find someone's phone number with a probability of 50%, any classical algorithm (whether deterministic or probabilistic) will need to access the database a minimum of $0.5N$ times. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. As a result, the desired phone number can be obtained in only $O(\sqrt{N})$ accesses to the database.