IMO in order to find the periodicity you do not need FFT.
In the above case as soon as when the value 1 is detected you can stop with string evaluation and you can calculate the 2 factors. The value 1 is called stop sign.

In reality there are four possibilities:

1. The total number of values between two stop signs is odd. y is the value in the middle. However, y is small (See also type 4). Shor's Algorithm works.
   
   For Example: See the factorization of n = 55 above.
   There is no stop sign = 1. In order to calculate p any value can be used. The second factor q is the factorization number divided by p.
   For example in case of factorization of the number 15 (with x=9) this string is:

   1,9,6,9,6,9,6,9,6

   GCD of 9 and 15 is p = 3. q = 15/3 = 5. The two factors of 15 are 3 and 5.
   GCD of 6 and 15 is p = 3. q = 15/3 = 5. The two factors of 15 are 3 and 5.
   For example in case of factorization of the number 77 (with x=14) this string is:

   1,14,42,49,70,56, 14,42,49,70,56,14,42,49,70,56, ...

   GCD of 14 and 77 is p = 7. q = 77/7 = 11. The two factors of 77 are 7 and 11. The same result you get with all the other numbers i.e., 42,49 etc
   

   The total number of values between two stop signs is even. In that case there is no value in the middle and Shor's Algorithm does not work.
   For example, in case of factorization of the number n = 5*29 = 145 this string is:
   

   1,16,111,36,141,81,136,1, 16,111,36,141,81,136,1 16,111,36,141,81,136,1

   For example, in case of factorization of the number n = 11*13 = 143 this string is:
   

   1,16,113,92,42,100,27,3,48,53,133,126,14,81,9,1

   The total number of values between two stop signs is odd. y is the value in the middle However if y is just 1 smaller than the number n you want to factorize. In that case Shor's Algorithm does not work.
   For example in case of factorization of the number n = 3*23 = 69 this string is:
   

   1,14,58,53,38,49,65,13,44,64,68,55,11,16,17,31,20,4,56,25,5,1

   y = 68. The GCD of 67 and 69 is 1. The GCD of 69 and 69 is 69. That means Shor's Algorithm does not work

What the simulation programs tells us is:

1. That Shor's Algorithm only works in 75% of the cases (Type 1 and Type 2).
2. That the number of steps involved with Shor's Algorithm is much larger than if a classical factorization algorithm is used.
   For example if you want to factorize n=899 (=29*31) the simulation of Shor's Algorithm requires 420 multiply calculations. The classical Algorithm requires 15*2 calculations
   Specific if in the case x = 21 and if in step 5 the value 9986 is selected the outcome will be that the periodicity r1 is a multiple of 210. To find the real periodicity (=r) requires the calculations of 21^210 Mod 899 = 869 and 21^420 Mod 899 = 1. These are Hugh calculations.
   To solve this issue the array sxn() is used. This array contains all the relevant Modulo values. The program follows the logic:
   If x^a Mod n = p then x^(a+1) Mod n = p*a Mod n
   The following table shows the results for 3^a mod 10 for a from 0 to 5

     3^0 =   1   
     3^1 =   3    3 Mod 10 = 3
     3^2 =   9    9 Mod 10 = 9   3*3 Mod 10 = 9
     3^3 =  27   27 Mod 10 = 7   9*3 Mod 10 = 7
     3^4 =  81   81 Mod 10 = 1   7*3 Mod 10 = 1
     3^5 = 243  243 Mod 10 = 3   1*3 Mod 10 = 3
   

   These results indicate that if the periodicity is 420 at least 420 multiply calculations are required.
   See also Reflection part 1
   The classical algorithm requires calculations of the type:
   899/3, 899/5, 899/7 until 899/29
3. What is more important classical Algorithm always works.
4. To observe the periodicity of all the type 1 combinations, select:Periodicity Table

   The following table shows if Shor's Algorithm works for prime numbers combinations 5 and 11:

   x	9	10	11	12	13	14	15	16	17	18	19	20
   q	512	1024	2048	4096	8192	16384	32768	65536	131072	262144	524288	1048576
   type	1	2	2	1	1	1	2	3	1	1	4	2

   The following table shows if Shor's Algorithm works for prime numbers combinations 11 and 13:

   x	9	10	11	12	13	14	15	16	17	18	19	20
   q	512	1024	2048	4096	8192	16384	32768	65536	131072	262144	524288	1048576
   type	3	4	2	1	2	3	1	3	4	1	1	1

   The following table shows if Shor's Algorithm works for prime numbers combinations 3 and 23:

   x	9	10	11	12	13	14	15	16	17	18	19	20
   q	512	1024	2048	4096	8192	16384	32768	65536	131072	262144	524288	1048576
   type	2	1	4	2	3	4	2	3	4	2	1	4

   The following table shows if Shor's Algorithm works for prime numbers combinations 13 and 29:

   x	9	10	11	12	13	14	15	16	17	18	19	20
   q	512	1024	2048	4096	8192	16384	32768	65536	131072	262144	524288	1048576
   type	1	1	4	1	2	1	4	3	1	4	4	1

5. The above 4 examples show that in all (?) situations there is always a value of x (and q) that Shor's algorithm works. In some cases, the value of x is more difficult to select than in others.

Answer question 3 - Does FFT work

1. In the decoupled state the two qubits each oscillates at their own frequencies. This is already tricky because it means that the more qubits you have at the more different frequencies each should operate. IMO this implies that the overall system will become slower.
   
2. In the decoupled state each qubit at any moment is in a particular state 0 or 1.
3. In the decoupled state if you consider both qubits than the pattern in which both qubits change into the 4 possibilities is periodic and depends on the two frequencies of each qubit.

                     .  .  .                 .  .  .                 .  .  .                 . 
      .           .           .           .           .           .           .           .
   qbit2 .  .  .                 .  .  .                 .  .  .                 .  .  .
   11100000000000011111111111100000000000011111111111100000000000011111111111100000000000011111
   qbit1           .  .  .               .  .  .               .  .  .               .  .  .
      .          .          .          .          .          .          .          .          .
   bit1 .  .  .               .  .  .               .  .  .               .  .  .
   11100000000000111111111110000000000011111111111000000000001111111111100000000000111111111110
                  .  .  .             .  .  .             .  .  .             .  .  .
      .         .         .         .         .         .         .         .         .         .
   qbit0.  .  .             .  .  .             .  .  .             .  .  .             .  .  .
   11100000000001111111111000000000011111111110000000000111111111100000000001111111111000000000
   77700000000001377777777664400000011133377776666444400111113333366666644445511111333222266664
   

   The above sketch shows the state of three decoupled qubits which have almost identical frequencies (12, 11 and 10).
   The top part shows the state of qubit 2, the middle qubit 1 and the bottom part qubit 0
   The bottom line shows the combined state. Not all states have the same probability in this sketch. State 0 has the highest and state 2 the lowest.
4. In the coupled state there is "information" exchange between the two qubits and the state of each qubit becomes more erratic. However, IMO at each instant each qubit is either in the state 0 or 1.
5. I see no reason to call the overall state entangled.
6. In the coupled state IMO, the behaviour and state of each qubit depends about the coupling constant. That means if you take the two qubits slowly apart the behaviour of each qubit will change. This makes the whole idea about action at the distance very unlikely.
7. The "information" exchange happens under the constraints of the speed of light. That means if you take the two qubits A and B apart and you change the state of A suddenly (You measure A at t1), it will take some time before that change will affect the state of the B qubit, implying that you cannot predict what the state of qubit A was by observing the state of B. As such is FTL responds highly arbitrary.

1. The First calculation is the easiest. Starting point (For Example in case of n=55) is that all the 8192 states of the 13 qubits should have the same probability. However, that rule is not so strict. More important is that when you measure Register 2 you should at least measure one of the following values:
   1,13,4,52,16,43,9,7,36,28,34,2,26,8,49,32,31,18,14,17
   And when you repeat the same experiment, you should measure a different one.

   The First calculation is of course the easiest to implement in case the qubits are decoupled.

   The First calculation is more difficult to implement in case the qubits are Johnson coupled, because of much higher frequencies involved. The more qubits the more difficult.

   The Second calculation is more difficult to implement. The object of this calculation is to find the periodicity. For example: in case of 55 this is the periodicity is 20. Part of the problem is that the periodicity is a physical effect and becomes only visible when you perform the calculation x^a mod n uniquely for x going from 0 to 8191. If you perform this calculation with random values of a than this periodicity does not become visible.

   In the First calculation in case of n=55 only 20 integer values are possible but the chance of measuring each value is identical. In the Second calculation many values are possible for all the possible values of c. Many of those values are small. However, the probability of measuring each of those values is not the same. Apparently to measure a single large value is much larger than measuring any of the many small numbers. Why is that?
   In the First calculation why does 48 not have a higher chance than 1?

   The standard way (?) to calculate FFT is to use COS functionality. The COS functionality uses the Real part of the function e^iwt = cos(wt) + i * sin(wt). Document 1 for n = 55 shows the result with SIN functionality.

   The probability calculation with SIN functionality for n=15, n=85 and n=119 results in a table with all zero probability values.

   The FFT transformation of a SIN(10t) or COS(10t) function has the following shape:

   1 X                   X                   X                   X 
     X                   X                   X                   X
     X                   X                   X                   X
     X                   X                   X                   X
   0 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
     0   2   4   6   8   10  12  14  16  18  20  22  24  26  28  30
       1   3   5   7   9   11  13  15  17  19  21  23  25  27  29  31
   

   n = 119 (With COS functionality) shows this behaviour. The reason is because the periodicity is 8 and is a power of 2.
   n = 85 also shows this behaviour. The periodicity is 16. The FFT values (COS functionality) are 16 values of 1024. The probability values are 16 values of 6.25. The grand total is 100%

   In document 8 mentioned above is written: "For a deterministic entanglement of two quantum degrees of freedom the two constituents must interact in a controlled manner". This whole sentence boils down to the definition of what means: "A controlled manner".
   For example: Controlled by means of the = operation could mean that the state of input and output qubit is always indentical.
   Controlled by means of the inverse operation could mean that the state of the input and output qubit are always opposite.
   This is all very simple. But how do you test that ?

Answer question 4 - Quantum Bit Entanglement

The main topic in the articles 7 and 8 in Nature is about entangled two qubit states. The articles do not mention, if a Quantum Computer can also operate without entanglement i.e., without interaction between the Qubits.
Two different questions or situations should be considered.

1. Is it possible to implement Shor's Algorithm without entanglement between the Qubits of the Registers involved in Step 2 and 3 i.e., in order to calculate the function x^a Mod n?
2. Is it possible to implement Shor's Algorithm without entanglement etc. in Step 4 and 5 i.e., in order to calculate the FFT function?

I expect it is important, specific to do FFT, but I have no glue what the observed differences are.

Answer question 5 - Superposition at any frequency

This question is only appropriate if quantum entanglement is no prerequisite for a QC to operate properly.
Superposition of each Qubit assumes that there is NO interference between the different Qubits of each Register and that each Qubit oscillates at his own frequency.
The same two situations of the previous questions should be investigated.
IMO if it is possible to calculate the function x^a Mod n, assuming that the variable a is implemented in Qubits each in superposition, than it should work also at any frequency including very low frequencies.

Answer question 6 - Clock pulses

Answer question 7 - programming

A quantum computer does not require any programming. If you want to solve a problem on a quantum computer you have to describe first the full problem in detail in all the function blocks (qubits) of a quantum computer and secondly you have to build your specific application out of those function blocks (Qubits) and all the necessary interconnections in total.

Answer question 8

Answer question 9 - Analog Computers

The more I study Shor's Algorithm and Quantum Computers the more similar Quantum Computers are becoming compared to Analog Computers.

The best book to study about Analog Computers is Hybrid Computation

In the following sections we discuss first an Analog Computer secondly a Quantum Computer and thirdly a Digital Computer. Finally, we discuss certain physical aspects of a Quantum Computer.

Let's start with an Analog Computer (AC):

• First of all, an Analog Computer is an electrical system consisting of integrators, multipliers, summers, potentiometers and wires. Those integrators, multipliers etc are the building blocks of the AC which are used in order to build an application. An AC is described by the law of Ohm, the law of Kirchhoff and Maxwell equations.
• Secondly an Analog Computer is mainly used to simulate a whole process, in real time. In order to simulate a process you have to know the differential equations that describe the whole process. In order to simulate those differential equations, the building blocks are used. For example, in order to simulate a second order differential equation you need two integrators.
  
• The emphasis is on whole process. That means if your process is described in full by 20 differential equations your Analog Computer must have enough integrators to implement all, else your simulation is in error. That also means if you want to enlarge your process you have to add integrators.
  
• The emphasis is also on real time. If you want to simulate a temperature in a reactor and you change the setpoint (i.e., you start the process) than you will actually see on your screen a line that changes continuously. This line represents the temperature. You cannot stop the simulation like you cannot stop an actual process.
  
• The fact that your simulation on an analog computer is a physical system becomes clear if you consider that in order to connect the integrators you need wires. If the input of integrator one is equal of the output of integrator two than you only need one wire and you can connect the two points directly. If this is not the case than you need more wires and a potentiometer in between, in order to scale the incoming input signal of integrator one. If integrator one has many inputs than maybe additional summers are required which again require more wires.
  The usage of those wires make each application on an Analog Computer very cumbersome.

The reason why a Quantum Computer (besides major differences which are mentioned later) is so similar as an Analog Computer has many reasons.

• First of all, a Quantum Computer is a physical system which is described by the laws Quantum Mechanics.
• Secondly of on the hardware side your Quantum Computer needs to be large enough to support the full application i.e., all the physical registers (qubits) and all the additional logic to connect those registers and to perform the arithmetic.
  This requirement implies that your Quantum Computer needs to be large enough to support the largest application.
• Third because Quantum Computation is a physical process you can not stop the calculation.
  
• Fourth each different application needs its own Quantum Computer because each application requires its own wirings i.e., connections between registers and logic.

A Digital Computer is completely different from an Analog Computer and a Quantum Computer for many different reasons:

• First of all, the hardware of a Digital Computer (DC) and the User Application are completely separated. That means the user needs nothing to know about the hardware of the PC. The link between the two is the Software. The user has to translate his application in the language of the Software and that is all.
• On the hardware side a DC consists of 4 single arithmetic units (AU): one adder, one subtracter, one multiplier and one divider. The emphasis is on single units i.e., one multiplier while on an Analog Computer you need many multipliers. The software takes care which AU is selected, one after one other.
  For example if you want to calculate a = b * c * d the software takes care that first b * c is calculated and temporary stored. The result is thereafter multiplied with d and stored as a.
  Because of this you do not need more hardware if you want to enlarge your simulation. The only limiting hardware constraint is memory.
• In order to simulate a process on a digital computer the process has to be described in the form of difference equations. Difference equations are easy to translate in software language.
• A simulation of a process on a DC can be stopped. As explained above this is not possible for an AC and QC.

Finally, some remarks about the physics of a Quantum Computer

• The basic building block of a QC is a register consisting of Qubits. In its simplest form it contains one Qubit. Such a Register can be preloaded with a superposition of two values with equal probability: 0 and 1. It is very important that the chance of finding a 0 or a 1 are equal. To test that you have to preload this 100 times. Roughly 50 times you have to measure a 0 and roughly 50 times you have to measure a 1.
• A longer register can consists of 3 Qubits. This Register can be preloaded with a superposition of eight values with equal probability: 0,1,2,3,4,5,6, and 7. It is very important that the chance of measuring each value is equal and 12.5% (normal distribution).
• The above step represents Step 1 in Shor's Algorithm for x = 3 and q = 2^3 = 8
• In Step 2 of Shor's Algorithm, we have to calculate y = x^a mod n for a going from 0 to q-1=7.
  In case of n = 6 (and x=3) we should measure the values 1 (=x^0 mod 6), 3 (=x^1 mod 6), 3 (=x^2 mod 6), 3,3,3,3,3 (=x^7 mod 6). That means 12.5 % chance of 1 and 88.5 % chance of 3. No other value is allowed.

Answer question 10 - Hybrid Computers

A standard Hybrid Computer consists of combination between an Analog Computer and a Digital Computer.
The best comparison with a Quantum Computer is with a sort of Hybrid Computer. That means a Hybrid Computer with a Hugh analog section and a small digital section.
You do not need an ADC (Analog to Digital Converter) and a DAC (Digital to Analog Converter). What you need is an interface to initialize the Qubits of the input Register and an interface to measure the states of the Qubits of the output Register. To measure the states, you need some form of Sample and Hold mechanism. The Sample bit mechanism should freeze the states of all the ouput qubits (or part thereof) instantaneous.
With a Hybrid arrangement it is relatively easy to test your Quantum Computer.

Answer question 11 - Calculating Periodicity in 5 easy steps

• Example 1
  Starting point is the number n you want to factorize. In this case n = 55
  1. Calculate the number amax = (n+1)/2 - sqr(55) = 56/2 - 7 = 28 - 7 = 21
     Use x = 2
  2. Perform modular Exponentiation on the function x^21 mod 55 = 2
     The number 2 is the stop sign
     

      amin                                                        amax
     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
     1  2  4  8  16 32 9 18 36 17 34 13 26 52 49 43 31  7 14 28  1  2  4  8 16 32  9 18
        X                                                           X
     

     The above table shows all the numbers involved.
  3. Start with a= 0: x(0) = 1:
     Now calculate x(1) = x(0) * x mod 55 = 2
     This number is equal to the stop sign: Periodicity = 21 - 1 = 20
  4. Perform Modular Exponentiation on the function x^10 mod 55 = 34. This is y
  5. GCD ( 35, 55) = 5 GCD (33,55) = 11
• Example 2
  n = 55
  1. Calculate the number amax = (n+1)/2 - sqr(55) = 56/2 - 7 = 28 - 7 = 21
     Use x = 6
  2. Perform modular Exponentiation on the function x^21 mod 55 = 4
     The number 4 is the stop sign
     

      amin                                                        amax
     0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
     1  4 16  9 36 34 26 49 31 14  1  4 16  9 36 34 26 49 31 14  1  4 16  9 36 34 26 
        X                                                           X
     

     The above table shows all the numbers involved.
  3. Start with a= 0: x(0) = 1:
     Now calculate a = 1: x(1) = x(0) * x mod 55 = 4
     This number is equal to the stop sign: Periodicity = amax - amin = 21 - 1 = 20
  4. Perform Modular Exponentiation on the function x^10 mod 55 = 1. Error
     Try periodicity 20/2 = 10 Perform Modular Exponentiation on the function x^5 mod 55 = 34. This is y
  5. GCD ( 35, 55) = 5 GCD (33,55) = 11
• Example 3
  n = 10823
  1. Calculate the number amax = (n+1)/2 - sqr(10823) = 10824/2 - 104 = 5412 - 104 = 5308
     Use x = 6
  2. Perform modular Exponentiation on the function x^5308 mod 10823 = 1296
     The number 1296 is the stop sign
     

                     amin                                                            amax
     0   1   2    3     4     5          2652      5302  5303  5304  5305 5306 5307  5308  5309
     1   6  36  216  1296  7776          4109      7516  1804     1     6   36  216  1296  7776
                        X                                                              X
     

     The above table shows all the numbers involved.
  3. Start with a = 0: x(0) = 1:
     Now calculate a = 1: x(1) = x(0) * x mod 10823 = 6
     Now calculate a = 2: x(2) = x(1) * x mod 10823 = 6 * 6 mod 10823 = 36
     Now calculate a = 3: x(3) = x(2) * x mod 10823 = 36 * 6 mod 10823 = 216
     Now calculate a = 4: x(4) = x(3) * x mod 10823 = 216 * 6 mod 10823 = 1296
     This number is equal to the stop sign. amin = 4. Periodicity = amax - amin = 5308 - 4 = 5304
  4. Perform Modular Exponentiation on the function x^2652 mod 10823 = 4109. This is y
     
  5. GCD ( 4110, 10823) = 137 GCD (4108,10823) = 79
• Example 4
  n = 10823
  1. Calculate the number amax = (n+1)/2 - sqr(10823) = 10824/2 - 104 = 5412 - 104 = 5308
     Use x = 2
  2. Perform modular Exponentiation on the function x^5308 mod 10823 = 16
     The number 16 is the stop sign
     

                      amin                                                           amax
     0   1   2    3     4     5          2652      5302  5303  5304  5305 5306 5307  5308  5309
     1   2   4    8    16    32          4109                    1     2    4    8    16
                        X                                                              X
     

     The above table shows all the numbers involved.
  3. But what you see here is very simple: 2^4 = 16 ! You do not need this mod x functionality with large x values.
     You should only use x=2 to find periodicity!
  4. Perform Modular Exponentiation on the function x^2652 mod 10823 = 4109. This is y
     
  5. GCD ( 4110, 10823) = 137 GCD (4108,10823) = 79

For practical results see: Reflection 5 - Cryptography

However there is still an slightly easier way: You can combine step 4 and 5. First calculate the sum of the two prime numbers The sum is equal to n+1 - 2 * period. In this case: (10823 + 1) - (2 * 4109) = 10824 -10608 = 216 the two prime numbers are now: 108 +/- sqr(108^2-10823) = 108 +/- sqr (841) = 108 +/- 29 = 137 and 79

Reflection Part 1

Does a Quantum Computer work? Does a QC do what a QC is supposed to do?
The biggest problem is what do we measure in Register 1 as a result of the FFT i.e., in step 5.
In case of n=55 accordingly to document 1 page 20 the most probable are the 16 values (multiple of 8192/20):

410,819,1229,1638,2458,2867,3277,3686,4506,4915,5325,5734,6554,6963,7373 and 7782
The least probable are the (specific) values: 0, 2048, 4096, 6144 and 8192
However when you do the simulation those 5 values are the most probable.

The first most probable value is the number 410. In step 2 Register 2 is measured. The number M=410 is the total number of values "a" that are the source/cause of the measured value f(x) = x^a mod n. If you know that value than the calculation of the periodicity r is easy because r = 8192/M = 8192/410 = 20.

The question is: is it physical possible to calculate this value instantaneous. There is no problem with the mathematics involved. The issue is: does the mathematics describe the functional behaviour of a physical system.
I have great doubts. Specific after studying the documents 7 and 8 in Nature.

Reflection Part 2

                                           000000
                                           ||||||
                                         ----------
                                        |     H    | 
                                         ----------
                                           ||||||
                      nnnnn  xxxx          cccccc
                      |||||  ||||          ||||||
    -----------       -----------        ----------
0--|           |--a--|           |--R2--|          |--R1
0--|           |--a--|           |--R2--|    FFT   |--R1      Continued
0--|     H     |--a--| x^a mod n |--R2--|          |--R1 ---> Fraction 
0--|           |--a--|           |--R2--|    QFT   |--R1     Convergents
0--|           |--a--|           |--R2--|          |--R1
    -----------       -----------        ----------

         H = Hadamard Operation              FFT = Fast Fourier Transform

The above sketch shows the following Registers to solve factorization of n=55:

1. Register 0000 - 13 Bit Input Register for the Hadamard Operation
2. Register aaaa - 13 Qubit Register with superposition of the values 0-8191
3. Register nnnn - 8 Bit Register with the value 55
4. Register xxxx - 4 Bit Register with the value 13
5. Register R2 - 13 Qubit Register - output of function x^a mod n
6. Register cccc - 13 Qubit Register with superposition of the values 0-8191
7. Register R1 - 13 Qubit Register - output of FFT or QFT function

The above sketch shows the following 4 Transformations:

1. Hadamard Transformation - Input is R0 - Output is Ra
2. Hadamard Transformation - Input is R0 - Output is Rc
3. x^a mod n Transformation - Inputs are Ra, Rn, Rx - Output is R2
4. FFT or QFT Transformation - Inputs are Rc and R2 (measured) - Output is R1

One of the central questions to solve is: how is the x^a mod n Transformation implemented on a Quantum Computer?
Suppose that a = 4089, n = 55 and x = 13 how is the function x^a mod n implemented? Which quantum operators are used? The result should be 28.

The function x^a mod n consists of two parts:

• First you have to calculate 13^4089. This is very difficult because it requires many internally bits.
• Secondly you have to divide 13^4089 by 55. The integer rest value is the answer. Also not easy.

The first part is "impossible" on a standard digital computer or PC because you need software which supports roughly 5000 digits.
A different approach on a PC is the following (by using a Loop structure):

First calculate a=1 or 13^1 mod 55. This is 13

Next calculate a=2 or 13*13 mod 55. This is 169 Mod 55 = 4

Next calculate a=3 or 4*13 mod 55. This is 52 Mod 55 = 52

Next calculate a=4 or 52*13 mod 55. This is 676 Mod 55 = 16

Etc, Etc

Finally calculate a=4089 or ((x^4088 mod n) * x mod n

When you follow this approach you keep the numbers small.
However IMO you cannot follow such a strategy on a Quantum Computer.

Reflection Part 3

     nnnnn  xxxx   0      
     |||||  ||||   |       
   ------------------     ------- 
  | U0 = x^2^0 mod n |---|       |       ------- 
   ------------------    |       |--M0--|       |
    --------             | a0*U0 |      |       | 
   |        |-----a0-----|       |      |       |       -------
0--|   H    |             -------       |M0*M1  |--N0--|       |
   |        |             -------       | mod n |      |       |--R2-- 
0--|        |     U1-----|       |      |       |      |       |
   |        |            | a1*U1 |--M1--|       |      |       |--R2--
0--|        |-----a1-----|       |       -------       |       |
   |        |             -------                      |N0*N1  |--R2--
0--|        |             -------                      | mod n | 
   |        |     U2-----|       |       -------       |       |--R2--
   |        |            | a2*U2 |--M2--|       |      |       |
   |        |-----a2-----|       |      |       |      |       |
   |        |             -------       |M2*M3  |--N1--|       |
   |        |             -------       | mod n |       -------
   |        |     U3-----|       |      |       |
   |        |            | a3*U3 |--M3--|       |
   |        |-----a3-----|       |       -------
    --------              -------
   
       H = Hadamard Operation             
       U0 = x^2^0 mod n    
       U1 = x^2^1 mod n = U0 * U0 mod n    
       U2 = x^2^2 mod n = U1 * U1 mod n
       U3 = x^2^3 mod n = U2 * U2 mod n     

The above sketch shows a possible implementation of the function x^a mod n for a going from 0 to 15.
This sketch is based on figure 4 at page 26 and section F of document http://www.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf. In the latest revision 3/25/03 those pages have been removed.
See also http://lanl.arXiv.org/pdf/quant-ph/9708016 figure 6 and section 6.
In this particular case we have 4 input Qubits a0, a1, a2 and a3. The output register 2 consists of 4 output Qubits. First, we have to calculate the values U0, U1, U2 and U3.

In case of x = 13 and n = 55 we get:

1. U0 = 13^1 Mod 55 = 13
2. U1 = 13^2 Mod 55 = U0 * U0 mod 55 = 4
3. U2 = 13^4 Mod 55 = U1 * U1 Mod 55 = 4 * 4 mod 55 = 16
4. U3 = 13^8 mod 55 = U2 * U2 Mod 55 = 16 * 16 Mod 55 = 36

The value of M0 should be calculated using the following logic: when a0 is equal to 1 then M0 is equal to U0 else M0 = 1. The same for M1, M2 and M3.

Observing the above matrix, you can see that it is relatively easy to calculate the function x^a mod n for all values a from 0 to 15

1. In case of 0 all a0, a1, a2, a3 are 0. M0, M1, M2, M3, N0 and N1 are 1. The final value in R2 becomes 1.
2. In case of 1 only a0 is one. M0 = 13. The final value becomes 13.
3. In case of 2 only a1 is one and the final value becomes 4.
4. In case of 4 only a2 is one and the final value becomes 16.
5. In case of 8 only a3 is one and the final value becomes 36.
6. In case of 3 both a0 and a1 are one. M0 = 13, M1 = 4. N0 = 13*4 Mod 55 = 52. The final value = 52
7. In case of 5 both a0 and a2 are one. M0 = 13, M2 = 16, N0 = 13, N1 = 16. The final value is 13*16 mod 55 = 43
8. In case of 6 both a1 and a2 are one. M1 = 4, M2 = 16, N0 = 4, N1 = 16. The final value is 4*16 mod 55 = 9
9. In case of 7 a0, a1 and a2 are one. M0 = 13, M1= 4, M2 = 16, N0 = 52, N1 = 16. The final value is 52*16 mod 55 = 7
10. In case of 9 both a0 and a3 are one. M0 = 13, M3 = 36, N0 = 13, N1 = 36. The final value is 13*36 mod 55 = 28
11. In case of 10 both a1 and a3 are one. M1 = 4, M3 = 36, N0 = 4, N1 = 36. The final value is 4*36 mod 55 = 34
12. In case of 15 a0, a1, a2 and a3 are one. M0 = 13, M1 = 4, M2 = 16, M3 = 36, N0 = 52, N1 = 26. The final value is 52*26 mod 55 = 32

There is major drawback is speed. Consider for one moment that the Hadamard operation generates the sequence of 16 numbers 0, 1, 2, 3 to 15 with 1 nano second interval each. May be that is not what the Hadamard operation is all about, but let us assume that it is true.
When that is the case the matrix should generate the numbers 1, 13, 4, 52 etc until 32 with the same interval of 1 nano second. If the hardware cannot calculate and react at that same speed you have a problem and you have to slow down the Hadamard number generator.
This becomes definitily an issue for much larger numbers. First because the number of calculation layers will increase. In the above case this is two i.e., an M layer and an N layer. In case of a going from 0 to 255 the number of layers is 3. etc Secondly because of larger numbers the size of each calculation a*b mod n within the matrix will increase.
Even when the Hadamard operation works different this is a problem because when the Hadamard operation generates the numbers too quickly and the calculations inside the matrix cannot follow then the values in Register 2 become unpredictable and wrong. That is not what we want.

Two of the hallmarks of quantum computation are superposition and parallelism. If you study the above sketch only then you will see that the calculation blocks M0*M1 and M2*M3 can be performed in parallel. On the other hand, the next block can only start when the previous two are finished. This makes the use of some sort of clock pulses or synchronisation pulses almost obligatory at the same time reducing the chance of using any form of superposition. The complexity of the calculation blocks like M0*M1 mod n should not be underestimated.

Reflection Part 4 - Modular Exponentiation.

The following table shows 6 examples to study modular exponentiation

• The column "n" shows the number to be factorized and the columns "p" and "q" show the prime numbers used.
• The column "simple" shows the number of calculations (loops) using a simple algorithm to perform factorization of the number "n". The result is equal to smallest prime number used, divided by 2.
• The column "Fermat" shows the number of calculations (loops) using a Fermat's factorization algorithm.
• The column "Binary" shows the number of calculations (loops) uses Right-to-left_binary_method to calculate x^period mod n.
• Column "x" shows the base value.
• Column "period" shows the real period. This is the number to calulate the two prime numbers.

• In table 3, First row (n=899), column Binary shows the value 9. That means to perform the calculation 21^420 Mod 899 requires 9 loops in 22%
  To perform the two calculations 21^210 Mod 899 and 21^420 Mod 899 requires 17 loops in 12%
  To perform the three calculations 21^140 Mod 899, 21^280 Mod 899 and 21^420 Mod 899 requires 24 loops in 11%
  In all the other cases (55%) at least 4 calculations are performed which involve 30 loops.
  That means in 100% Fermat's Factorization algorithm is better, which requires 1 loop.
• In table 3, Second row (n=2489), column Binary shows the value the 8. That means to perform the calculation 24^234 Mod 2489 requires 8 loops in 30%
  To perform the two calculations 24^117 Mod 2489 and 24^234 Mod 2489 requires 16 loops in 31%
  To perform the three calculations 24^78 Mod 2489, 24^117 Mod 2489 and 24^234 Mod 2489 requires 23 loops in 10%
  In all the other cases (29%) at least the six calculations have to be performed, which involve 44 loops
  That means in only 29% Fermat's Factorization algorithm is better, which requires 26 loops.
• In table 3, Third row (n=9169), column Binary shows the value the 12. That means to perform the calculation 28^2236 Mod 9169 requires 12 loops in 45%
  In all the other cases (55%) at least the calculations 28^1118 Mod 9169 and 28^2236 Mod 9169 have to be performed which involve 23 loops.
  That means in 55% Fermat's Factorization algorithm is better, which requires 18 loops.
• In table 3, Sixth row (n=61093), column Binary shows the value the 8. That means to perform the calculation 33^198 Mod 61093 requires 8 loops in 31%
  To perform the two calculations 33^99 Mod 61093 and 33^198 Mod 61093 requires 7 loops in 29%
  In all the other cases (40%) at least the three calculations 33^66 Mod 61093, 33^99 Mod 61093 and 33^198 Mod 61093 which involve 21 loops have to be performed.
  That means in 100% Fermat's Factorization algorithm is better, which requires 6 loops.

This means when you compare Fermat's Factorization Algorithm with the number of loops involved with Modular Exponentiations that you get on average the impression that Fermat's Factorization is difficult to beat. However:

• In some cases, Modular Exponentiation can be a heavy load. For example, in the case of n=61093 there is a 1% chance that the (preliminary) periodicity 2 is measured. In that case 99 calculations have to be performed to find the real periodicity, while Fermat's Algorithm requires 6 calculations (loops)
• When you try higher prime numbers the number of calculations involved using Fermat's Algorithm increases more than with Modular Exponentiation. That means in those cases Shor's Algorithm seems to be the best way to go (not considering any Quantum Computer induced hardware limitations).
  For more detail study this: FindPrim.xls GetPrime 1 - Example 2 n=283321

Reflection Part 5. - Cryptography.

The general application behind Shor's Algorithm is in Cryptography. The idea is to start with two large prime numbers and to calculate the "number n" which is the multiplication of both. The "number n" is in the public domain. See for example Clay Mathematics Institute.
The problem is to calculate the two prime numbers starting from the "number ". The fastest method to use is: Shor's Algorithm. As I already said it is easy to calculate the "number n", but it is very difficult to calculate the prime numbers.

The largest know prime number is: Largest Known prime number in the order of 10^15000000. That means if you multiply two of those numbers you get something in the order of 10^3000000. The question how do you calculate the period (required using shor's algorithm) which is the unknown. The problem is if you use a Quantum Computer and the quantum computer gives the answer "x" how do you know that this answer is correct. In fact, this is a serious problem because Shor's algorithm does not always give the correct answer. See also Question 2. The only way is to use a classical computer, but that is practical impossible? (See next)

The strategy in the QBasic program FINDPRIM (and also in the EXCEL program) is to calculate the period in step 2. This is done by calculating for all "a" starting from 1 the function x^a mod n until the same result (By preference the value 1) is calculated. Part of the problem is that you cannot perform this calculation in parallel because the result of the next value of a depends on the previous value.
Suppose that the period is in the order of 10^20000000. That means you have to perform 10^20000000 multiplications.
To get some idea about this number: in 1 second you can perform 10^10 multiplications. 1 Year consists of 10^10 seconds. That means in 1 year you can execute 10^20 multiplications on 1 PC. Still a long way to go.

A different strategy is to execute the same problem on two different quantum machines. You are "lucky" if both machines give the same answer. The problem is if both are different you have three possibilities: Both are right, both are wrong or only one is right.

In the article Oversimplifying quantum factoring in Nature RSA-768 is discussed which is the largest number yet factored by a general-purpose classical computer. The two prime numbers used are approximate 3.347*10^115 and 3.674*10^115. The result is 10^311.
The document indicates that it is difficult to find the base x (in the Nature document this is the parameter a). They also use the term easy period.
General speaking the real period found on the general-purpose machine should be the same as the period on the Quantum Computer. The real period can be a multiple. In this case, you have an advantage because you know the answer (i.e., the real period) you are looking for. In general, you do not know the answer because what you have are two large prime numbers, the number n and a period calculated on a Quantum Machine.

As indicated above, in cryptography the receiving side has both the composite number n and one prime number pm1. The object is to calculate the second prime number pm2.
When the composite number is in the order of 10^306 and the prime number is in the order of 10^153 it takes on a standard PC roughly 2 seconds to calculate the second prime number. It is important to know that you need special subroutines to perform multiply and divide (integer) operations. The largest number on a standard PC is 10^308. After that more complicated software is required to perform divisions.
A general problem to simulate Shor's algorithm is to calculate the period.

pm1 pm2 n x type period time Fermat 345701 364601 126042930301 50 T1 (1) 630211100 1860,000 sec 0,15625 ms 345701 364601 126042930301 6 T1 (2) 31510555000 1,468 sec 0,15625 ms 645713 664603 429142796939 6 T1 (2) 214570743312 2,812 sec 0,09375 ms 845729 864629 731241819541 6 T1 (2) 365620054592 3,656 sec 0,07812 ms 645713 664603 429142796939 6 T1 (3) 214570743312 1,453 ms 0,09375 ms 845729 864629 731241819541 6 T1 (3) 182810027296 2,172 ms 0,07812 ms 712357 812347 578681071879 6 T1 (3) 289339773588 1,453 ms 2,29687 ms 712357 912349 649918196593 10 T1 (3) 162479142972 3,094 ms 8,03125 ms 712357 912367 649931019019 6 T1 (3) 324964697148 2,109 ms 7,89062 ms 1112351 1212397 1348611015347 6 T1 (4) 674304345300 40,625 ms 1,31250 ms 1212347 1312351 1591024797797 8 T1 (4) 795511136550 35,625 ms 1,20312 ms 345701 364601 126042930301 6 T1 (5) 31510555000 3,906 ms 0,17187 ms 1112351 1212397 1348611015347 6 T1 (5) 674304345300 240,625 ms 1079,68 ms 1212347 1312351 1591024797797 8 T1 (5) 795511136550 218,750 ms 992,96 ms 3347831 3674609 12301969923079 3 T1 (5) 6150981450320 748,438 ms 3960,94 ms 1112351 1212397 1348611015347 6 T1 (6) 674304345300 57,813 ms 1309,37 ms 1212347 1312351 1591024797797 8 T1 (6) 795511136550 51,563 ms 1181,25 ms 3347831 3674609 12301969923079 2 T1 (6) 768872681290 228,125 ms 4643,75 ms 3347831 3674609 12301969923079 3 T1 (6a) 6150981450320 53,125 ms 4643,75 ms 33478079 36746063 1230187600052977 2 T3 (6) 307546882457209 390 ms 53,06 sec 33478079 36746063 1230187600052977 5 T1 (6a) 615093764914418 62 ms 53,06 sec 334780717 367460449 123018672585361933 2 T1 (6) 15377333985390096 2793 ms 539 sec 334780717 367460449 123018672585361933 7 T1 (6a) 30754667970780192 121 ms 539 sec 3347807173 3674604371 12301866871170953183 2 T1 (6) 6150933432074270820 29 sec --- 3347807173 3674604371 12301866871170953183 5 T1 (6a) 6150933432074270820 86 ms --- 33478071761 36746043727 1230186688825349893247 2 T1 (6) 307546672188781444440 300 sec --- 33478071761 36746043727 1230186688825349893247 3 T1 (6a) 615093344377562888880 94 ms --- 334780716989 367460436671 123018668453808408303619 2 T1 (6) 61509334226553083574980 3131 sec --- 334780716989 367460436671 123018668453808408303619 3 T1 (6a) 61509334226553083574980 125 ms --- 3347807169919 3674604366743 12301866845597881993603817 2 T1 (6) 61509334226553083574980 28736 sec --- 3347807169919 3674604366743 12301866845597881993603817 3 T1 (6a) 61509334226553083574980 148 ms ---

Table 5 CPU Performance P4

What the table shows are the results of two different ways to do period finding.

1. The lines with Type T1 (1) show period finding starting from the bottom.
   First you calculate x mod n. This value is stored as a stop sign. (x^0 mod n = 1)
   Next you start with a=2 and you calculate x^a mod n and you compare the result with the values 1 and the stop sign
   You repeat this process with the next value of a until you find a match this will give you the period.
   Next you calculate the values y,p and q using GCD.
2. The lines with Type T1 (2) show the results when you start from the back.
   The initial value of a is n=pm1*pm2/2. Next you calculate x^a mod n using Modular Exponentiation.
   Next you calculate a^x mod n for a=a-1 until you find the values 1 or the stop sign. This gives you the period.
   Next you calculate the values y,p and q using GCD.
   
3. The problem with both methods is that the result can be that p=1.
   When you go upwards you can try a period which is twice as high.
   When you go downwards you can try a period which is twice as small.
   
4. The lines with Type T1 (3) show a time of roughly 2 ms.
   This time is calculated based on the assumption that the period is equal to: (n+1)/2 - (pm1+pm2)/2
   In this case you have to perform the calculation of the function a^x mod n at least twice:
   • Once with a = period. The result should be 1 in case of type T1
   • The second time with a = period/2. The result is y.
     Next you have to perform the GCD operation twice to calculate p and g.
   However, this method requires a warning. The factor pm1+pm2 is not known!
5. The line with Type T1 (4) uses the same methodology as Type T1 (3)
   The time is also calculated based on the assumption that the period is equal to: (n+1)/2 - (pm1+pm2)/2
   In this particular case you have to perform the calculation of the function a^x mod n two times.
   The basic concept of the program is integer logic. That means whole numbers. You cannot use floating point numbers. In this particular case the numbers become too large. That means a number like 1234567890123 has to be divided into two parts. One part is 123 * 10^10 and the second part 4567890123 * 10^0. When you multiply two of those numbers you get something in the order of: a*10^20 b*10^10 and c*10^0. To do this type of arithmetic you need special subroutines. That is why the performance decreases.
   The bottom line is that this decrease in performance is an both an issue when you do factorization with a simulation of Shor's algorithm on a standard PC or when you use a Quantum Computer. Both approaches require Modular Exponentiation.
6. The line with Type T1 (5) uses a slightly different way to calculate the period.
   In this particular case the number "amax" = (n+1)/2 - int(sqr(n)) is calculated.
   The number "amax" is next used to calculate the "secundary stop sign" with Modular Exponentiation.
   Using the methodology x(a+1) = x(a)*x mod n (starting from a = 1) the "primary stop sign" is calculated. The "primary stop sign" is detected when the value x(a+1) is equal to the "secondary stop sign".
   The difference between the values (a+1) and "amax" is the period.
   
7. The line with Type T1 (6) uses the same methodology as with Type T1 (5)
   In this particular case the number "amax" = (n+1)/2 - int(sqr(n)) is also calculated, however with x = 2
   The number "amax" is also here used to calculate the "secondary stop sign" with Modular Exponentiation.
   However to calculate the "primary stop sign" is now much faster, because x(a+1) = x(a)*2 mod n is simpler to calculate.
8. The line with Type T1 (6a) uses the same methodology as with Type T1 (6)
   The difference is that Type T1 (6) show the results with x = 2 while Type T1 (6a) shows the results with higher values of x.
   Type T1 (6) with x = 2 is used to calculate the period. Type T1 (6a) assumes that the period is already known. This can be beneficiary in case x=2 does not give the two primary numbers.
   The time scales of Type T1 (6a) are in the ms range and almost constant for larger values of n. The main reason is because they only require Modular Exponentiation. The minimum number is two.

What the table shows is that in case of Type T1 (5), the results in milli seconds of the column "Time" is smaller than in the column "Fermat". In both cases array logic subroutines are used.
What this means is that the simulated "Shor's Algorithm" method is faster than "Fermat's algorithm" on a standard PC.
In the case of Type T1 (6a) the values of the column "Time" are in the milli second range. The time values are equivalent of 2 (or 3) times the time of Modular Exponentiation.
In the case of Type T1 (6) the values of the column "Time" are in the second range. The reason of this increase is the calculation of the period. This requires the calculation of the function 2^x mod n = xn or xn = xn-1 * 2 mod n until the stop sign is detected.
For more detail about this strategy see Question 11 "Calculating Periodicity in 5 Easy steps"

IMO the lesson to be learned from this exercise that the future of practical Quantum Computation is very bleak. Specific as a tool to do factorization

To evaluate Quantum Factoring Performance factorization using Parallel Processing select each of the following links in succession:

Quantum Factoring Performance Evaluation - Using Parallel Processing - VB2010
Quantum Factoring Performance Evaluation - Using Parallel Processing - VB2019
Quantum Factoring Performance Evaluation - Using Parallel Processing - VB2022

What the VB2010 program demonstrates is Quantum Computer performance on your own PC. Specific is discussed, how the performance of the value 29 in green in Table 5 with roughly a factor 4 can be improved. Try it out yourself.
What the VB2019 program demonstrates that the algorithm works (seems to work) for all possible combinations of large prime numbers.
What the VB2020 program demonstrates that the algorithm which seems to work still contains two errors i.e., the path to victory is slow.

User discussion (Usenet) about Shor's Algorithm

• The document Feasibility of Shor's Algorithm in serious doubt discusses in sci.physics.research the posting: quantum computing=bad science? as of October 2001. 24 messages. The area considered is mainly physical.
• Discussion in sci.physics,research started 2 December 2002 Quantum Computers 36 messages.
  The same postings can also be studied from this link: Quantum Computers 41 messages
  Or from this link: Quantum Computers
  3 messages are from Peter Shor.
• Discussion in sci.physics started 29 April 2003 Quantum Computers and Shor's algorithm 4 messages.
• Discussion in sci.physics.research started 16 August 2013 Quantum Computers and Shor's algorithm 4 messages.
• Discussion in sci.math started 14 November 2013 Quantum Computers and Shor's algorithm 5 messages.

Feedback

Back to my home page Contents of This Document