(* construct 2-qubit basis vectors *)
ket00={1,0,0,0};
ket01={0,1,0,0};
ket10={0,0,1,0};
ket11={0,0,0,1};

Deutsch's Algorithm

Deutsch’s algorithm addresses questions concerning  the properties of functions that map a single bit into a single bit, i.e. f:{0,1} →{0,1}. A little thought informs us that only four distinct functions exist, which we label (Subscript[f, 0,])(Subscript[f, 1,])(Subscript[f, 2]),(Subscript[f, 3]). Their truth tables are

(({{x, (Subscript[f, 0])(x)}, {0, 0}, {1, 0}}))     (({{x, (Subscript[f, 1])(x)}, {0, 0}, {1, 1}}))    (({{x, (Subscript[f, 2])(x)}, {0, 1}, {1, 0}}))     (({{x, (Subscript[f, 3])(x)}, {0, 1}, {1, 1}}))    

Deutsch’s problem asks: Given a black box that evaluates one of these functions, how many computations are required to infer whether the black box is a balanced or constant function. A balanced function is one that contains an equal number of 0’s and 1’s in its output. Thus (Subscript[f, 1,])(Subscript[f, 2])are balanced. A constant function outputs either all 0’s or all 1’s. Obviously (Subscript[f, 0,])(Subscript[f, 3])are balanced.

Convince yourself that a classical algorithm requires at least two computations to answer Deutsch’s question.
We now investigate how a quantum algorithm can return an answer with only a single quantum computation.

The wire diagram for this algorithm is given in Fig. 3.9 of the text

We start from the left-most side of the diagram with the input value

ket0={1,0};
ket1={0,1};
psiin=Flatten[KroneckerProduct[ket0,ket1]]

This state passes through a tensor product of two Hadamard gates.

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

and the output after (Subscript[t, 1]) is

psiatt1=KroneckerProduct[Had,Had].psiin;
MatrixForm[psiatt1]

Note that this state is a linear combination of all 2-qubit states |00⟩, |01⟩, |10⟩, |11⟩. This feature, generated by the two Hadamard gates, is called quantum parallelism. This state is now input into (Subscript[U, f]), which we must construct. Following the procedure used to generate Table 3.8 in the text, we appeal to protocol (3.18)
(Subscript[U, f])|x ⟩ |y ⟩ ⟶ |x ⟩ |y ⊕ f(x) ⟩

From these relations we can construct the matrix elements of operator (Subscript[U, f]). The first column of this 4×4 matrix is given by the entries

Exercise:

(a) Find the matrix entries for the remaining three columns of (Subscript[U, f]) and show that its matrix representation is given by

Uf={{"⟨0|f(0)⟩","⟨0|f(0)⊕ 1)⟩",0,0},{"⟨1|f(0)⟩","⟨1|f(0)⊕1⟩",0,0},{0,0,"⟨0|f(1)⟩","⟨0|f(1)⊕ 1⟩"},{0,0,"⟨1|f(1)⟩","⟨1|f(1)⊕1⟩"}};
MatrixForm[Uf]

(b) Demonstrate that this matrix operator is unitary.

With the matrix expression for (Subscript[U, f]) we  evaluate the 2-qubit amplitude at time  (Subscript[t, 2])

psiatt2=Uf.psiatt1;
MatrixForm[psiatt2]

Finally the system passes through a single Hadamard gate in the upper wire, whose matrix representation is

unit={{1,0},{0,1}};
Hadgate2=KroneckerProduct[Had,unit];
MatrixForm[%]

After passing through this gate, the 2-qubit amplitude becomes

psiatt3=Hadgate2.psiatt2;
MatrixForm[psiatt3]

Measurement

State |psiatt3⟩ represents the amplitude at the measurement device show above. The measurement device M represent a Hermitian operator given by M =|1⟩⟨1| ⊗ (|1⟩⟨1 | + |0 ⟩⟨0| ) , or in matrix form

M=KroneckerProduct[KroneckerProduct[ket1,ket1],unit];
MatrixForm[M]

According to the Born rule, a measurement with device M leads to measurement of its eigenvalues, which have the values 0,1. If M reads 0,the system collapses to the eigenstates corresponding to that eigenvalue. Inspecting matrix M, we note that those eigenstates correspond to the eigenvectors

|00⟩  =  (({{1}, {0}, {0}, {0}}))  |01⟩ = (({{0}, {1}, {0}, {0}}))

as can be seen from the identities

zerozero={1,0,0,0};
zerone={0,1,0,0};

M.zerozero==0 zerozero

M.zerone==0 zerone

Therefore, according to the Born rule,  the probability to obtain eigenvalue 0, following a measurement with M is
({{|({{⟨00 | ψ⟩}})((|)^2)+|({{⟨10|ψ⟩}})((|)^2)
}})
where |ψ ⟩ is the amplitude |psiatt3⟩.  Thus the probability is give by

prob=FullSimplify[Expand[(ket00.psiatt3)^2 + (ket01.psiatt3)^2]]

If f(0)=f(1) the two terms in this expression reduce to

(1/2) (((⟨0|f(0)⟩-⟨0|f(0)⊕ 1⟩))^2)+ (1/2) ((( ⟨1|f(0)⟩-⟨1|f(0)⊕1⟩ ))^2),

and regardless of the value for f(0), evaluates to unity.

So when the measuring device registers a zero value, the function is constant.

Exercise:

Demonstrate that if  the function is balanced the measurement meter displays the value 1, with 100% certainty.

Simulation of Deutsch’s algorithm.

Start simulation here

(* Define a random function f *)
f[0]:=Module[{x},x=RandomInteger[];{x,1-x}];
f[1]:=Module[{x},x=RandomInteger[];{x,1-x}];
ketf0=f[0];
ketf1=f[1];
(* construct the blackbox *)
Ublackbox={{ket0.ketf0,ket0.Mod[ketf0+1,2],0,0},{ket1.ketf0,ket1.Mod[ketf0+1,2],0,0},
{0,0,ket0.ketf1,ket0.Mod[ketf1+1,2]},{0,0,ket1.ketf1,ket1.Mod[ketf1+1,2]}};
(* initial state *)
psiin=ket01;
(* Implement the Deutsch circuit diagram *)
finalstate=Hadgate2.Ublackbox.KroneckerProduct[Had,Had].psiin;
(* Measure top wire *)
probablitytomeasure0=(ket00.finalstate)^2+(ket01.finalstate)^2;
probablitytomeasure1=(ket10.finalstate)^2+(ket11.finalstate)^2;
If[probablitytomeasure0==1,Print[" Constant Function "],Print[" Balanced Function "]]

Check your answer by looking inside the black box

MatrixForm[{{"x","f(x)"},{0,If[ketf0[[1]]==1,0,1]},{1,If[ketf1[[1]]==1,0,1]}}]