The Idea of Grover’s Algorithm

3 min readMar 30, 2024

#Quantum30 Cohort 04

Day 13

Date: 30th March, 2024.

Google | IBM Quantum Computing on slidesShare.

When the number xₐ satisfies f(xₐ)=1, it is needed to be found in a largely unsorted database, the qubits are set to be in a superposition state of all possible ID numbers {x = 0,1,2,…,N–1} as the initial state. To simplify the expression, the decimal notation is used for n-qubit.

For example,

|1⟩|0⟩|0⟩ is written as |4⟩. The initial state (Figure 6) can be written as;

Next, a quantum circuit is used to flip the phase of the state where x is equal to xₐ (Figure 7).

Then, the difference between the average of the probability amplitudes ρₐᵥₑ and the amplitude ρₓ is subtracted from the amplitude ρₐᵥₑ (Figure 8).

This operation is called inversion about the average.

Get Bushra Haque’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

As shown in the example with N=8 (n = 3), the probability amplitude of the target state |3⟩ goes up to 5/2√8
from 1/√8 after the operation, while the amplitudes for the rest of the states is reduced to 1/2√8. This result still satisfies:

Thus, the probability of finding the target state |3⟩ by measurement is

increased from 12.5% to 78.1%. If the operation is repeated one more time,

Thus, the probability (2𝜌𝑎𝑣𝑒 − 𝜌𝑥3)²
is increased to 94.5%. By performing inversion about the average multiple times, the probability of yielding the targeted ID xₐ by measurement can be boosted from the initial probability of 1/𝑁. Since finding an item from 𝑁 items takes 𝑁/2 operations on average, when 𝑁 is small, the quantum algorithm does not substantially exceed the

performance of classical algorithms.

0(√N)<(N/2) — — — — — — (18)

However, when 𝑁 is large, the advantage is quite distinct.

For example, when a database has 10⁶ items (e.g., for biometric authentications), Grover’s algorithm only needs 1000 steps to search an item while a classical algorithm needs 50,000 steps (Morsch, 2008).

Reference: