Quantum Fourier Transform II

The Quantum Fourier Transform (QFT) is a key ingredient in Shor's algorithm. Remember that we defined it as a linear combination of computational basis states for an n-Qbit register.


Suppose we have an n-bit register, which can hold N=(2^n) states, which we label in the usual manner
|0 ⟩_n  |1 ⟩_n  |3 ⟩_n   ...          |(2^n)-1⟩_n . Let’s define a linear superposition of these states

|(Subscript[ψ, m])⟩ = (1/(Sqrt[N])) (Underoverscript[ ∑, (k=0), (k=N-1)]) (e^( i  2π  ((m  k )/N))) |k⟩_n     

or

(Subscript[U, FT])|m ⟩_n = |(Subscript[ψ, m])⟩ = (1/(Sqrt[N])) (Underoverscript[ ∑, (k=0), (k=N-1)]) (e^( i  2π  ((m  k )/N))) |k⟩_n 

We also learned that the q m th' matrix element of  (Subscript[U, FT]) is given by 

⟨q | (Subscript[U, FT])| m ⟩ =  (1/(Sqrt[N]))  (e^( i  2π  ((m  q )/N)))   

and so it is easy to construct a matrix representation for  (Subscript[U, FT]), the Quantum Fourier Transform gate.

U[Num_]:=1/Sqrt[Num] Table[Exp[2I i j Pi/Num],{i,0,Num-1},{j,0,Num-1}];

MatrixForm[U[2]]

Udag=Conjugate[Transpose[U[2]]];
MatrixForm[Udag]

FullSimplify[Udag.U[2]];
MatrixForm[%]

For large n this procedure gets cumbersome as we need to construct a n x n gate. Remember how classical gates, such as the n-bit adder can be built up from modular units of smaller gates. Can we do the same for the QFT gate? i.e. find a way to modularize it, this would be of great practically utility since we know how to build small 2 - Qubit gates and by connecting them together, like Lego blocks, we can construct the large n x n QFT gate. This is the question we are going to study below.

On some properties of QFT

Lets look at some specific cases, (Subscript[U, FT]) in detail. Suppose n=1 (N=2) ( a single  Qubit QFT)

we find  (using  the definition (Subscript[U, FT])|m ⟩_n = (1/(Sqrt[N])) (Underoverscript[ ∑, (k=0), (k=N-1)]) (e^( i  2π  ((m  k )/N))) |k⟩_n  )

(Subscript[U, FT])|0⟩ =  (1/(Sqrt[2])) (Underoverscript[ ∑, (k=0), (k=1)]) (e^( i  2π  ((0  k )/2))) |k⟩_n = (1/(Sqrt[2]))( |0⟩ + |1⟩ )
(Subscript[U, FT])|1⟩ =  (1/(Sqrt[2])) (Underoverscript[ ∑, (k=0), (k=1)]) (e^( i  2π  ((1 k )/2))) |k⟩_n = (1/(Sqrt[2]))( |0⟩ - |1⟩ )

which, as we remarked above, is also the Hadamard gate. Suppose now that n=2 (N=4) the computational basis are
|0⟩_2=|00⟩,  |1⟩_2=|01⟩, |2⟩_2=|10⟩,  |3⟩_2=|11⟩

and

(Subscript[U, FT]) |00⟩_2 =  (1/(Sqrt[4])) (Underoverscript[ ∑, (k=0), (k=N-1)]) (e^( i  2π  ((0  k )/4))) |k⟩_n = |0⟩_2+ |1⟩_2 +  |2⟩_2 + |3⟩_2  = (1/2) ( |00⟩ + |01⟩ + |10⟩ +|11⟩ ) =
                                                                                                   (1/2) ( |0⟩ + |1⟩) ⊗  (|0⟩ + |1⟩)

(Subscript[U, FT]) |01⟩_2 =  (1/(Sqrt[4])) (Underoverscript[ ∑, (k=0), (k=N-1)]) (e^( i  2π  ((1  k )/4))) |k⟩_n = |0⟩_2 + i  |1⟩_2 -  |2⟩_2 - i |3⟩_2  = (1/2) ( |00⟩ + i  |01⟩ -  |10⟩ -i  |11⟩) =
                                                                                                    ( |0⟩ -  |1⟩ ) ⊗  ( |0⟩ + i  |1⟩ )

Exp[2Pi I k/4] /. k->0

(Subscript[U, FT]) |10⟩_2 =  (1/(Sqrt[4])) (Underoverscript[ ∑, (k=0), (k=N-1)]) (e^( i  2π  ((2  k )/4))) |k⟩_n = |0⟩_2 - |1⟩_2 +  |2⟩_2 -  |3⟩_2  = (1/2)( |00⟩ -  |01⟩ +  |10⟩  -   |11⟩ )=
                                                                                                   (1/2)  ( |0⟩ +  |1⟩ ) ⊗  ( |0⟩ -  |1⟩ )

(Subscript[U, FT]) |11⟩_2 =  (1/(Sqrt[4])) (Underoverscript[ ∑, (k=0), (k=N-1)]) (e^( i  2π  ((3  k )/4))) |k⟩_n = |0⟩_2 - i |1⟩_2 -  |2⟩_2 + i  |3⟩_2  = (1/2)( |00⟩ - i  |01⟩ -  |10⟩ + i  |11⟩) =
                                                                                                    (1/2) ( |0⟩ -  |1⟩ ) ⊗  ( |0⟩ - i  |1⟩ )

For these two cases we note that the QFT transform breaks up into pieces that involve products of single Qbit states. Is this true
for any n-Qbit QFT ? The answer is yes, first validate this rule by trying evaluating, as above, the 3-Qbit QFT (See Class Project below).

In general it turns out that

(Subscript[U, FT])| (Subscript[b, n-1]) (Subscript[b, n-2]) ... (Subscript[b, 1])(Subscript[b, 0])⟩ =   (1/(2^(n/2))) ( | 0 ⟩ + (e^( i  2π  [.(Subscript[b, 0])])) |1 ⟩)  ( | 0 ⟩ + (e^( i  2π  [.(Subscript[b, 1])(Subscript[b, 0])])) |1 ⟩)  ...  ( | 0 ⟩ + (e^( i  2π  [.(Subscript[b, n-1 ])(Subscript[b, n-2])...(Subscript[b, 1])(Subscript[b, 0])])) |1 ⟩) .

where the (Subscript[b, n]) are the bit entries (0,1) in our register and the symbol

[. (Subscript[b, 0])] ≡ (Subscript[b, 0]) × (2^(-1))

[. (Subscript[b, 0])(Subscript[b, 1])] ≡ (Subscript[b, 0]) × (2^(-1))+ (Subscript[b, 1]) × (2^(-2))

etc.

The importance of this result should be obvious. According to it, (Subscript[U, FT]) can simply be expressed as direct product of  various linear 
combinations of the single Qbits |0⟩,|1⟩. These linear combinations could be generated by a single bit gate (a 2 dimensional matrix).
However these gates must be connected somehow, for example lets look at the pair

  (1/(2^(n/2))) ( | 0 ⟩ + (e^( i  2π  [.(Subscript[b, 0])])) |1 ⟩)  ( | 0 ⟩ + (e^( i  2π  [.(Subscript[b, 1])(Subscript[b, 0])])) |1 ⟩)  
  
  note that the one bit gate acting on the second Qbit depends on the value  (Subscript[b, 0]), so  this really describes a 2-Qbit gate.

Diagrammatics

It's now a good time to review how we describe quantum gates diagrammatically. Consider the Hadamard gate, a one Qbit gate, which
we represent diagrammatically as

The gate is represented by the box and the single lead wire on the left represents the incoming state. The outgoing state
is represented by the lead wire on the right of the box (gate). The Hadamard gate is a single Qbit gate since there is only
one lead entering or leaving the box.

We also learned about the Controlled - Not gate  CNOT. It is a two-Qubit gate and  it's truth table looked like this

CNOT |00⟩ = |00⟩
CNOT |01⟩ = |01⟩
CNOT |10⟩ = |11⟩
CNOT |11⟩ = |10⟩

we can represent this by the following diagram

For an incoming state | a b c ⟩   the  lead wires would look like 






For the CNOT gate
The top lead represents the control bit and the bottom lead represents target bit, which passes through a Pauli gate X.
The Pauli gate only gets activated (turned on) if the top lead has value |1⟩.

We can define other control type gates simply by replacing the Pauli gate with another single Qbit gate. We now define
the following single Qbit phase gate 

(Subscript[R, n])  It has the effect of multiplying any of the two single Qbit states by a phase factor 

(e^( i  2π /(2^n)))  if the state is |1⟩ and
by the phase factor 1 if the state is |0⟩

The matrix representation for the (Subscript[R, n]) gate is

(({{1, 0}, {0, (e^( i  2π /(2^n)))}}))


so let's consider the following

The truth table for this, two-Qbit, controlled phase gate is


C(Subscript[R, 2])| 0 0 ⟩ = |0 0 ⟩
C(Subscript[R, 2])| 0 1 ⟩ = |0 1 ⟩
C(Subscript[R, 2])| 1 0 ⟩ =  |1 0 ⟩ =  |1 0 ⟩
C(Subscript[R, 2])| 1 1 ⟩ =  (e^( i  2π /4))|1 1 ⟩ = i |1 1 ⟩

Lets now look at the following circuit

Class exercise: let the input state be | 0 0 ⟩, find the output state.

We start from left and proceed to right

At the dashed blue the input state | 0 ⟩| 0⟩ goes into   H⊗ 1 | 0 ⟩| 0⟩ =  (1/(Sqrt[2]))( |0⟩+|1⟩)  |0⟩ =  (1/(Sqrt[2]))( |00⟩+|10⟩)

Now we pass through the control-(Subscript[R, 2])gate i.e and we get at the green line

(1/(Sqrt[2]))( |00⟩ + |10⟩)

Can you see why this is true?

Finally, after the green dashed line we pass through another Hadamard gate

1⊗H  (1/(Sqrt[2]))( |00⟩ + |10⟩) = (1/(Sqrt[2]))|0⟩H|0⟩ +  (1/(Sqrt[2]))|1⟩H|0⟩ = (1/2)|0⟩(|0⟩ + |1⟩) +  (1/2)|0⟩(|0⟩ + |1⟩) =     (1/2) ( |0⟩ + |1⟩) ⊗  (|0⟩ + |1⟩)      

We note this is the same as (Subscript[U, FT]) |00⟩_2

Let's see what happens for the incoming state |0 1 ⟩

At the green line we have

  H⊗ 1 | 0 ⟩| 1⟩ =  (1/(Sqrt[2]))( |0⟩+|1⟩)  |1⟩ =  (1/(Sqrt[2]))( |01⟩+|11⟩) 
  
  Now we pass through the control-(Subscript[R, 2])gate
  
  C(Subscript[R, 2]) (1/(Sqrt[2]))( |01⟩+|11⟩) = (1/(Sqrt[2]))( |01⟩+i |11⟩) 
  
  Can you see why ?
  
  Finally passing through the Hadamard gate again
  
  1⊗H  (1/(Sqrt[2]))( |01⟩+i |11⟩) = (1/2) ( |0⟩⊗ (|0⟩-|1⟩) +i |1⟩ ⊗ (|0⟩-|1⟩  ) =  (1/2) ( |0⟩ + i |1⟩) ⊗ (|0⟩-|1⟩) 
  
  Note this is equal to  (Subscript[S , 2])(Subscript[U, FT]) |01⟩_2  where (Subscript[S, 2])is a swap operator for 2 Qbits i.e
  
 (Subscript[S, 2])| a b ⟩=|b a⟩
 
 (In general (Subscript[S, 3]) |a b c⟩ = |c⟩(Subscript[S, 2])| a b⟩ = |c b a ⟩  etc. )

Let's check to see if indeed

for the remaining states |1 0 ⟩ and | 1 1 ⟩  the above circuit is equal to 

 (Subscript[S, 2]) (Subscript[U, FT]) |01⟩_2  and  (Subscript[S, 2]) (Subscript[U, FT]) |11⟩_2 respectively.  Since (Subscript[S, 2])(Subscript[S, 2])=1  we then claim that   (Subscript[U, FT]) for n=2, is equal to the following
 diagram

Matrix Representation of (Subscript[U, FT])

In the previous notebooks we constructed matrix representations of (Subscript[U, FT]) . For the case n=2 it is given by

MatrixForm[U[4]]

Thus this matrix should also be obtained by an appropriate products of  single  and 2-Qubit operators shown in the diagram.
Remember we work from left to right.

zero={1,0};
one={0,1};
unit={{1,0},{0,1}};
hadamard=1/Sqrt[2]{{1,1},{1,-1}};
R2={{1,0},{0,Exp[2Pi I/2^k]} /. k->2}

(* for the Control R2 * we note that it can be wriiten in Dirac form *)

Identity ⊗ I0⟩⟨0|  + (Subscript[R, 2])⊗|1⟩⟨1|

zerozero=KroneckerProduct[zero,zero]
oneone=KroneckerProduct[one,one]

CR2=KroneckerProduct[unit,zerozero]+ KroneckerProduct[R2,oneone];
MatrixForm[CR2]

(* from left to right, first gate *)

firstgate=KroneckerProduct[hadamard,unit];
MatrixForm[firstgate]

secondgate=CR2;
MatrixForm[CR2]

thirdgate=KroneckerProduct[unit,hadamard];
MatrixForm[thirdgate]

totalproduct=firstgate.secondgate.thirdgate;
MatrixForm[totalproduct]

Note that this matrix gives the product (1/(2^(n/2))) ( | 0 ⟩ + (e^( i  2π  [.(Subscript[b, 0])])) |1 ⟩)  ( | 0 ⟩ + (e^( i  2π  [.(Subscript[b, 1])(Subscript[b, 0])])) |1 ⟩) swapped ( i.e. bits 1 and 2 are interchanged) ,  but not the (Subscript[U, FT]) because we have not  include the swap operator for two qubits. How does this operator look like? Well, by definition it requires

S |a ⟩|b⟩=|b⟩|a⟩    for all possible a,b  taking the matrix representation (as in our previous homework assignment ) we obtain

S={{1,0,0,0},{0,0,1,0},{0,1,0,0},{0,0,0,1}};
MatrixForm[S]

totalproduct=firstgate.secondgate.thirdgate.S
MatrixForm[totalproduct]
MatrixForm[U[4]]

Thus we see that for n=2 the matrix representation for the above diagram does indeed equate to the matrix representation of our QFT gate. Does this work for any n?  Yes! the diagram for it is (up to a final swap gate )