Grover’s Algorithm is a quantum computing algorithm that can search databases much faster than a classical computer, using amplitude amplification, a property of quantum physics.
The Task
Suppose you are given a large database of N items. One of them has an ID that we want to locate, say, w. To find p, the marked item, using classical computation, one would have to check on average N/2 of the lists to see if their ID matched with w’s ID, and all N items in the worst case. However, using Grover’s Algorithm, one can find w in √N steps, a quadratic speedup.
Oracle
One way to find w is to create a function f such that f returns 0 when the ID does not match w’s and 1 if it does. Next, define an oracle matrix U.f (where . denotes sub) to act on basis states |x⟩ like
This way, when f(x) returns 0 (meaning that x does not match w), -1 to the f(x) evaluates to 1. When f(x) returns 1 (meaning that x matches w), -1 to the f(x) evaluates to -1. Therefore, if x is not p, the oracle does nothing. If x is w, it maps |w⟩ to -|w⟩. Geometrically, this unitary matrix corresponds to a reflection about the origin for an item w in a N dimensional vector space.
