Grover’s Search Algorithm

Let’s develop our first Quantum Search Algorithm, Gover’s algorithm.

Let’s say we have a collection of 16 items each represented by their current Binary position in the collection. So we item is represented by 4 bit system as shown below

Ordered Item Collection

Now Let’s say we shuffle the above collection randomly, and so the collection above would look something like below

Randomly Shuffled Item Collection

Now searching any particular item (say 0101) would take us on an average 8 steps (N/2 steps in general). But this is where we use Quantum Computing using Grover’s search algorithm to do this in 4 steps (n = Square Root of N).

To keep this problem simple lets assume the list is of size 4 (N=4) and so each item would be represented by 2 bits (n = Square Root of N)

The Grover’s algorithm on high level works with 2 ideas in each step/ iteration:

1. Search Oracle: Negating the exact position (computational basis) we are looking for
2. Amplitude Amplification: Amplifying the amplitude of the exact position we found with the Search Oracle above.

Now first part of the problem would be represent this list with a Quantum State, and again like always, all we would need is H, Hadamard gate

Preparing all possible items, each computation basis representing one possible item

|ψ⟩ = 1/2 |00⟩ + 1/2 |01⟩ + 1/2 |10⟩ + 1/2 |11⟩

Note in the above state |ψ⟩, each of the basis states has the coefficient as 1/2, so if we measure the |ψ⟩ currently it could be in any of the four states with equal probability (=1/4 for each basis).

|ψ⟩ in terms of coefficients/ amplitude (left) & Probability of being in any of the 4 states (right)

Now let’s assume we were searching for “00" item. To do that here, we would want to change |ψ⟩ to something in which coefficient of |00⟩ is sufficiently higher than coefficient of |01⟩, |10⟩ & |11⟩. This is required so that now when we measure the modified |ψ⟩, it has highest (say almost =1) change of being in state |00⟩.

Now let’s make use of the circuit we made earlier, Selector Circuit 2
as this circuit would make the sign flip for the |00⟩ basis, this is what we call the Oracle circuit, as mentioned in step 1 above

Now in our problem for getting |00⟩ after measurement, we have progressed a bit closed as we converted |ψ⟩ to |ω⟩
|ω⟩ = — 1/2 |00⟩ + 1/2 |01⟩ + 1/2 |10⟩ + 1/2 |11⟩

Now though you might think we are done here, the |00⟩ basis already has the sign change and we have searched the element, but this is where superposition comes back, when we measure this qubit state, it again has same probability for being in any of the four stages.

|ψ⟩ in terms of coefficients/ amplitude (left) & Probability of being in any of the 4 states (right)

Now this is where we need 2nd step of Amplitude Amplification as mentioned above. And we have made this circuit as well in the post before, as Reflection Circuit 1.

Amplitude Amplification Circuit

|ω⟩ = — 1/2 |00⟩ + 1/2 |01⟩ + 1/2 |10⟩ + 1/2 |11⟩
|ω1⟩ = Hq1 ( Hq0 ( |ω⟩)
where Hq0 is the heramard Gate at qubit position 0 & Hq1 is the heramard Gate at qubit position 1.

Similarly applying Z0 & Z1 Gate for 0 & 1 Qubit respectively, followed by CZ Gate
|ω2⟩ = CZ(Z1(Z0 (|ω1⟩)))
= CZ(Z1(Z0 (1/2 |00⟩ — 1/2 |01⟩ — 1/2 |10⟩ — 1/2 |11⟩ )))
= CZ(Z1(1/2 |00⟩+1/2 |01⟩ — 1/2 |10⟩+1/2 |11⟩ ))
= CZ(1/2 |00⟩+1/2 |01⟩ +1/2 |10⟩ — 1/2 |11⟩ )
|ω2⟩ = 1/2 |00⟩+1/2 |01⟩ +1/2 |10⟩ + 1/2 |11⟩

Check how we prepared |ψ⟩ at the very first step to confirm
|ω2⟩ = H|0⟩ ⊗ H|0⟩

Now if we apply heramard Gate to each of the qubit after state |ω2⟩, we should come out of superposition as, each Quantum Gate is inverse of itself & so is H Gate, i.e.

H H = I

Output = H0(H1(|ω2⟩) = H H|0⟩ ⊗ H H|0⟩ = |0⟩ ⊗ |0⟩ = |00⟩,
Output = 1 |00⟩+ 0 |01⟩ +0|10⟩ + 0|11⟩

O/P state in terms of coefficients/ amplitude (left) & Probability of being in any of the 4 states (right)

So the end to end Circuit for searching “00" is below:

2 Qubit Grover Circuit for 00

Similarly now check below Circuits for the remaining elements

For 11

2 Qubit Grover Circuit for 11

Please check yourslef the below value of each of the States above:

|ψ⟩ = 1/2 |00⟩+1/2 |01⟩ +1/2 |10⟩ + 1/2 |11⟩
|ω⟩ = 1/2 |00⟩+1/2 |01⟩ +1/2 |10⟩ — 1/2 |11⟩
|ω1⟩ = 1/2 |00⟩+1/2 |10⟩ +1/2 |01⟩ — 1/2 |11⟩
|ω2⟩ = 1/2 |00⟩ — 1/2 |10⟩ — 1/2 |01⟩ — 1/2 |11⟩
Again Check
|ω2⟩ = H|1⟩ ⊗ H|1⟩
Output = H0 ( H1 (|ω2⟩)) = HH |1⟩ ⊗ HH|1⟩ = |1⟩ ⊗ |1⟩ = |11⟩

Output = 0|00⟩+ 0 |01⟩ +0|10⟩ + 1|11⟩

For 01

2 Qubit Grover Circuit for 01

For 10

2 Qubit Grover Circuit for 10

So done, we have implemented 2 qubits Grover’s Search Algorithm using Quantum circuits.

Next step for you would be to try to do this for 8 elements array using 3 qubit circuits for developing the better intuition for this whole thing.

Next steps for this series would be
1. Implementing the above search algorithm using one of the programming languages
2. More Mathematical explanation of the above algorithms, without Circuit Diagrams

This post is 5th part of the “Quantum Computing 101” Series …