GROVER’S ALGORITHM
Grover’s algorithm is a search algorithm designed for use by quantum computers, which was invented by Lov Grover in 1996. This algorithm demonstrates the unparalleled speed of a quantum computer in the task of searching databases. It can also increase the speed of unstructured searches quadratically, but it has many more uses than just that. You can also use it as a “hack” to quadratically improve the run-time of many other algorithms. This “hack” is called the amplitude amplification trick. But first, let’s investigate the unstructured search problem.
Unstructured Search
Pretend you are given a long list (as in very long) of N items, one of which has a specific property that you wish to find. For example, suppose that you have 1,000,000 Among Us players, and you wish to find the only Imposter among the other 999,999 Crewmates.
Using classical computation, it takes about N/2 (in this case 1,000,000/2 = 500,000) emergency meetings (we’ll stick with the Among Us analogy) to expose the Imposter, and in the worst case, all N = 1,000,000 emergency meetings.
However, on a quantum computer, we can expose the Imposter in approximately √N = √1,000,000 = 1,000 emergency meetings, with the help of the aforementioned amplitude amplification trick. A quadratic speedup saves substantial amounts of time as the list grows larger and larger (as N increases). Alright, so now let’s move on to how Grover’s Algorithm works.
The Oracle
One common way to transform the list of N items is to map it in terms of a function f, which outputs f(I) = 1 for the Imposter (I) and f(C) = 0 for all the other Crewmates (C). The inputs are provided to the quantum computer in a superposition, in a unitary matrix known as an oracle. The first step is to make a binary (0 or 1) encoding of all the Crewmates C,I ∈ {0,1}^n, so that N (the 1,000,000 Among Us players) = 2^n; thus we can represent this information as qubits (quantum bits) on our quantum computer. Next, we make the oracle matrix U_f act on the base states ⎜C⟩ such that U_f (⎜C⟩) = [(-1)^f(C)]×⎜C⟩. Note that when the input is a Crewmate, the oracle has no affect on the state. On the other hand, when the oracle is applied to the base state ⎜I⟩, it maps U_f (⎜I⟩) = −⎜I⟩, thereby exposing the Imposter!
Amplitude Amplification
Obviously, before the first meeting, we have no idea who the Imposter could be. It could be Red, or it could be Blue, or any other of the 999,998 other players. This can be expressed in terms of a uniform superposition:
As with qubits and quantum states, if we were to measure the state {⎜I⟩}, it would collapse into of the base states with probability 1/N = 1/(2^n). Then our chance of voting out the Imposter I would be about 1 in 2^n. Therefore, we would need to have N = 2^n emergency meetings to find the Imposter. Allow me to introduce amplitude amplification, which is how a quantum computer increases this probability. Basically, it amplifies the amplitude of the Imposter and shrinks the amplitude of all the Crewmates.
This can be interpreted geometrically, with the two states we are considering, ⎜I⟩, and the uniform superposition⎜s⟩. These vectors are in a 2D plane in the vector space C^n. They are not exactly perpedicaulr, as⎜I⟩ is in a superposition with amplitude √N. We therefore introduce the additional state ⎜s’⟩ that is in the span of the 2 vectors and perpendicular to⎜I⟩, obtained by removing⎜I⟩ from⎜s⟩.
Step 0:
The amplitude amplification process starts with the uniform superposition state ⎜I⟩. At time t = 0, the initial state is⎜ψ_0⟩ =⎜s⟩.
Step 1:
Then we apply the oracle reflection U_f to the state U_f(⎜ψ⟩ = ⎜ψ_t’⟩. This makes the amplitude in front of the⎜I⟩ state negative, which in turn reduces the average amplitude.
Step 2:
We apply another reflection U_s about the state⎜s⟩; this reflection is written as U_s = (2)(⎜s⟩)(⟨s⎜)−1. It maps the state to⎜ψ_t’⟩ and finishes the transformation ⎜ψ_(t+1)⟩ = (U_s)(U_f)(⎜ψ_t⟩).
Two reflections are equivalent to a rotation; the transformation (U_s)(U_f) rotates the initial state⎜s⟩ closer towards the Imposter⎜I⟩. Since the average amplitude was lowered by the first reflection, the negative amplitude of⎜I⟩ is now approximately 3 times its original value, while the Crewmate⎜C⟩ amplitudes have decreased. Now we repeat this process several times.
After t steps, the state will have become [((U_s)(U_f))^t](⎜ψ_0⟩). How many times will we need to apply the rotation then? The answer is about √N times. The amplitude of the state⎜I⟩ grows linearly with the number of applications, which is about (t)(√N). The vector space’s dimension is a square root, since we are dealing with amplitudes, and not probabilities. As a result, both the amplitude and probability are being amplified in this process.
Grover’s Algorithm Examples
Circuit 1: N=2, Imposter = 00
This is what the quantum circuit looks like: (created with IBM Quantum Experience)
Circuit 2: N = 2, Imposter = 01
This is what the quantum circuit looks like: (created with IBM Quantum Experience)
Circuit 3: N = 2, Imposter = 10
This is what the quantum circuit looks like: (created with IBM Quantum Experience)
Circuit 4: N = 2, Imposter = 11
This is what the quantum circuit looks like: (created with IBM Quantum Experience)
Key Takeaways
- Grover’s Algorithm is an algorithm used by quantum computers to perform unstructured searches in searching databases.
- You can use it to quadratically improve the run-time of other algorithms, using a hack called amplitude amplification.
- Amplitude amplification increases the probability of finding unique item w among a list of items N.
- It does this by applying oracle reflections to the uniform superposition state (which can be represented geometrically) and repeating this process to “single out” item w.
- The oracle is a unitary matrix, with its inputs in superposition; the inputs are the items in the list N, which when provided to function f, which outputs f(w) = 1 for the unique item and f(x) = 0 for all the other items.
