### Quantum Computers and Shor's Algorithm

 1 "Nicolaas Vroom" Quantum Computers and Shor's Algorithm dinsdag 29 april 2003 16:17 2 "Nicolaas Vroom" Re: Quantum Computers and Shor's Algorithm donderdag 8 mei 2003 14:35 3 "Grigoris Lionis" Re: Quantum Computers and Shor's Algorithm donderdag 8 mei 2003 15:02 4 "Nicolaas Vroom" Re: Quantum Computers and Shor's Algorithm woensdag 21 mei 2003 13:12 5 "Nicolaas Vroom" Re: Quantum Computers and Shor's Algorithm vrijdag 23 mei 2003 14:10

### 1 Quantum Computers and Shor's Algorithm

Van: "Nicolaas Vroom"
Onderwerp: Quantum Computers and Shor's Algorithm
Datum: dinsdag 29 april 2003 16:17

As part of my ongoing study of Quantum Computers I have written a program in Visual Basic for Excell to simulate Shor's Algorithm in 6 steps.

My simulation program is based around the following document: "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.

For a copy of my program See: http://users.pandora.be/nicvroom/findprim.xls
For a description of this program See: http://users.pandora.be/nicvroom/findprim.xls.htm For more information in general See: http://users.pandora.be/nicvroom/
Question 23 Discusses Shor's Algorithm

First I have tested my program with 55 and the result is almost identical as mentioned in the above document.

Secondly I have tested my program with 8383 the simulation works fine however step 6 gives a problem which challenges the whole validity that Shor's Algorithm is the fastest algorithm to factorize a number.

If you use the program to factorize 8383 First it tells you that x=28 and q=268435456.
As part of step 3 you can measure register 2 on your QC You can enter nothing than the "QC" selects something random But you can also select 1 for the next step.

As part of step 5 you can measure register 1 on your QC You again can enter nothing than the "QC" selects something random

All of above is okay and can go very fast.

But you can also select for example 65472 or (205123972)
As a result of Step 6 on your PC you calculate: Continued Fraction Convergent of 65472

0 a = 0          p =  65472 / 268435456
1 a = 4100   p =  256 / 65472    Convergent  1 / 4100
2 a = 255     p =  192 / 256      Convergent  255 / 1045501
3 a = 1         p =  64 / 192       Convergent  256 / 1049601
4 a = 3         p =  0 / 64         Convergent  1023 / 4194304
Possible values for periodicity r are multiples of r1 =  4100
r = 4100

The next step is to calculate y = 28^2050 mod 8383 The result is 3736

But now we have a problem:

how do you do that "fast" in "one step" ?
On my pc I do that in a do loop of 2050 calculations but that is a very slow methode.

Part of the problem is in order to calculate 28^2050 fast on a PC you need a tremendous powerfull PC which huge registers.

Remember this is only a simple example for really large numbers of 100 digits this becomes impossible to handle except if you do it in a loop but that makes shor's algorithm very very slow.

The only alternative is to calculate y = 28^2050 mod 8383 on a QC but how can you do that single calculation on a QC ? I would like to see the details. Do you also need some form of a loop structure ?

If you cannot perform this calculation on a QC then the total execution of Shor's Algorithm is not fast. and slower than for example a Sieve Algorithm.

Finally If you have y = 3736 Than you have to calculate GCD(3737,8383) and GCD(3735,8383) which will give you the final answer 83 and 101 But that is easy and gives no problem on a PC

I hope that my descriptions and questions are clear.

Nick

### 2 Quantum Computers and Shor's Algorithm

Van: "Nicolaas Vroom"
Onderwerp: Re: Quantum Computers and Shor's Algorithm
Datum: donderdag 8 mei 2003 14:35

"Nicolaas Vroom" schreef in bericht news:KZvra.66984\$t_2.5998@afrodite.telenet-ops.be...

 > My simulation program is based around the following document: "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.

SNIP

 > The next step is to calculate y = 28^2050 mod 8383 The result is 3736

Shor's Algorithm consists of 6 "steps".

All those steps are either short calculations on a PC or can be performed (in principle) very fast on a QC.

As far as I'am concerned there is one problem. In case of factorization of 8383 you have to calculate: 28^2050 mod 8383

I have asked for advice how you do that fast. Untill now I received no help:
1. Either by telling me that that calculation has not to be performed (is of no importance)
2. Or by telling me how that calculation can be done fast. My best quess is on a QC because on a PC that calculation is done definitively slow.

My main concern of this issue is: that if one step is slow (part of step 6) then what is the importance of Shor's Algorithm?

Nick http://users.pandora.be/nicvroom/ See question 23.

### 3 Quantum Computers and Shor's Algorithm

Van: "Grigoris Lionis"
Onderwerp: Re: Quantum Computers and Shor's Algorithm
Datum: donderdag 8 mei 2003 15:02

"Nicolaas Vroom" wrote in message news:nasua.79321\$t_2.7477@afrodite.telenet-ops.be...
 > "Nicolaas Vroom" schreef in bericht news:KZvra.66984\$t_2.5998@afrodite.telenet-ops.be...
 > > My simulation program is based around the following document: "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.
 > SNIP
 > > The next step is to calculate y = 28^2050 mod 8383 The result is 3736
 > Shor's Algorithm consists of 6 "steps". All those steps are either short calculations on a PC or can be performed (in principle) very fast on a QC. As far as I'am concerned there is one problem. In case of factorization of 8383 you have to calculate: 28^2050 mod 8383 I have asked for advice how you do that fast. Untill now I received no help: 1. Either by telling me that that calculation has not to be performed (is of no importance) 2. Or by telling me how that calculation can be done fast. My best quess is on a QC because on a PC that calculation is done definitively slow. My main concern of this issue is: that if one step is slow (part of step 6) then what is the importance of Shor's Algorithm? Nick http://users.pandora.be/nicvroom/ See question 23.
for caclulating 27^2050 mod 8383 you could do as follows

a=27^1 mod 8383
b=27^2 mod 8383= a^2 mod 8383
c=27^4 mod 8383=b^2 mod 8383
d=27^8 mod 8383=c^2 mod 8383
e=27^16 mod 8383=d^2 mod 8383
f=27^32 mod 8383=e^2 mod 8383
g=27^64 mod 8383= f^2 mod 8383
h=27^128 mod 8383=g^2 mod 8383
i=...
...
...
p=27^2048 mod 8383

thn 27^2050 mod 8383=(p*b) mod 8383

therefore , you only need O(log(2050)) operations in order to do compute what you are searching

if a=a1 mod c
b=b1 mod c

then (ab)=a1*b1 mod c

proof

a=a1 mod c -> a=a1+k1*c
b=b1 mod c -> b=b1+k2*c
therefore
a*b=(a1+k1*c)(b1+k2*c)=a1*b1+c*(a1*k2+b1*k1+k1*k2*c
so  (a*b)=a1*b1 mod c

### 4 Quantum Computers and Shor's Algorithm

Van: "Nicolaas Vroom"
Onderwerp: Re: Quantum Computers and Shor's Algorithm
Datum: woensdag 21 mei 2003 13:12

"Grigoris Lionis" schreef in bericht news:b9dkm9\$hoc\$1@ulysses.noc.ntua.gr...
 > "Nicolaas Vroom" wrote in message news:nasua.79321\$t_2.7477@afrodite.telenet-ops.be...
 > > "Nicolaas Vroom" schreef in bericht news:KZvra.66984\$t_2.5998@afrodite.telenet-ops.be...
 > > > My simulation program is based around the following document: "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.
 > > SNIP
 > > > The next step is to calculate y = 28^2050 mod 8383 The result is 3736

SNIP

 > for caclulating 27^2050 mod 8383 you could do as follows a=27^1 mod 8383 b=27^2 mod 8383= a^2 mod 8383 c=27^4 mod 8383=b^2 mod 8383 d=27^8 mod 8383=c^2 mod 8383 e=27^16 mod 8383=d^2 mod 8383 f=27^32 mod 8383=e^2 mod 8383 g=27^64 mod 8383= f^2 mod 8383 h=27^128 mod 8383=g^2 mod 8383 i=... ... ... p=27^2048 mod 8383 thn 27^2050 mod 8383=(p*b) mod 8383 therefore , you only need O(log(2050)) operations in order to do compute what you are searching if a=a1 mod c b=b1 mod c then (ab)=a1*b1 mod c proof a=a1 mod c -> a=a1+k1*c b=b1 mod c -> b=b1+k2*c therefore a*b=(a1+k1*c)(b1+k2*c)=a1*b1+c*(a1*k2+b1*k1+k1*k2*c) so(a*b)=a1*b1 mod c

Many thanks for telling me this. (Except instead of the value 27 read 28 above)
It improves my trust that Shor's Algorithm is fast (but it does not solve all my worries) Today I discovered that that same information (sort of) can also be found at page 15 of:
http://www.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf by David Mermin

In case of factorizing n=55 you need an input register of 13 Qubits. See Moorhouse document mentioned at beginning of this posting which discusses this example.
After Hadamard operation in step 1 the 13 Qubits output register is in a superposition state of 8192 values that means when your measure the state of the output register you have an equal chance to find any value between 0 and 8192 with 0 included.
The state of the output register is called a.

In step 2 the operation f(a) = x^a mod n is performed with x = 13 and n = 55.
The result can again be stored in an output register of 13 Qubits (This one is called Register2) which is in a superposition state of 20 values one of which is the value 28 which is measured in step 3.

My question is how is this function x^a mod n implemented in a quantum computer.
I doubt they use the methodology as explained as explained above because that can only be implemented on a classical computer ?
It is not "easy". The final step 28^2050 mod 8383=(p*b) mod 8383 is still rather complicated because you have to "calculate" that 28^2050 mod 8383 is a combination of two calculations:
28^2048 mod 8383 and 28^2 mod 8383 because 2050 is made up (the sum) of 2048 + 2

I doubt they use the methodology: f(a+1) = f(a) * x mod n because that implies that you use a previous superposition state.

In document page 15-17 and figure 4 of:
http://www.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf they use an operator U in case of 13^a mod n the U operators are:

U0 = 13^2^0= 13^1   U1= 13^2^1= 13^2   U2 = 13^2^2 = 13^4  U3 = 13^8

Studying the pages 15 -17 and figure 4 it is not clear to me if when for example "a" has the superposition value 2050
how you select the right U operators (after the H operator ?) in order to calculate 13^2050 mod 55 (i.e. U11 and U1)

It is also not clear if they perform step 3 (i.e. measure register 2) as explained in the Moorhouse document.

It seems that the Mermin document describes a more integrated approach.

### 2 Quantum Computers and Shor's Algorithm

Van: "Nicolaas Vroom"
Onderwerp: Re: Quantum Computers and Shor's Algorithm
Datum: vrijdag 23 mei 2003 14:10

"Nicolaas Vroom" schreef in bericht news:eaJya.12252\$1u5.941@afrodite.telenet-ops.be...
 > My question is how is this function x^a mod n implemented in a quantum computer. In document page 15-17 and figure 4 of: http://www.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf they use an operator U

In the latest version those pages are removed.

 > in case of 13^a mod n the U operators are: U0 = 13^2^0= 13^1 U1= 13^2^1= 13^2 U2 = 13^2^2 = 13^4 U3 = 13^8 Studying the pages 15 -17 and figure 4 it is not clear to me if when for example "a" has the superposition value 2050 how you select the right U operators (after the H operator ?) in order to calculate 13^2050 mod 55 (i.e. U11 and U1) It is also not clear if they perform step 3 (i.e. measure register 2) as explained in the Moorhouse document. It seems that the Mermin document describes a more integrated approach.

Based on the above mentioned document I have designed my own solution how to implement the function x^a mod n See: http://users.pandora.be/nicvroom/shor.htm#ref3

However I think that it is slow raising doubts that it can incorporate any form of superposition or quantum entanglement.

In order to use my design for 200 digits numbers the quantum computer needs to be terrible large and big, which I expect becomes impossible to built.

One of the building blocks of my design is a block to calculate the function p*q mod n. Such a function is easy to perform and calculate on a classical computer or PC.

i.e.  a = p*q
b = int (a/n)
result = c =  a - b*n
If some one can tell me how that function is executed on a quantum computer I will be very gratefull.

Nick http://users.pandora.be/nicvroom/ See question 23 for Shor's Algorithm.

Created: 6 June 2003

Back to my home page Contents of This Document