Shor's  Algorithm

In the previous notebook we defined the Quantum Fourier Transform operator or gate. It's action on a computational
state |m ⟩_n is given by

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

and we demonstrated that (Subscript[U, FT]) is indeed unitary (reversible).

In our discussion of order finding we needed to find the root of the equation

f(x) =1 

where  f(r) ≡Mod[(x^r),n] 

The solution of the smallest r that satisfies that equation is called the order of the x (Mod,n) . We also noted
that r is the period of the function  f(z)  where  z ∈ Integers, i.e.  f(z+r) = f(z). Thus finding the order is equivalent to
finding the period of f(r). Shor's quantum algorithm proceeds by first constructing a 2 register state

(Subscript[|a ⟩, n]) |f(a) ⟩    where a is any of the (2^n) values allowed.  We call (Subscript[| a ⟩, n])  register I,  and | f(a) ⟩ register II. We need
to make sure that register II is large enough that it holds all values of f(a).  We make this state by following our 
quantum protocol

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

now if  y=0 we get

(Subscript[U, f])| x ⟩ |0 ⟩ =  | x ⟩ |f(x) ⟩

which is exactly what we want.

Having constructed the  state 

(Subscript[| a ⟩, n]) |f(a) ⟩ 

which is one of the computational basis states, we want to use quantum parallelism 

to get the following linear combination

(1/(Sqrt[N])) (Underoverscript[ ∑, (a=0), (a=N-1)]) (Subscript[| a ⟩, n]) | f(a) ⟩ 

where N=(2^n).  One way of doing this is by applying a set of Hadamard operators on register one. Let's, for now, agree that we
can make such a linear combination


Now operate the QFT operator (gate) on the first register 

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

Now from our previous discussion on the classical DFT we know that if  f(a) is periodic then the sum

  (Underoverscript[ ∑, (a=0), (a=N-1)])  (e^( i  2π  ((a  k )/N))) |k⟩_n  | f(a) ⟩  can be written as       ( (((e^(2 π i k r M/N))  -1)/( (e^(2 π i k r /N))-1)))  (Underoverscript[ ∑, (a=0), (a=r-1)])  (e^( i  2π  ((a  k )/N))) |k⟩_n  | f(a) ⟩  where r is the period (or order) of
 
 f(x), and therefore we can re-write
 
|(Subscript[ψ, FT]) ⟩  =  (Subscript[U, FT])(Subscript[|(1/(Sqrt[N])) (Underoverscript[ ∑, (a=0), (a=N-1)]) | a  ⟩, n]) |f(a) ⟩     ≈  (1/N) (Underoverscript[ ∑, (k=0), (k=N-1)])    ( (((e^(2 π i k r M/N))  -1)/( (e^(2 π i k r /N))-1)))    (Underoverscript[ ∑, (a=0), (a=N-1)])  (e^( i  2π  ((a  k )/N))) |k⟩_n  | f(a) ⟩ 
 
 Now lets take a measurement of both register I and II ,  We will get one of the possible values of the computational basis
 
 i.e.  we will get a k-value from register I (lets call this (OverTilde[k]), and an f(a) value, lets call this(OverTilde[ f])((OverTilde[a]))  ) then the system "collapses"
 into that computational basis state |(OverTilde[k]) ⟩|(OverTilde[ f])((OverTilde[a])) ⟩  the probability that this event occurs is given by the Born rule
 
|  ⟨ (OverTilde[ f])((OverTilde[a])) | ⟨(OverTilde[k]) |(Subscript[ψ, FT]) ⟩ ((| )^2)   =  |  (1/N) (Underoverscript[ ∑, (k=0), (k=N-1)])    ( (((e^(2 π i k r M/N))  -1)/( (e^(2 π i k r /N))-1)))    (Underoverscript[ ∑, (a=0), (a=N-1)])  (e^( i  2π  ((a  k )/N))) ⟨(OverTilde[k]) |k⟩ ⟨(OverTilde[ f])((OverTilde[a])) | f(a) ⟩ ((|)^2)    Using orthogonality of our
basis e.g.  ⟨(OverTilde[k]) |k⟩=(Subscript[δ, K,])(OverTilde[k])     ⟨(OverTilde[ f])((OverTilde[a])) | f(a) ⟩ = (Subscript[δ, a,])(OverTilde[a])   we get


|  ⟨ (OverTilde[ f])((OverTilde[a])) | ⟨(OverTilde[k]) |(Subscript[ψ, FT]) ⟩ ((| )^2)   =  (1/(N^2))  |( (((e^(2 π i  (OverTilde[k])  r M/N))  -1)/( (e^(2 π i (OverTilde[k]) r /N))-1)))((|)^2)   |(e^( i  2π  (( (OverTilde[a])k )/N))) ((|)^2)   = (1/(N^2))  |( (((e^(2 π i  (OverTilde[k])  r M/N))  -1)/( (e^(2 π i (OverTilde[k]) r /N))-1)))((|)^2) 

so the probability to get a specific result for (OverTilde[k])  and (OverTilde[a])  is independent of the value of  (OverTilde[a]), but does depend on (OverTilde[k]) determined by
the exponential factor  shown above. But this term is exactly the one that arises in the expression for the power spectrum
of the classical DFT. We showed that it is almost zero except for the cases when
 (OverTilde[k]) r /N   has the value of an integer,  or  (OverTilde[k]) is an integer multiple of (1/r).  Thus when measuring the output of of the contents
in register I, for the state |(Subscript[ψ, FT]) ⟩  we are most likely to get the value (OverTilde[k])  that is an integer multiple of 1/r the quantity we are
seeking. Importantly, we will show that the time is takes to perform the quantum calculation scales in polynomial time.