Quantum Mechanics Helps in Searching for a Needle in a Haystack

TLDR

Quantum mechanics can accelerate searches on unsorted data, as illustrated by a randomly ordered phone directory where classical algorithms require O(N) accesses for a 50% success probability. Quantum systems exploit superposition and phase adjustments to reinforce correct outcomes while canceling incorrect ones, enabling simultaneous examination of many entries. This approach reduces the required database accesses to O(√N) to retrieve a phone number.

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 O(N) 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.