Shor's Algorithm "Findprim_array_x.xls" Operation

Introduction and Purpose

The purpose of Shor's Algorithm is to do factorization on a Quantum Computer.
The purpose of the Excel program "Findprim shor.xls" is to simulate Shor's algorithm on a personal computer or PC.
To understand this program select this link: Findprim shor.xls. The program is identified as phase 1.
The purpose of Excel Program "Findprim_array_x.xls" is the same as "Findprim shor.xls". The primary reason is that a rare error is removed. A second reason is that this version uses integer array logic. The program is identified as phase 2.
This document describes how to operate the Excel Program "Findprim_array_x.xls" and the spreadsheets: "x=x", "x=2", "T?", "T1" and "T234".

For a copy of the Excel program in zip format select:



1. Spreadsheet layout: "x=x"

Figure 1A: pm1 = pm1
Figure 1B: pm1 = c1

1.1 General Description of Spreadsheet: "x=x"

The program is a simulation of Shor's Algorithm as described in this document: 2. Spreadsheet layout: "Get Pr1". Button "Get Prime 1" which is part of the Excel program "Findprim shor.xls".
The layout is shown as Figure 1A and as Figure 1B.
Both Figures show the following columns: There are 4 more parameters which control the execution of the program.

1.2 Operation of Spreadsheet "x=x"

  1. In order to start the program, select the Get Prime 1 Command
  2. Input for the program are two (prime) numbers: pm1 and pm2. Multiplication of those two (prime) numbers gives a number n in column 3, which is factorized using Shor's Algorithm. Those two numbers should be entered in the cells (2,A) and (2,B).
  3. The number of prime number products factorized is controlled by the parameter n primes. The results are stored in one row.
  4. At the beginning of each simulation n is calculated as a product of pm1 and pm2. That means in reality first pm1 and pm2 are calculated, which are the next higher prime numbers. pm2 should be higher as pm1.
  5. The final result is stored in the columns P and Q.

1.3 Discussion

2. Spreadsheet layout: "x=2"

Figure 2A: Button = Get Prime 1
Figure 2B: Button = Get Prime x

2.1 Operation spreadsheet: "x=2"

Sheet "x=2" contains two buttons: "Get Prime 1" and "Get Prime X"

2.2 Discussion

3. Spreadsheet layout: "T?"

Figure 3.1 "Get Prime x". pm1 = pm1
Figure 3.2 "Get Prime x". pm1 = c1

3.1 Operation spreadsheet: "T?"

The purpose of spreadsheet T? is to test in detail the "Calculating Periodicity in 5 easy steps" functionality to factorize the product n of two prime numbers pm1 and pm2. This functionality is identified as phase 1.
Important is the parameter n primes = 50, which shows that the total number of products n factorized is 50.

3.2 Discussion

4. Spreadsheet layout: "T1"

Figure 4.1 "Get Prime x". pm1 = pm1
Figure 4.2 "Get Prime x". pm1 = c1

4.1 Operation spreadsheet: "T1"

The purpose of spreadsheet "T1" is to test in more detail the "Calculating Periodicity in 5 easy steps" functionality to factorize the product of two prime numbers pm1 and pm2. This is identified as: phase 2. The purpose of phase 2 is to solve a problem in the functionality identified as phase 1.

4.2 Discussion

As can be observed in Figure 3.1 the reason, why factorization does not work, lies in the calculation of amin. In all the cases when factorization is in error amin is too small. This are the rows 21 and 24.
The same can be observed in Figure 4.2. The rows in error are 21 and 24. To show this error, the Type is T2.

Amin calculation follows this logical scheme:
     a = 0  :       x = 1
     a = a + 1 :    x = x * 2      'x(a+1) = x(a) * 2
     If x > n    then  x = x - n   
     If x = "stop sign"   then amin = a : exit sub
     goto p1

Subroutine to calculate amin.
The problem is that in certain cases this test is stopped too early. The next occurrence of the "stop sign" should be used.
The actual subroutine used is: Geta_mod2_Int_array2. Two parameters: str_amin$ and Str_xn$ are added to initialize the two variables a and x mentioned in the above subroutine.

5. Spreadsheet layout: "T234"

Figure 5.1 "Get Prime x". pm1 = pm1
Figure 5.2 "Get Prime x". pm1 = pm1

5.1 Operation Spreadsheet: "T234"

The purpose of spreadsheet "T234" is to test in more detail the "Calculating Periodicity in 5 easy steps" functionality to factorize the product of two prime numbers pm1 and pm2. This is identified as: phase 2. The purpose of phase 2 is to solve a problem in the functionality identified as phase 1.
Infact, the program used in case of Spreadsheet T234 is exactly the same as Spreadsheet T1. The main difference that in case of T1 all the examples are displayed. In case of T234 only the lines in error are displayed. Type or error discovered are shown as T2, T3 and T4.
In order to calculate amin the stop sign has to be retrieved. However not always this value of amin works and the searching has to continue, and again. This results in the error types T2, T3, T4 etc. The combination pm1=3 and pm2 = 2113 shows the type T24.

5.2 Discussion

Both Figure 5.1 and Figure 5.2 almost show the same information. The difference is in the parameter line max. The same type of information is also shown for all the 8 examples.

Reflection 1 - Phase 2

One of the main objective of phase 2 was to solve one error in the original program to simulate Shor's algorithm, which performs factorization on a quantum computer, on a digital computer. Already the effort to write the original program was a road of falling and getting up. One of the first discoveries was that Shor's algorithm on a quantum computer does not always work, assuming my understanding, for all values of n = pm1*pm2 on a quantum computer. The possible errors were identified as T1, T2, T3 and T4. The second step was to adept the algorithm such that it would work, preventing large internal numbers and preventing multiplications and divisions, with the object to make the program as fast as possible. This whole process goes in small steps. Often you think you have reached your goal, but additional testing showed that this was not true. A typical case is to write a program to take the square root, with array logic, to handle very large numbers. The final solution was what I called phase 1. The 'error' code was T?
In some sense I was lucky to identify the final solution with a: ?, assuming that it contained no errors. More testing revealed that the solution which I called phase 1, actual contained an error. First you get the feeling: again, what is wrong, why etc. The next step is to try to repeat the error using more examples and see what is common to all errors. Lucky again I soon found how to observe more errors, what the specific cause is and how to fix the error. Your nightmare disappears.
Still, this raises the question: is it possible using Shor's algorithm, to perform factorization, error free, on a Quantum Computer. I have my doubts. Even assuming that the Quantum Computer itself operates error free.

One of the lessons learned from this exercise is, that testing is a very important issue. The advantage of factorization the product of two prime numbers, is that you know the answer. If that is not the case, the results of any computational exercise have to be investigated very carefully. A typical case in point is artificial intelligence, specific if also intermediate results cannot be tested.

Reflection 2



Created:2 May 2023

Back to my home page: Contents of This Document