Implementing Grover’s Algorithm

We diagram the Grover algorithm

According to the above diagram 

Also,

Next we apply the Grover diffusion operator



We repeat this series of gates the integer value of  (Sqrt[π (2^n)/4]) times prior to making a measurement. Lets translate this procedure into code for n=7 qubit.

(* we construct the 7-qubit input register *)
zerobit={1,0};
onebit={0,1};
(* nullket represents the upper register input *)
nullket=Flatten[KroneckerProduct[zerobit,zerobit,zerobit,zerobit,zerobit,zerobit,zerobit]];

Hadamard=1/Sqrt[2]{{1,1},{1,-1}};

(* apply the (H^(⊗7)) gate on the upper register *)
Hadtimesn=KroneckerProduct[Hadamard,Hadamard,Hadamard,Hadamard,Hadamard,Hadamard,Hadamard];

MatrixForm[Hadtimesn];

(* phi represent state |ϕ> defined above *)
phi=Hadtimesn.nullket;

(* tagnumber q is an arbitary number 0 < q < 127 *)
tagnumber=RandomChoice[Table[i,{i,0,2^7-1}]];

(* construct the oracle for this tagnumber *)
V=DiagonalMatrix[Table[If[i==tagnumber,-1,1],{i,0,2^7-1}]];

(* construct gate W *)

W=2 KroneckerProduct[phi,phi]-IdentityMatrix[2^7];

MatrixForm[W];

(* Grover operator G = W V *)

(* Grover operator *)
G=W.V;

(* Construct the first six Grover iteration, grover1, grover2 ...grover 6 is the output register to be measured *)

grover1=N[G.phi];
grover2=N[G.grover1];
grover3=N[G.grover2];
grover4=N[G.grover3];
grover5=N[G.grover4];
grover6=N[G.grover5];

Measurements

binaryoutput=Table[IntegerDigits[i,2,7],{i,0,2^7-1}];

We assume that six Grover iterations have been performed and the final state of the upper register |ψ⟩  is given by grover6. Using the Born rule, the probability to measure state |k⟩ is  |⟨k|ψ⟩((|)^2)

measurement:=RandomChoice[grover6^2->binaryoutput];

measurement
FromDigits[%,2]

Actual tag number for item is

tagnumber

Exercises

(1) Run the code with only one Grover iteration. Tabulate the number of repeated measurements necessary to arrive at the correct tag number. Repeat for two Grover iterations. How do these results compare with the results obtained above, using 6 Grover iterations.

(2) Construct codes with 7,8,9,10 Grover iterations. Which of these gives the optimal success rate.