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:

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 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

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 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 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)]
The "tot1" part and "tot2" part are used the FFT value as tot = SQR(tot1*tot1 + tot2*tot2)

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


Created: 8 April 2003
Modified 16 April 2003

Back to my home page Contents of This Document