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

   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 29*31 the simulation of Shor's Algorithm requires 420 steps. The classical Algorithm requires 30 steps.
3. What is more important classical Algorithm always works.
4. To observe the periodicity of all the type 1 combinations select:Perodicity 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 depents 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 qbit 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 depents 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 effect 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 propability of measuring each of those values is not the same. Apparently to measure a single large value is much larger than 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 fuctionality.

   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 propability 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 mentioned 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 oscilates 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.

Lets 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 processes 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 actual see on your screen a line that changes continuously. This line represents the temperature. You can not stop the simulation like you can not stop a 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 arithmatic.
  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 arithmatic 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 simualtion. 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. Rouhgly 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 mechanisme. The Sample bit mechanisme should freeze the states of all the ouputs qubits (or part their of) instantaneous.
With a Hybrid arrangement it is relatif easy to test your Quantum Computer.

                                           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

     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 op 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 relative 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 can not 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 can not 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 parallelisme. 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 otherhand 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 obligatoire 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.

Feedback

Back to my home page Contents of This Document