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
Now Let’s say we shuffle the above collection randomly, and so the collection above would look something like below
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:
- Search Oracle: Negating the exact position (computational basis) we are looking for
- 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
|ψ⟩ = 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).
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.
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.
|ω⟩ = — 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⟩
So the end to end Circuit for searching “00" is below:
Similarly now check below Circuits for the remaining elements
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
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 …