Deutsch Gate

In the previous notebook we considered the four possible functions for the mapping f:{0,1}  ⟶ {0,1}

(Subscript[f, 0]):0 ⟶0         (Subscript[f, 1]):0 ⟶0        (Subscript[f, 2]):0 ⟶1       (Subscript[f, 3]):0 ⟶1
(Subscript[f, 0]):1 ⟶0         (Subscript[f, 1]):1 ⟶1        (Subscript[f, 2]):1 ⟶0       (Subscript[f, 3]):1 ⟶1


We would like to construct the operator

(Subscript[U, f])|x ⟩ |y ⟩ ⟶ |x ⟩ |y ⊕ f(x) ⟩

for all the operators (Subscript[f, i]) tabulated above.  The answers are (can you see why?)

(Subscript[U, (Subscript[f, 0])]) = 1⊗1

(Subscript[U, (Subscript[f, 1])]) = (Subscript[C, 01])

(Subscript[U, (Subscript[f, 2])])= (Subscript[C, 10]) (1⊗(Subscript[X, 0]))

(Subscript[U, (Subscript[f, 3])])= 1⊗(Subscript[X, 0])

Let's explicitly evaluate these operators in the matrix representation.

one={0,1};
zero={1,0};
unit={{1,0},{0,1}};
XPauli={{0,1},{1,0}};
C01={{1,0,0,0},{0,1,0,0},{0,0,0,1},{0,0,1,0}};

Uf0=KroneckerProduct[unit,unit];
MatrixForm[Uf0]
Uf1=C01;
MatrixForm[Uf1]
Uf2=C01.KroneckerProduct[unit,XPauli];
MatrixForm[Uf2]
Uf3=KroneckerProduct[unit,XPauli];
MatrixForm[Uf3]

(* lets construct our computational basis *)
ket00=Flatten[KroneckerProduct[zero,zero]]
ket01=Flatten[KroneckerProduct[zero,one]]
ket10=Flatten[KroneckerProduct[one,zero]]
ket11=Flatten[KroneckerProduct[one,one]]

Consider the table for function (Subscript[f, 0])


({{State, |x ⟩|y⊕f(x)⟩, |x ⟩|y⊕f(x)⟩}, {|0⟩|0⟩, |0⟩|f(0)⟩, |0⟩|0 ⟩}, {|0⟩|1⟩, |0⟩|1⊕f(1)⟩, |0⟩|1⟩}, {|1⟩|0⟩, |1⟩|f(1)⟩, |1⟩|0⟩}, {|1⟩|1⟩, |1⟩|1⊕f(1)⟩, |1⟩|1⟩}})

(* lets check with our matrix operator *)

Uf0.ket00==ket00
Uf0.ket01==ket01
Uf0.ket10==ket10
Uf0.ket11==ket11

Consider the table for function (Subscript[f, 1])


({{State, |x ⟩|y⊕f(x)⟩, |x ⟩|y⊕f(x)⟩}, {|0⟩|0⟩, |0⟩|f(0)⟩, |0⟩|0 ⟩}, {|0⟩|1⟩, |0⟩|1⊕f(0)⟩, |0⟩|1⟩}, {|1⟩|0⟩, |1⟩|f(1)⟩, |1⟩|1⟩}, {|1⟩|1⟩, |1⟩|1⊕f(1)⟩, |1⟩|0⟩}})

Uf1.ket00==ket00
Uf1.ket01==ket01
Uf1.ket10==ket11
Uf1.ket11==ket10

Consider the table for function (Subscript[f, 2])


({{State, |x ⟩|y⊕f(x)⟩, |x ⟩|y⊕f(x)⟩}, {|0⟩|0⟩, |0⟩|f(0)⟩, |0⟩|1 ⟩}, {|0⟩|1⟩, |0⟩|1⊕f(0)⟩, |0⟩|0⟩}, {|1⟩|0⟩, |1⟩|f(1)⟩, |1⟩|0⟩}, {|1⟩|1⟩, |1⟩|1⊕f(1)⟩, |1⟩|1⟩}})

Uf2.ket00==ket01
Uf2.ket01==ket00
Uf2.ket10==ket10
Uf2.ket11==ket11

Consider the table for function (Subscript[f, 3])


({{State, |x ⟩|y⊕f(x)⟩, |x ⟩|y⊕f(x)⟩}, {|0⟩|0⟩, |0⟩|f(0)⟩, |0⟩|1 ⟩}, {|0⟩|1⟩, |0⟩|1⊕f(0)⟩, |0⟩|0⟩}, {|1⟩|0⟩, |1⟩|f(1)⟩, |1⟩|1⟩}, {|1⟩|1⟩, |1⟩|1⊕f(1)⟩, |1⟩|0⟩}})

Uf3.ket00==ket01
Uf3.ket01==ket00
Uf3.ket10==ket11
Uf3.ket11==ket10

Deutsch' problem

Given the following circuit

Suppose someone built the above circuit for a given function f (on one of the four described above)
but we don't know which one it is. We can feed in bits on the left and see what comes out on the
right, we can then figure out which of the above functions are hard wired into the black box.
How many computations do you require to correctly guess f ?

for example we feed in 00 and 01 comes out is that sufficient to figure
out which of these   (Subscript[f, 0]),(Subscript[f, 1,])(Subscript[f, 2]),(Subscript[f, 3])  is hard wired in the processor ?
It could either be (Subscript[f, 2]),or (Subscript[f, 3]). How do we choose between those two?

 
Deutsch suggested we take the black box (Subscript[U, f]) given above and add to it
the following so that it looks like.

Let’s assume that the input state on the left is the 2-Qubit |0⟩|0⟩=|00⟩

Passing through the first stage (first dashed line on left): we get the following output

X ⊗ X |00⟩ = |11⟩

where we used the fact that  X|0⟩=|1⟩, X|1⟩=|0⟩



Now passing through the pair of Hadamard gates

H ⊗  H |11⟩ = (1/2)( |0⟩-|1⟩) ( |0⟩-|1⟩) = (1/2)( |00⟩ - |10⟩- |01⟩ + |11⟩)

Going through the (Subscript[U, f]) gate

(1/2)( (Subscript[U, f])|00⟩ - (Subscript[U, f])|10⟩ - (Subscript[U, f]) |01⟩ + (Subscript[U, f])|11⟩) = (1/2)( |0⟩|f(0)⟩ -|1⟩|f(1)⟩-|0⟩|f(0) + 1⟩+|1⟩|f(1)+1⟩)

Finally the upper lead goes through another Hadamard gate

So we get as output

 (1/2) (H |0⟩|f(0)⟩ -H |1⟩|f(1)⟩-H |0⟩|f(0) + 1⟩+H |1⟩|f(1)+1⟩)=
 
 
 (1/2)  (1/(Sqrt[2]))( |0⟩+|1⟩) |f(0)⟩ -  (1/2) (1/(Sqrt[2]))( |0⟩-|1⟩) |f(1)⟩ - (1/2)(1/(Sqrt[2]))( |0⟩+|1⟩) |f(0)+1⟩ + (1/2)(1/(Sqrt[2]))( |0⟩-|1⟩)|f(1)+1⟩ 
 
 = (1/2) (1/(Sqrt[2]))|0⟩(   |f(0)⟩ - |f(1)⟩ - |f(0)+1⟩+ |f(1)+1⟩ ) 
 
 + (1/2)|1⟩(1/(Sqrt[2])) (  |f(0)⟩ + |f(1)⟩  - |f(0)+1⟩ - |f(1)+1⟩ )

Let's take a measurement of the top lead.

What are possible results?

Suppose f(0) = f(1) then
above result gives

  |1⟩(1/(Sqrt[2]))  |f(0)-|f(0)+1⟩) = |1⟩ |Φ⟩  so, according to the generalized Born rule, we get the value 100% of the time.
  
 
  if  f(0) ≠ f(1)
  
  then |f(0)⟩ = |f(1)+1⟩ and |f(1)⟩=|f(0)+1⟩ and so
  
  we get
  
  (1/(Sqrt[2]))|0⟩( |f(1)+1⟩ - |f(0)+1⟩ )  = |0⟩ |ψ⟩  and we get 0 100 % of the time.

Therefore,  after going through the Deutsch gate only once, we will know, with certainty, wether

f(0)=f(1)

or

f(0) ≠ f(1)