Shor's Algorithm - FFT optimisation

As part of step 4 the following function is calculated in two ways as tot1 and tot2:

f(c) = Sum e^dwi for d = 0 to M-1 with w = 2pi*c*r/q

As tot1:

f(c) = Sum cos(dw) for d = 0 to M-1 with w = 2pi*c*r/q

As tot2:

f(c) = Sum sin(dw) for d = 0 to M-1 with w = 2pi*c*r/q

The standard way to calculate this function is by means of a loop structure.
However there is also a quicker way available if you consider f(c) as a combination of two functions:

• one function f1(c) = Sum e^dwi for d = 0 to M-1 step 2
  i.e. f1(c) = e^0wi + e^2wi + e^4wi + e^6wi + e^8wi + etc
• one function f2(c) = Sum e^wi for d = 1 to M-1 step 2
  i.e. f2(c) = e^1wi + e^3wi + e^5wi + e^7wi + e^9wi + etc

If you do that than each function f1(c) and f2(c) consists of a set of points which are on a circle. The solution is the length of the line segment between the first and the last point of each circle.

                ........D....D'                D 
                       . .                         .
                      .   .                            .
                     .     .                               G
                    .       .                            .     .
                   .         .                          .          .
                  .           G                       .                C....C'
                 .          .  .                     .             .   .
                .        .      .                  .           .       .
               .      .          .                .        .           .
              .    .              .             .     .                .
             .  .                  .           .  .                    .
            H.......................C....C'   H........................F
           ... .                   .          ..  .                    .
          . . .   .               .           . .     .                .
         .  .  .     .           .            .   .        .           .
        .   .   .       .       .             .    .           .       .
       .    .    .         .   .              .      .             .   .
      .     .     .           F               .       .                B....B'
     .      .      .         .                .         .          .   .
    .       .       .       .                 .          .    .        .
   .        .        .     .                  .           E            .
  .         .         .   .                   .       .                .
 .          .          . .                    .   .                    .  
A...........E...........B.....B'              A........................A'              

           f1(c)                                         f2(c)

The above drawing shows the functions f1(c) and f2(c) for M-1 = 3. The centre of each circle is the point H

• The left part shows the function f1(c) = e^0wi + e^2wi
  The object of this part is to calculate the line segment AC
• The right part shows the function f2(c) = e^1wi + e^3wi
  The object of this part is also to calculate the line segment AC

The final solution is the sum of those two line segments AC for M-1=3 or AD for M-1=5

The projection on a horizontal line through the point A represents the tot1 part
The projection on a vertical line through the point A represents the tot2 part

We will start with the right drawing i.e. f2(c)
The right drawing consists of two triangles ABH and BCH. Triangle ABH consists of two equal legs AH and HB. The bottom leg is tilted over an angle w. The top angle is 2*w. Triangle BCH is of the same size. The first question is what is the angle B'BC

• The line segment AB (and BC and CD) is called x.
  
• The angle BAA' is called w
  
• AE = EB = 0.5*x, AA' = x*cos(w), A'B = x*sin(w)
  
• Angle AHE = Angle EHA = w
  
• HA = HB = HC = 0.5*x/sin(w). HA is also called x1.
  
• Angle A'BA = Angle EBH = Angle HBF = 90-w
  
• Angle B'BC = 360 - 90 - A'BA - EBH - HBF = 270 - (90-w) - (90-w) - (90-w) = 3w

This is a very important result, because when you repeat this same process and you draw the next triangle the angle C'CD becomes 5w. The next angle 7w.
The length of the projection of the line AC on the horizontal line AA'is equal to AB*cos(w) + BC*cos(3w) or x*cos(w)+ x*cos(3w).
This is the "tot1" part of function f2(c).
Because the points A,B and C are on a circle we can also calculate the length of AC directly:

• The angle AHB = angle BHC = 2*w.
• The angle AHC is called sw. sw = 2*2*w = M * w
• The line AC is called x2. x2 = 2*x1*sin(0.5*sw)
• The angle AA'C is 0.5*sw.
• The projection of the line AC on the horizontal line AA' is called x3.
• x3 = x2 * cos(0.5*sw) = 2*x1*sin(0.5*sw) * cos(0.5*sw) = x*sin(0.5*sw)*cos(0.5*sw)/sin(w)

The left drawing is very much identical as the right drawing. The main difference is that the bottom leg AB is not tilted over an angle w. As a result the angle B'BC is not 3w but 2w.
Again also here you can repeat the same proces. The angle C'CD is not 5w but 4w. The next angle 6w.
The length of the projection of the line AC on the horizontal line AA'is equal to AB*cos(0) + BC*cos(2w) or x*cos(0)+ x*cos(2w). This is the "tot1" part of function f1(c).
Because the points A,B and C are on a circle we can also calculate the length of AC directly:

• The angle AHB = angle BHC = 2*w.
• The angle AHC is called sw. sw = 2*2*w = M * w
• The line AC is called x2. x2 = 2*x1*sin(0.5*sw)
• The angle AA'C is 0.5*sw-w
• The projection of the line AC on the horizontal line AA' is called x3.
• x3 = x2 * cos(0.5*sw-w) = 2*x1*sin(0.5*sw) * cos(0.5*sw-w) = x*sin(0.5*sw)*cos(0.5*sw-w)/sin(w)

The total length (Sum of left and right part) of "tot1" part and with x = 1 is:

[sin(0.5*sw)/sin(w)] * [cos(0.5*sw-w) + cos(0.5*sw)]

In order to calculate the FFT value the angle a0 has to be included. This is done by introducing the angle w0, which is equal to w0 = 2*pi*a0*c/q
The total length of "tot1" part including w0(i.e. a0) and with x = 1:

[sin(0.5*sw)/sin(w)] * [cos(0.5*sw + w0 - w) + cos(0.5*sw + w0)]

The total length of "tot2" part including w0(i.e. a0) and with x = 1:

[sin(0.5*sw)/sin(w)] * [cos(0.5*sw + w0 - w - pi/2) + cos(0.5*sw + w0 - pi/2)]

This same strategy can be used to calculate the probablity p(c), but than w0 is not used i.e. w0=0.

Back to my home page Contents of This Document