%% Brief descrption of the work.

%The following code explain by steps every detail of design.
%The code is trying to solve graph coloring problem using quantum computer
%gates and circuits.
%We going to use grover algorithm to explore all possible solution states 

%% Step1:The definition of gates and circuits used in the design

%Input state one
One=[0;1];
%Input state zero
Zero=[1;0];
%Wire circuit
W=eye(2,2);
%Inverter gate
I=[0 1;1 0];
%Hadamard gate
Hd=[0.7071 0.7071;0.7071 -0.7071];
%Feyman gate
Fn=[1 0 0 0;0 1 0 0;0 0 0 1;0 0 1 0];
%Swap gate
Sp=[1 0 0 0;0 0 1 0;0 1 0 0;0 0 0 1];
%2-input Toffoli gate
%Note Toffoli gate is an identity matrix with last two rows been exchanged
T2=[1 0 0 0 0 0 0 0;0 1 0 0 0 0 0 0;
    0 0 1 0 0 0 0 0;0 0 0 1 0 0 0 0;
    0 0 0 0 1 0 0 0;0 0 0 0 0 1 0 0;
    0 0 0 0 0 0 0 1;0 0 0 0 0 0 1 0];
%3-input Toffoli gate
temp=eye(16,16);%creating Identity matrix
x=temp(15,:);%Saving line(15) of the matrix
temp(15,:)=temp(16,:);%Exchanging line(15) with line(16)
temp(16,:)=x;%Exchange line(16) with line(15)
T3=temp;%The result Toffoli gate of 3-input

%% Step2:Constructing the input vector(In)

%Here we are going to construct the input vector which appear as the first
%block of the design in Fig1. This vector is constructed by taking the
%kronecker multiplication of all inputs and working bits. Where inputs
%taking values of zero from the definition of Grover and the working bits
%taking the values of 1,1,1,0 respectivly which related to our oracle
%design.

In=kron(kron(kron(kron(kron(kron(kron(kron(kron(Zero,Zero),Zero),Zero),Zero),Zero),One),One),One),Zero);

%% Step3:Constructing the Hadamarad vector(H)

%Here we are going to construct the second block in Fig1. We are going
%to you the illistration described in Fig5. This vector is constructed by
%taking kronecker multiplication of Hadamarad gates of input wires and 
%normal wire circuits for working bits.

H=kron(kron(kron(kron(kron(kron(kron(kron(kron(Hd,Hd),Hd),Hd),Hd),Hd),W),W),W),W);

%% Step4: Oracle design(O)

%Here we are going to construct the oracle circuit which shown in Fig6 and
%Fig7. We divide the oracle into 4 stages and each stage into a number of
%units to make it more easier to construct. We will going to design each
%stage separately then we are going to construct the oracle O be taking the
%matrix multiplication of stages in reverse order. Where O=S4*S3*S2*S1

%Stage1:
%S1 is constructed by taking the matrix multiplication for its units. 
%Units are constucted by taking the kronecker multiplication for the 
%gates and circuits of each unit.
U1=kron(kron(kron(kron(kron(kron(kron(W,Sp),W),W),Sp),W),W),W);
U2=kron(kron(kron(kron(kron(kron(kron(Fn,Fn),W),W),W),W),W),W);
U3=kron(kron(kron(kron(kron(kron(kron(kron(kron(W,I),W),I),W),W),W),W),W),W);
U4=kron(kron(kron(kron(kron(kron(kron(W,Sp),W),Sp),W),W),W),W);
U5=kron(kron(kron(kron(kron(kron(kron(W,W),T2),W),W),W),W),W);
U6=U4;U7=U3;U8=U2;U9=U1;

S1=U9*U8*U7*U6*U5*U4*U3*U2*U1;% Stage1 of the oracle.

%Stage2:
%S2 is constructed by taking the matrix multiplication for its units. 
%Units are constucted by taking the kronecker multiplication for the 
%gates and circuits of each unit.
U1=kron(kron(kron(kron(kron(kron(W,Sp),Sp),W),Sp),W),W);
U2=kron(kron(kron(kron(kron(kron(Sp,Sp),Sp),W),W),W),W);
U3=kron(kron(kron(kron(kron(kron(kron(W,Fn),Fn),W),W),W),W),W);
U4=kron(kron(kron(kron(kron(kron(kron(kron(kron(W,W),I),W),I),W),W),W),W),W);
U5=kron(kron(kron(kron(kron(kron(kron(W,W),Sp),W),Sp),W),W),W);
U6=kron(kron(kron(kron(kron(kron(kron(W,W),W),T2),W),W),W),W);
U7=U5;U8=U4;U9=U3;U10=U2;U11=U1;

S2=U11*U10*U9*U8*U7*U6*U5*U4*U3*U2*U1;% Stage2 of the oracle.

%Stage3:
%S3 is constructed by taking the matrix multiplication for its units. 
%Units are constucted by taking the kronecker multiplication for the 
%gates and circuits of each unit.
U1=kron(kron(kron(kron(kron(kron(kron(W,W),W),Sp),W),W),Sp),W);
U2=kron(kron(kron(kron(kron(kron(kron(W,W),Fn),Fn),W),W),W),W);
U3=kron(kron(kron(kron(kron(kron(kron(kron(kron(W,W),W),I),W),I),W),W),W),W);
U4=kron(kron(kron(kron(kron(kron(kron(W,W),W),Sp),W),Sp),W),W);
U5=kron(kron(kron(kron(kron(kron(kron(W,W),W),W),T2),W),W),W);
U6=U4;U7=U3;U8=U2;U9=U1;

S3=U9*U8*U7*U6*U5*U4*U3*U2*U1;% Stage3 of the oracle.

%Stage4:
%S4 is constructed by taking kronecker multiplication for the 
%gates and circuits of each unit.
S4=kron(kron(kron(kron(kron(kron(W,W),W),W),W),W),T3);

%The oracle:
O=S4*S3*S2*S1;

%% Step5:Grover block(G)

%Here we are going to construct the grover algorith block which we denote
%it by G. G is the result of the following formula G=HZHO. Till this step
%we create both H & O. So we have to define Z which is the Zero State Phase
%Shift. Z is an identity matrix of size m*m where m=2^k, and k= number of
%inputs(n)+ number of working bits. In our case of 3-node graph colorng
%m=2^10 which equal to m=1024.

%Constructing Z
m=1024;
temp2=eye(m,m);
temp2(1,1)=-1;
Z=temp2;

%Constructing G
G=H*Z*H*O; %Grover algorithm block

%% Step6: Evaluation of the Grover algorith

%We discussed in the report that we need to repeat Grover block N times so
%we can see that all possible solutions start taking high probability
%values close to one and all bad solutions start taking low probability
%valuse close to zero. where N=8, this was calculated using the following formula
%N=Sqrt(2^n) where n is number of inputs in our case 6 bits.

%Constructing for loop to calculate the output of the algorithm
Out=H*In;%We initialize Out with the matrix multiplication of H and In.
NoG=1;%Number of Grover blocks will be apllied in the algorithm
for i=1:NoG
    Out=G*Out;%Loop for constructing the whole design
end

Out%Print Out

%Visualizing results
bar(Out);
title('Results of applying Grover block 3times');
xlabel('Matrix Index');
ylabel('Values');