Quantum Fourier Transform

In the previous notebook we defined the discrete fourier transform (DFT)

Suppose we have an n-bit register, which can hold (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     

Notice that the expansion coefficients in |ψ ⟩ are th same factors that appear in the classical Fourier transform i.e. we replaced
(Subscript[f, k])  with  the state |k⟩_n.  The index m also runs over the same range as the index k. We shall now show that state |(Subscript[ψ, m])⟩ is generated
by the action of a unitary operator  (Subscript[U, FT])  that acts on state |m ⟩_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 

Proof.  First we construct the matrix representation for (Subscript[U, FT]) by taking the inner product of both sides in the above equation
by an arbitrary bra ⟨q |  so that

⟨q | (Subscript[U, FT])| m ⟩ =  (1/(Sqrt[N])) (Underoverscript[ ∑, (k=0), (k=N-1)]) (e^( i  2π  ((m  k )/N)))  ⟨q |k⟩     (here I dropped the subscript n in the kets to make the notation easier to look at)

Now we know that our computational basis states |k ⟩  are orthogonal, or  ⟨q|k⟩ = (Subscript[δ, q k])   (The symbol on the right is a Kronecker delta, it is unity
if k=n and zero otherwise ).  So summing over index k, we get

⟨q | (Subscript[U, FT])| m ⟩ =  (1/(Sqrt[N]))  (e^( i  2π  ((m  q )/N)))   in other words the q,m th matrix element of (Subscript[U, FT]) is given by the exponential factor

((Subscript[U, FT]))_qm  = (1/(Sqrt[N]))  (e^( i  2π  ((m  q )/N)))     ( We have to be careful about the use of matrix indices here because usually they start at index=1,2,...N, here
the first row and column are identified by 0 ). Now we know from the definition of the adjoint of a matrix. We interchange row and
collumn indices (Transpose) and take the complex conjugate,

i.e.

((SuperDagger[(Subscript[U, FT])]))_qm = ((SuperStar[(Subscript[U, FT])]))_mq

((SuperDagger[(Subscript[U, FT])]))_qm= (1/(Sqrt[N]))  (e^( -i  2π  ((m  q )/N)))

By definition, a unitary operator (matrix) is such that   (SuperDagger[U])U=1

Thus we require


(∑_(ij=0)^(N-1))(1/(Sqrt[N]))  (e^( i  2π  ((m  j)/N))) (1/(Sqrt[N]))  (e^( -i  2π  ((q  j)/N))) = (∑_(i=0)^(N-1))    (1/N) (e^( i  2π  ((  j)/N)(m-q)))  = 1   if  m=q   and  (∑_(j=0)^(N-1))    (1/N) (e^( i  2π  ((  j)/N)(m-q)))  = 0   otherwise.

The first identity is easy since if m=q we have
 (∑_(i=0)^(N-1))    (1/N)   and since the sum involve N equal terms it is clear that the sum must add to unity. Consider now the alternative 
 
 we know that    (∑_(i=0)^(N-1)) (z^i)  =( (z^N)-1)/(z-1)   in our case  z= (e^( i  2π  (( (m-q))/N)))
 
 so we get   ( (e^( i  2π  (( (m-q) N)/N)))-1)/(z-1)   expanding the exponent  on the numerator   (e^( i  2π   (m-q) ))-1   but m-q is an integer and 
 (e^( i  2π   p)) =1  if p is an integer, so the numerator vanishes and indeed the sum is null. QED
 
 We illustrate this using a few concrete examples.

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

MatrixForm[U]

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

FullSimplify[Udag.U];
MatrixForm[%]