Hw 4 due 2/27

(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.)

Because we have a direct product of a 3-bit state and a single bit state i.e. | x ⟩_3|y⟩ we have a 4 bit register
and so there are, altogether, (2^4)=16 computational basis states. We label them in the usual way

|0⟩_4  = |0000⟩ = | 000 ⟩_3|0⟩ 
|1⟩_4  = |0001⟩=  | 000 ⟩_3|1⟩
|2⟩_4  = |0010⟩=  | 001 ⟩_3|0⟩
|3⟩_4  = |0011⟩=  | 001 ⟩_3|1⟩
|4⟩_4  = |0100⟩=  | 010 ⟩_3|0⟩
|5⟩_4  = |0101⟩=  | 010 ⟩_3|1⟩.
|6⟩_4  = |0110⟩=  | 011 ⟩_3|0⟩.
|7⟩_4  = |0111⟩=  | 011 ⟩_3|1⟩.
|8⟩_4  = |1000⟩=  | 100 ⟩_3|0⟩
|9⟩_4  = |1001⟩=  | 100 ⟩_3|1⟩
|10⟩_4  = |1010⟩=  | 101 ⟩_3|0⟩
|11⟩_4  = |1011⟩=  | 101 ⟩_3|1⟩
|12⟩_4  = |1100⟩= | 110 ⟩_3|0⟩
|13⟩_4  = |1101⟩=  | 110 ⟩_3|1⟩
|14⟩_4  = |1110⟩=  | 111⟩_3|0⟩
|15⟩_4  = |1111⟩=  | 111 ⟩_3|1⟩


and so

(Subscript[U, f])|0(Subscript[ ⟩, 4])=   | 000 ⟩_3 |f(000)+0⟩ =  | 000 ⟩_3|1⟩ = |1⟩_4
(Subscript[U, f])|1(Subscript[ ⟩, 4]) =  | 000 ⟩_3 |f(000)+1⟩=   | 000 ⟩_3|0⟩ = |0⟩_4
(Subscript[U, f]) |2(Subscript[ ⟩, 4])  =  | 001 ⟩_3 |f(001)+0⟩ =  | 001 ⟩_3|1⟩ = |3⟩_4
(Subscript[U, f]) |3⟩_4  =   | 001 ⟩_3 |f(001)+1⟩ =  | 001 ⟩_3|0⟩ = |2⟩_4
(Subscript[U, f]) |4⟩_4  =   | 010 ⟩_3 |f(010)+ 0⟩=  | 010 ⟩_3|0⟩ = |4⟩_4
(Subscript[U, f]) |5⟩_4  =   | 010 ⟩_3 |f(010)+1⟩ =  | 010 ⟩_3|1⟩ = |5⟩_4
(Subscript[U, f]) |6⟩_4  =   | 011 ⟩_3 |f(011)+0⟩=   | 011 ⟩_3|1⟩=  |7⟩_4
(Subscript[U, f]) |7⟩_4  =   | 011 ⟩_3 |f(011)+1⟩=   | 011 ⟩_3|0⟩=  |6⟩_4
(Subscript[U, f]) |8⟩_4  =   | 100 ⟩_3 |f(100)+0⟩=   | 100 ⟩_3|0⟩ = |8⟩_4
(Subscript[U, f]) |9⟩_4  =   | 100 ⟩_3 |f(100)+1⟩=   | 100 ⟩_3|1⟩ = |9⟩_4
(Subscript[U, f]) |10⟩_4  = | 101 ⟩_3 |f(101)+0⟩=   | 101 ⟩_3|0⟩ = |10⟩_4
(Subscript[U, f]) |11⟩_4  = | 101 ⟩_3 |f(101)+1⟩=   | 101 ⟩_3|1⟩ = |1(Subscript[1⟩, 4])
(Subscript[U, f]) |12⟩_4  = | 110 ⟩_3 |f(110)+0⟩=   | 110 ⟩_3|1⟩ = |13⟩_4
(Subscript[U, f]) |13⟩_4  = | 110 ⟩_3 |f(110)+1⟩=   | 110 ⟩_3|0⟩ =|1(Subscript[2⟩, 4])
(Subscript[U, f]) |14⟩_4  = | 111⟩_3 |f(111)+0⟩ =  | 111⟩_3| 1⟩ = |15⟩_4
(Subscript[U, f])| 15⟩_4  = | 111 ⟩_3|f(111)+1⟩=  | 111⟩_3| 0⟩ = |1(Subscript[4⟩, 4])

So taking the inner product we can get the required matrix elements.

Another way of obtaining the matrix is by expressing (Subscript[U, f]) in terms of Dirac operators

i.e. 

(Subscript[U, f]) = | 1 ⟩ ⟨ 0 | +  | 0 ⟩ ⟨ 1 | +  | 3 ⟩ ⟨ 2 | +   | 2 ⟩ ⟨ 3 | 
    +  | 4 ⟩ ⟨ 4 | +  | 5 ⟩ ⟨ 5 | +  | 7 ⟩ ⟨ 6 | +   | 6 ⟩ ⟨ 7 |
    +  | 8 ⟩ ⟨ 8 | +   | 9 ⟩ ⟨ 9 | +  | 10⟩ ⟨1 0 | +  | 11⟩ ⟨ 11 | 
    +  | 12 ⟩ ⟨ 13 | +  | 13 ⟩ ⟨ 12 | +  | 14 ⟩ ⟨ 15 | +  | 15 ⟩ ⟨ 14 |

(* defining our kets and bra's the usual way *)

ket[i_]=Table[KroneckerDelta[j,i+1],{j,1,16}];

(* for example *)
MatrixForm[ket[0]]

(* So the operator can then be written *)

Uf=(KroneckerProduct[ket[1],ket[0]]+KroneckerProduct[ket[0],ket[1]]+KroneckerProduct[ket[3],ket[2]] + KroneckerProduct[ket[2],ket[3]]+ KroneckerProduct[ket[4],ket[4]] + KroneckerProduct[ket[5],ket[5]]+ KroneckerProduct[ket[7],ket[6]]+ KroneckerProduct[ket[6],ket[7]]+
KroneckerProduct[ket[8],ket[8]]+KroneckerProduct[ket[9],ket[9]] +
KroneckerProduct[ket[10],ket[10]]+KroneckerProduct[ket[11],ket[11]]+
KroneckerProduct[ket[12],ket[13]]+KroneckerProduct[ket[13],ket[12]]+
KroneckerProduct[ket[14],ket[15]]+KroneckerProduct[ket[15],ket[14]]);
MatrixForm[Uf]

(* check if this is unitary *)
Ufdagger=Transpose[Uf];
MatrixForm[Ufdagger.Uf]

(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?

We know that

(H^(⊗3))|0⟩_3 =  (1/(Sqrt[8]))  ( |0⟩_(3 )+ |1⟩_(3 )+... + |7⟩_(3 ))

taking a measurement of the computational basis  each has equal amplitude   (1/(Sqrt[8])) , and
so the probablity of obtaining the correct value is 1/8.


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

Since f(x)=1 if x=011=3 and zero otherwise we get

V=DiagonalMatrix[{1,1,1,-1,1,1,1,1}];
MatrixForm[V]

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

phistate=1/Sqrt[8]{1,1,1,1,1,1,1,1};
unitmatrix=IdentityMatrix[8];
W= 2 KroneckerProduct[phistate,phistate]-unitmatrix;
MatrixForm[W]

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

G = W.V;
MatrixForm[G]

(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 ?

MatrixForm[N[G.phistate]]

So the probability of obtaining the correct value is   (0.883883^2) = 0.78 about 78% of the time a measurement
will yield the correct answer.

(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 .

MatrixForm[N[G.G.phistate]]

So the probability of obtaining the correct value is   (0.972^2) = 0.945  about 95% of the time a measurement
will yield the correct answer.