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:
https://www.nicvroom.be/findprim.xls
For a description of this program See:
https://www.nicvroom.be/findprim.xls.htm
For more information in general See:
https://www.nicvroom.be/
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:
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
"Nicolaas Vroom"
SNIP
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:
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
https://www.nicvroom.be/
See question 23.
"Nicolaas Vroom"
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:
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
https://www.nicvroom.be/
See question 23.
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
then (ab)=a1*b1 mod c
proof
"Grigoris Lionis"
"Nicolaas Vroom"
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
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
Many thanks for telling me this.
(Except instead of the value 27 read 28 above)
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.
In step 2 the operation f(a) = x^a mod n is performed
with x = 13 and n = 55.
My question is how is this function x^a mod n implemented
in a quantum computer.
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:
Studying the pages 15 -17 and figure 4
it is not clear to me if when for example "a" has the
superposition value 2050
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.
"Nicolaas Vroom"
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.
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: https://www.nicvroom.be/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.
Nick
https://www.nicvroom.be/
See question 23 for Shor's Algorithm.
Back to my home page Contents of This Document
>
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.
>
The next step is to calculate y = 28^2050 mod 8383
The result is 3736
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.
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"
> >
>
> >
for caclulating 27^2050 mod 8383
you could do as follows
>
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.
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
b=b1 mod c
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
>
> >
"Nicolaas Vroom"
> > >
> >
> > >
>
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
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
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
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.
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.
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
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
how you select the right U operators (after the H operator ?)
in order to calculate 13^2050 mod 55 (i.e. U11 and U1)
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
>
>
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
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.
Created: 6 June 2003