Shor's Algorithm

Questions:

Question 1 How Does Shor's Algorithm work?
Question 2 Is (Discrete) Fast Fourier Transformation required in order for factorization a number?
Question 3 Does Fast Fourier Transformation physical work on a Quantum Computer?
Question 4 Is Entanglement between the Qubits a necessary requirement for a QC to work?
Question 5 Is Superposition of each Qubit a necessary requirement for a QC to work? at any frequency?
Question 6 Does a Quantum Computer require a clock or synchronisation pulse?
Question 7 Does a Quantum Computer require programming?
Question 8 Are Quantum Computers faster than Classical Computers?
Question 9 How different are Quantum Computers compared to Analog Computers?
Question 10 How different are Quantum Computers compared to Hybrid Computers?
Question 11 Calculating the periodicity in 5 easy steps

Contents


Purpose

The purpose of these question are to investigate if Quantum Computers will replace Classical Computers.


Answer question 1 - Shor's Algorithm

Shor's Algorithm is explained in the following documents:
  1. "Shor's Algorithm for factorizing large numbers" by G. Eric Moorhouse, UW Math http://www.uwyo.edu/moorhouse/slides/talk2.pdf
    In this document Shor's Algorithm is implemented in 6 steps.
  2. "Quantum Computing, Shor's Algorithm, and Parallelism" by Arun, Bhalla, Kenneth Eguro, Matthew Hayward http://alumni.imsa.edu/~matth/quant/433/shor-par/
  3. Bernhard Ímer http://tph.tuwien.ac.at/~oemer/doc/quprog/node18.html
  4. From Wikipedia, the free encyclopedia http://www.wikipedia.org/wiki/Shor's_algorithm
  5. Centre for Quantum Computation http://www.qubit.org/
  6. Lecture Notes on Quantum Computation. Cornell University. Spring 2002. N. David Mermin. http://www.ccmr.cornell.edu/~mermin/qcomp/CS483.html
  7. For the latest article about quantum computers in Nature 421, 823-826(2003)
    "Quantum oscillations in two coupled charge qubits" by:
    YU. A. Pashkin, T. Yamamoto, O. Astafiev, Y. Nakamura, D. V. Averin & J. S. Tsai see:
    http://www.nature.com/nature/journal/v421/n6925/pdf/nature01365.pdf
  8. For an aditional News and Views in Nature 421, 796-797(2003) "Quantum computing: The qubit duet" by Gianni Blatter See: http://www.nature.com/nature/journal/v421/n6925/pdf/421796a.pdf
  9. For the latest situation about Quantum Computation see this: Oversimplifying quantum factoring in Nature. In this document of 11 July 2013 implementation constraints of Shor's Algorithm are discussed.

Simulation Program of Shor's Algorithm

Your author has written a program to simulate Shor's Algorithm
  1. For a copy of the QBasic program select: FINDPRIM.BAS.
  2. For a listing of the QBasic program select: FINDPRIM.HTM.
  3. To execute the QBasic program select: FINDPRIM.ZIP.
  4. For an explanation of the program See: PROGRM19.HTM
  5. For a copy of the program in Excel See: findprim.xls.zip
  6. For a description of how to operate See: findprim.xls.htm


Answer question 2 - Is FFT required

Document 1 explains Shor's Algorithm in 6 steps (See page 18 of 22)
The number to factorize is called: n Step 2 is called "Apply Modular Exponentiation". The result of step 2 is a string of numbers.
For Example in case factorization of n=55 (with x=13) this string is:
1,13,4,52,16,43,9,7,36,28,34,2,26,8,49,32,31,18,14,17
1,13,4,52,16,43,9,7,36,28,34,2,26,8,49,32,31,18,14,17
1,13,4,52,16,43,9,7,36,28,34,2,26,8,49,32,31,18,14,17
etc
i.e. a string of 20 numbers which repeats itself
The important part is to find the periodicity. To do that Shor's algorithm uses FFT. The result is 20. See Document 1 for details.
The next task is to find the middle of those 20 or 19 values. This is the 10th value which is called y.
y = 34. y-1 = 33. y+1 = 35.
The Greatest Common Denominator (GCD) of the numbers 33 with 55 is p = 11. The GCD of the numbers 35 with 55 is q = 5. The two factors of n = 55 are p = 11 and q = 5.

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.
  2. 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
  3. 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
  4. 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
The following table shows if Shor's Algorithm works for prime numbers combinations:
x 3 5 7 11 13 17 19 23 29 31 37 41 43
3 x 2 1 2 2 1 1 4 1 2 2 2 3
5 2 x 1 1 1 1 2 2 3 3 4 1 1
7 1 1 x 2 1 1 3 3 1 4 1 3 1
11 2 1 2 x 3 2 1 4 1 1 1 1 4
13 2 1 1 3 x 2 1 1 4 1 4 4 1
17 1 1 1 2 2 x 1 1 1 1 1 1 1
19 1 2 3 1 1 1 x 2 3 3 1 1 1
23 4 2 3 4 1 1 2 x 1 1 4 1 1
29 1 3 1 1 4 1 3 1 x 1 1 1 4
31 2 3 4 1 1 1 3 1 1 x 1 1 4
37 2 4 1 1 4 1 1 4 1 1 x 1 1
41 2 1 3 1 4 1 1 1 1 1 1 x 1
43 3 1 1 4 1 1 1 1 4 4 1 1 x
Result of 78 tests:
Type 1: 46 times. Type 2: 12 times. Type 3: 9 times. Type 4: 11 times.

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 perodicity r1 is a multiple of 210. To find the real perodicity (=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 perodicity 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 untill 899/29
  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

In order to study the current state of the art of Quantum Computers please read the articles 7 and 8 in NATURE mentioned above.
The memory units of a Classical Computer are FlipFlops. A FlipFlop is a electronic (symmetrical) stable device which is either in the state 0 or 1. The basic building blocks of a FF are transistors; for a FF two. All FlipsFlops are identical. The behaviour of a FF is deterministic; it follows precise mathematical rules. The same for a Classical Computer.
An oscillator is a device very much like a FF and consists of also of two transistors. The connection between the two transistors is different and such that each transistor oscillates between the states 0 and 1 at a certain frequency.
In the articles in NATURE two qubits are discused. Each qubit is like an oscillators. First the two oscillators are studied separated or decoupled and Secondly coupled.
  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.
As part of Shor's Algorithm two specific calculations take place: First to calculate x^a Mod n and Secondly to calculate the Fast Fourier Transformation. As a result of the First calculation the state of Register 2 is measured and as a result of the Second calculation the state of Register 1 is measured.
For example: in case of n = 55, x = 13 and both Register 1 and 2 each consist of 13 bits.
To observe the results of Fast Fourier for n=15, n=55, n=85 and n=119 select:Fast Fourier Transform
  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.
  2. The First calculation is of course the easiest to implement in case the qubits are decoupled.
  3. 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.
  4. 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.
  5. 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 ?
  6. 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.
  7. The probability calculation with SIN functionality for n=15, n=85 and n=119 results in a table with all zero probability values.
  8. 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%
  9. 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

A classical computer or PC works internally with clock pulses. Each instruction in a PC requires one or more clock pulses. For example: a clock pulse indicates that a previous instruction is finished and is used to start execution of the next instruction. The execution of each instruction very often consists of three parts: A fetch part to fetch the instruction from memeory and to read a necessary data value from memory. A calculation part in which a certain arthematic calculation is performed and a store part in which a data value in memory is stored. To subdivide between those parts clock pulses are used.
A quantum computer does not work with clock pulses because a quantum computer contains all the hardware to solve a problem and all the time all the hardware is involved in solving a problem. In that sense a quantum computer is very much like an analog computer.


Answer question 7 - programming

A classical computer or PC requires programming in a higher level programming language in order to describe the problem that you want to solve. A higher level programming language makes the reading, writing and modifying of a programme relative easy.

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

Shor's Algorithm does not answer the question if Quantum Computers are faster than Classical computers. If Shor's Algorithm is the fastest algorithm to factorize a number is also a question mark. The simulation program does not support that claim.
To answer the question if Quantum Computers are faster than classical computers you should only compare FFT on both computers. A Quantum Computer needs only one step to find the periodicity. I have great doubts if it works.


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

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

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

Finally some remarks about the physics of a Quantum Computer


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.


Answer question 11 - Calculating Periodicity in 5 easy steps

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:

The first part is "impossible" on a standard digital computer or PC because you need software which supports roughly 5000 digits.
A different appraoch 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 folow this approach you keep the numbers small.
However IMO you can not 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 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.


Reflection Part 4 - Modular Exponentiation.

As part of shor's algorithm in step 5 Register 1 is measured. This measurement does not directly results in the period, but requires what is called Continued Fraction Convergent to calculate a preliminary period value. The period is an important parameter of the number n to be factorized. To decide if this preliminary value is the period you have to perform the calculation: xvalue mod n.
When the result is 1 (within certain constraints) than value is the period.
When the result is not 1, the real period is a multiple of this value. In this case you have to perform the calculations x2*value mod n, x3*value mod n, x4*value mod n until the result is a 1.
The calculation xa Mod n is called modular exponentiation.
For more detail study: Modular exponentiation The fastest way to perform Modular Exponentiation is to use the Right-to-left binary method. This method is implemeneted in the Excel program findprim.xls in the subroutine Modular_pow

The following table shows 6 examples to study modular exponentiation

p q n simple Fermat Binary x period
29 31 899 15 1 9 21 420
19 131 2489 10 26 8 24 234
53 173 9169 27 18 12 28 2236
89 223 19847 45 16 12 30 3256
199 257 51143 100 2 15 33 25344
199 307 61093 100 6 8 33 198
Table 3
To explain the importance between preliminary period and real period, the following three tables are used.
period 420 210 140 105 84 70 60 rest
% 22 12 11 11 6 5 4 29
# 1 2 3 4 5 6 7 -
Table 4.1 n=899 p=29 q=31

period 234 117 78 39 26 18 13 rest
% 30 31 10 10 6 3 5 5
# 1 2 3 6 9 13 18 -
Table 4.2 n=2489 p=19 q=131
period 2236 1118 559 172 86 rest
% 45 22 23 2 2 4
# 1 2 4 13 26 -
Table 4.3 n=9169 p=53 q=173

period 198 99 66 33 22 18 11 rest
% 30 30 10 10 5 3 5 7
# 1 2 3 6 9 11 18 -
Table 4.4 n=61093 p=199 q=307
The above four tables shown for different n values the chance that the real period or the prelimnary period is measured. Table 4.1 shows the result for n = 899.
The top line shows the possible period values that can be measured. The first value 420 is the real period. The chance that this happens is 22 percent. In that case 1 Modular Exponentiation calculation has to be performed: 21^420 mod 899
The second column shows that in 12 % cases the (preliminary) period 210 is measured. In that case 2 Modular Exponentiation calculations have to be performed: 21^210 Mod 899 and 21^420 Mod 899.
The third column shows that in 11 % cases the (preliminary) period 140 is measured. In that case 3 Modular Exponentiation calculations have to be performed: 21^140 Mod 899, 21^280 Mod 899 and 21^420 Mod 899.

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


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 multiplification 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 functiom x^a mod n until the same result (By preference the value 1) is calculated. Part of the problem is that you can not perform this calculation in parallel because the result of the next value of a depents 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 aproximate 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 mutiply 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 methodes 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 someting in the order of: a*10^20 b*10^10 and c*10^0. To do this type of arithmatic 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 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 "secundary 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 "secundary 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 "Fermats 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 are very bleak. Specific as a tool to do factorization

The above results are calculated with the Excel Program FindPrim.xls which runs a Pentium P4 2.8
For more technical information about program performance for the two values of 390 ms and 62 ms in yellow select the following link:
Quantum Factoring Performance Evaluation - Pentium P4 2.8 - Intel i5 M 460

To evaluate fatorization using Parallel processing select the following link:
Quantum Factoring Performance Evaluation - Using Parallel Processing - VB2010
What the 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.


User discussion (Usenet) about Shor's Algorithm


Feedback

None


Created: 17 December 2002
Last Updated: 23 May 2003
Link updated: 4 December 2009
URL's updated: 12 June 2012
Mod Exp updated: 13 Sept 2013
Use Mod 2 updated: 27 Sept 2013

Back to my home page Contents of This Document