Grover's Algorithm

Consider a list set of  N=(2^n)  objects. Lets identify them by the binary representation (({0,1})^(⊗n))  so that the 
first element in the list is ...000, the second ...001, the third ...010, and so on.  We want to find a particular member so we need a function that identifies it for us. The function should have the property that when the candidate is identified it should be flagged. 

i.e.  f(sought for candidate)=1, f(any other member)=0.  Question: how much effort is exerted in seeking that member. Example: suppose we have list of objects of N=(2^3) objects, since we agreed to label them according to the above convention we have the list

{111,110,101,100,011,010,001,000}

now have a function that identifies, or flags, the desired member. 
Example: I define such a  function called  threebitoracle[bit2,bit1,bit0] below

threebitoracle[bit2_,bit1_,bit0_]:=Module[{one={0,1},zero={1,0},oracle={0,0,0,1,0,0,0,0}},
ket2=If[bit2==0,zero,one];ket1=If[bit1==0,zero,one];ket0=If[bit0==0,zero,one];Flatten[KroneckerProduct[ket2,ket1,ket0]].oracle]

threebitoracle[1,1,1]

For (2^n) objects you can convince yourself that at worst you need N=(2^n) evaluations of f(x) in order to flag the object, or at best 1 evaluation. In the mean we expect N/2 evaluations of f(x) before we find our record.  Grover in 1996, pointed out that a quantum circuit requires only, on the average, (Sqrt[N]) evaluations of f(x) in order to find the candidate. So if n=20 and it takes 1 second for each evaluation of f(x) the classical algorithm takes on the order of 150 hours to complete the task. A quantum computer would take only 17 minutes.

First we need to need to follow the quantum protocal, introduced in our previous lectures,

(Subscript[U, f])|x ⟩|y ⟩ = |x ⟩|f(x)+y⟩ 

where f(x) is the "oracle" function defined above, and |x ⟩ is the input register. For |y⟩ we take
the superposition  H |1⟩ = (1/(Sqrt[2]))(|0 ⟩ - |1⟩). Therefore,

(Subscript[U, f])|x ⟩H|1 ⟩ = | x⟩ ⊗(1/(Sqrt[2]))(|f(x)+0 ⟩ - |f(x)+1⟩).   If f(x) =0 then

(Subscript[U, f])|x ⟩H|1 ⟩ = | x⟩ ⊗(1/(Sqrt[2]))(|0 ⟩ - |1⟩) = |x ⟩H|1 ⟩ 

and if If f(x) =1  then

(Subscript[U, f])|x ⟩H|1 ⟩ = | x⟩ ⊗(1/(Sqrt[2]))(|1 ⟩ - |0⟩) =- |x ⟩H|1 ⟩ 

Therefore we can write this as

(Subscript[U, f])|x ⟩H|1 ⟩ = (((-1))^(f(x) ))|x ⟩ H|1⟩


Thus this gate does not effect the first bit but we can think of it as an effective operator V acting
on the input register | x ⟩ so that

V | x ⟩= (((-1))^(f(x) ))|x ⟩   that is, V is simply the identity if |x ⟩ is not our candidate, but changes
the sign of | x ⟩ if it is. In this way it flags the solution. Convince your self that

V= I - 2 |ξ ⟩⟨ξ |   where |ξ ⟩  is the ket that the oracle is trying to find.

We now feed our quantum computer with the states (Subscript[|0⟩, n])H |1⟩ and we operate the Hadamard
gate (H^(⊗n))  on the register (Subscript[|0⟩, n]). From our previous work we know that

(H^(⊗n)) (Subscript[|0⟩, n]) = (1/(2^(n/2)))  (Underoverscript[(∑_( )^( )), 0, ((2^n)-1)]) |x⟩_n  ≡ |ϕ⟩  and so

(Subscript[U, f]) (H^(⊗n)) (Subscript[|0⟩, n])H|1 ⟩ =    (1/(2^(n/2)))  (Underoverscript[(∑_( )^( )), 0, ((2^n)-1)]) (((-1))^(f((Subscript[x, n])) ))(Subscript[|x ⟩, n]) H|1⟩ = V|ϕ⟩ H|1⟩

i.e. the input register looks like

V|ϕ⟩ = (1/(2^(n/2)))  (Underoverscript[(∑_( )^( )), 0, ((2^n)-1)]) (((-1))^(f((Subscript[x, n])) ))(Subscript[|x ⟩, n])   as output from this series of gates.  

Consider now,
 
 a new operator W = 2 |ϕ⟩⟨ϕ|-I  where |ϕ⟩ = (H^(⊗n)) (Subscript[|0⟩, n]). Lets consider its action on the state above.
 
  Let |x=ξ ⟩ ≡|ξ⟩ be the desired solution, then ⟨ϕ|ξ⟩ = (1/(2^(n/2))) = (1/(Sqrt[N])). Note that if N is very large this suggests that
  ⟨ξ|ϕ⟩≈0, i.e. they are almost orthogonal. This leads us to consider the following geometric picture.
  Let |ξ⟩ represent a vector on a 2 D plane that points along the vertical axis, and |η⟩ is a vector along the horizontal axis.
 |η ⟩  should have the properties ⟨ξ|η⟩=0, ⟨η|η⟩=1, and so we choose
  
  |η⟩ = (Sqrt[(N/(N-1))]) ( |ϕ ⟩ - (Sqrt[(1/N)]) |ξ ⟩ )    = (Sqrt[(N/(N-1))])  |ϕ ⟩ - (1/(Sqrt[N-1]))  |ξ ⟩ 
  
   We can then rewrite
  
(Eq. 1)     |  ϕ ⟩ =  (1/(Sqrt[N])) |ξ ⟩ + (Sqrt[((N-1)/N)]) |η ⟩    (note ⟨ϕ|ϕ⟩=1)      
  
 Now  V| ξ ⟩ = -|ξ⟩  V |η⟩ = |η⟩ and the 2 D matrix representation for V can be expressed
 
V = (({{⟨ξ|V|ξ⟩, ⟨ξ|V|η⟩}, {⟨η|V|ξ⟩, ⟨ξ|V|ξ⟩}})) = (({{-1, 0}, {0, 1}})) ; that is |ξ⟩ is represented as a vector (({{1}, {0}})) and |η⟩ as (({{0}, {1}}))

then the matrix representation for V transforms the basis states accordingly.
 

Consider now 

W = 2 |ϕ⟩⟨ϕ|-I  = 2   ( (1/(Sqrt[N])) |ξ ⟩ + (Sqrt[((N-1)/N)]) |η ⟩ )   ( (1/(Sqrt[N])) ⟨ ξ| + (Sqrt[((N-1)/N)]) ⟨η | )  - I

= 2 ( (1/N) |ξ ⟩ ⟨ ξ|  +  ((N-1)/N) |η ⟩ ⟨η | +  ((Sqrt[N-1])/N)| η ⟩⟨ξ | +  ((Sqrt[N-1])/N)| ξ ⟩⟨ξ |)  - I

  and the matrix representation for W becomes
  
  W = (({{⟨ξ|W|ξ⟩, ⟨ξ|W|η⟩}, {⟨η|W|ξ⟩, ⟨ξ|W|ξ⟩}})) = (({{(2/N)-1, ((2(Sqrt[N-1]))/N)}, {((2(Sqrt[N-1]))/(N )), 1-(2/N)}}))

Consider now the product  G =  W V   =

 (({{(2/N)-1, ((2(Sqrt[N-1]))/N)}, {((2(Sqrt[N-1]))/(N )), 1-(2/N)}})) (({{-1, 0}, {0, 1}})) =  (({{1-(2/N), ((2(Sqrt[N-1]))/N)}, {((-2(Sqrt[N-1]))/(N )), 1-(2/N)}}))

The structure of the G looks like a rotation matrix that has the generic form

 (({{cos θ, sin θ}, {-sin θ, cos θ}}))    where comparing with above we find tanθ  = (((2(Sqrt[N-1]))/N)/(1-(2/N)))= ((2(Sqrt[N-1]))/(N-2))   ( for N > 2) 
 
 or  W rotates a vector by the amount  θ = ArcTan (((2(Sqrt[N-1]))/(N-2)) ).  If N ≫1  θ≈ArcTan (2/(Sqrt[N]))≈ (2/(Sqrt[N]))
 To see W in action consider the following demo:

Demo of Grover's iteration

(* define basis vectors *)
ξ={1,0}; (* ξ points along vertical *)
η={0,1};(* η points along horizontal *)

ϕ[n_]= (1/(Sqrt[n])) ξ +(Sqrt[((n-1)/n)]) η;
G[n_]={{1-2/n,2 ((Sqrt[n-1])/n)},{-2  ((Sqrt[n-1])/n),1-2/n}};

pt0={0,0};
pt1[n_]={ϕ[n][[2]],ϕ[n][[1]]};

phi[n_]:=Graphics[{RGBColor[1,0,0],Arrow[{pt0,pt1[n]}]}];
ηaxis=Graphics[{RGBColor[0,0,1],Arrow[{pt0,{1,0}}]}];
ξaxis=Graphics[{RGBColor[0,0,1],Arrow[{pt0,{0,1}}]}];

Lets assume N=16  and we first plot the vector |ϕ⟩ below;

graph0=Show[ηaxis,ξaxis,phi[16],AspectRatio->1]

Now lets operate on |ϕ ⟩ with G, call this |(Subscript[ϕ, 1])⟩

ϕ1[n_]=G[n].ϕ[n];
(* change point of vector tail *)
pt1[n_]={ϕ1[n][[2]],ϕ1[n][[1]]};
graph1=Show[ηaxis,ξaxis,phi[16],AspectRatio->1]

Show[graph0,graph1]

ϕ2[n_]=G[n].G[n].ϕ[n];
(* change point of vector tail *)
pt1[n_]={ϕ2[n][[2]],ϕ2[n][[1]]};
graph2=Show[ηaxis,ξaxis,phi[16],AspectRatio->1]

Show[graph0,graph1,graph2]

ϕ3[n_]=G[n].G[n].G[n].ϕ[n];
(* change point of vector tail *)
pt1[n_]={ϕ3[n][[2]],ϕ3[n][[1]]};
graph3=Show[ηaxis,ξaxis,phi[16],AspectRatio->1]

ϕ4[n_]=G[n].G[n].G[n].G[n].ϕ[n];
(* change point of vector tail *)
pt1[n_]={ϕ4[n][[2]],ϕ4[n][[1]]};
graph4=Show[ηaxis,ξaxis,phi[16],AspectRatio->1]

Show[graph0,graph1,graph2,graph3,graph4,AspectRatio->1]

So the optimum choice to stop the Grover iteration is at the third iteration for then the vector |ϕ⟩ has rotated
almost into the |ξ ⟩ direction. If we make a measurement of the system we are most likely to get the value ξ,
our desired result. It took us 4 evaluations of the oracle function f(x) to get to the most likely result.
Compare this with the classical evaluation, on average, we need N/2 evaluations of f(x) to find ξ, since N=16
we need about 8 evaluations of f(x) to find ξ.

Hw 4 due 3/8

(1) Consider a 3 bit register |x ⟩_3   and consider the following function f: {0,1}^(⊗3) ⟶{0,1}

 ({{x, f(x)}, {000, 1}, {001, 1}, {010, 0}, {011, 1}, {100, 0}, {101, 0}, {110, 1}, {111, 1}})

Construct an operator (matrix gate) (Subscript[U, f]) that has the property

(Subscript[U, f])| x ⟩_3|y⟩ = | x ⟩_3|f(x) + y ⟩

where |y⟩ is the single target bit. 

(Hint: there are many different ways to get to the correct answer, one of them is: (a) figure out the  dimensionality of (Subscript[U, f])(Note: it operates on both |x ⟩_3, and |y ⟩).  Make a truth table labeling each incoming lead and outgoing lead i.e. (Subscript[U, f])|a⟩=|b⟩, where |a⟩ is the input state and |b⟩ the output. Then take the inner product ⟨c |(Subscript[U, f])|a⟩ = ⟨c|b⟩. The r.h.s. is a number and the l.h.s. is the matrix element of the c, a'th element of matrix (Subscript[U, f]) i.e.  (Subscript[(Subscript[U, f]), ca]) . Repeating this for all computational basis states you get the desired result.)

(2) We have the three-bit register |x(Subscript[ ⟩, 3]). Using Grover's algorithm we wish to identify the bit with the address 011.  So the oracle function f(011)=1, and vanishes for any other choice.

(a) First construct the superposition |ϕ ⟩ ≡ (H^(⊗3))|0⟩_3. We make a measurement of that state, what is the probablity that our oracle will identify the correct target?

(b) Find the matrix representation of  V, so that V|x ⟩ = (-1)^(f(x)) |x ⟩. 


(c) Construct (matrix representation)  W = 2|ϕ ⟩⟨ϕ| -  1    where |ϕ ⟩ was defined in part (a)


(d) Construct (matrix representation) the Grovers operator G = W V.


(e) Now start our computation again as in part (a), but after the state |0⟩_3 goes through the Hadamard gates
send it into the G gate. Evaluate the output and find the probablitity that a measurement results in the value
011 ?

(f) Let's do this again. Start with  |0⟩_3, pass it through (H^(⊗3)) then let that output go through G twice.
Evaluate the output and find the probablitity that the measurement results in the value 001 ?  Does this lead to a better chance of finding the correct answer. Can you figure out the number consecutive G gates you need in order to get the optimum answer?  If your answer is in the affirmative calculate the probability that you find 011, in the optimum setup .