Comments about the article in Nature: Oversimplifying quantum factoring

Following is a discussion about this article in Nature Volume 499, 11 July 2013
In the last paragraph I explain my own opinion.

Header

The article in the header starts with the following text:
Previous experimental implementations of Shor's Algorithm have used simplifications dependent on knowing the factors in advance. Etc
Valid implementations should not make use of the answer sought.
The second sentence is correct. At the same time it is important to investigate if Shor's Algorithm is capable to factor all composite numbers.
There have already been several small scale demonstrations of Shor's algorithm but these experiments have factored number no larger than 21.
That means the combinations (3 and 5) and (3 and 7). That means almost nothing. The progress is extremely slow.
Given a composite number N=pq Shor's algorithm efficiently computes the factors p and q from N.
In this setting 'efficiently' means that the size of the computer and length of the computation required scales polynomially in Log N, the number of digits of N.
The issue is computation time. Quantum computers should be faster than classical computers (and as accurate) given the same problem.
The issue is not the size of the computers. In fact the size of a quantum computer increases when the size of composite number N increases because more quantum logic is required. For a classical computer this is not the case for the program, which can be used to solve any number N. The only 'issue' is the memory size.
The main reason is because a Quantum Computer is in a superposition state to solve the whole problem at once. A Classical Computer solves the problem step by step and can use loops.
For more information about the issues involved read this: Shor's Algorithm - 10 questions

Main article

The main article starts with the following sentence:
Building a quantum computer capable of factoring larger numbers than any classical computer can etc.
This sentence should be: Building a quantum computer capable of faster factoring large numbers etc.
Such a device would have to be a fully scalable fault-tolerant quantum device capable of carrying out any task a quantum computer could be asked to do.
I hope the authors of the article mean: A quantum computer (build using quantum logic) should be able to solve the same problems presently performed on a classical computer but faster.
I doubt this. The main reason is: why does a quantum computer to factor a number requires a special algorithm? The fact that quantum computers require special algorithms already imply that quantum computers are special purpose machines and not general purpose.
For more information about the issues involved read this: Shor's Algorithm - 10 questions
The ability to compute this period allows the factor to be found, and this can be done efficiently on a Quantum Computer. See Box 1
Efficiently meaning IMO faster and as accurate compared to a classical computer or PC.

Compiling Shor's Algorithm

In 2001 the composite 15 was factored using two different bases an 'easy' base (a = 11) and a 'difficult' base (a=7).
We are speaking here of 2001. In the last 10 years almost nothing has happened.

The following table shows if Shor's Algorithm works for prime numbers combinations 3 and 5 (N=15):
a 6 7 8 9 10 11 12 13
q 64 128 256 512 1024 2048 4096 8192
type 2 1 1 2 2 1 2 1
period 1 4 4 2 1 2 4 4
y 6 4 4 9 10 11 12 4

In the above table type 1 means type T1 (with stop sign) and type 2 means type T2 (no stop sign).
See Shor's Algorithm - Question 2 for details.
There are four T1 combinations. Those with a = 7,8,11 and 13.
The parameter y = a^(r/2) mentioned in step 7
Next is written in the Nature article:
More recently 21 has been factored. These results are summarized in Table 1
What Table 1 shows is that only the numbers N=15 and N=21 are factorized. However in each case only for one value of N and one value of a That means only for specific, predefined cases and not in general. This in turn means that until now no one has build any general implementation using Shor's Algorithm to factorize composite numbers.

Box 1 - Shor's algorithm

Given an integer N=p*q with p,q distinct primes, one proceeds as follows:
Next a recipe of 7 steps is shown.
For an implementation of those 7 steps on a classical computer the Excel program findprim.xls can be used. For a description of the program select this link: findprim.xls.htm . The excel program more or less contain the same 7 steps except that the function a^x mod N is implemented as x^a mod N.
When you investigate the 7 steps than step 1, 2, 3 (partly), 6 (partly) and 7 are performed on a classical PC.
As part of step (6) is written:
With reasonable probability, etc for some y' near y will be an integer multiple r1 of the period r of the function fa(x) = a^x mod N
In the case when p and q are 29 and 31 then N = 899. The period r is 420.
Depending on the value measured in Register 1 and with a = 21 the period r can be a multiple of 210. That means the following two functions have to be calculated: 21^210 Mod 899 and 21^420 Mod 899. The result of the second function is 1, which means the period is 420.
The problem is that the calculation of those functions is huge and requires resp. 210 and 420 multiply instructions, much more than a classical implementation. This raises a reasonable doubt about the usefulness of Shor's Algorithm.

The following table shows if Shor's Algorithm works for prime numbers combinations 5 and 11:
a 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
period 10 2 1 4 20 10 5 5 20 20 10 5

What the above table shows that there are only T1 type of solutions (With stop sign and even periodicity) for a = 9,12,13, 16 and 17.
To find all the solutions use the "Findprime 2" application of the Excel program findprim.xls "Blad2"

In the text of the Nature article is further on written:
Here we etc show that any composite number pq has compiled versions of Shor's algorithm that can run on a very small quantum computer. In particular, we show that there always exits a base "a" such that r = 2.
The following table shows different prime number combinations with r = 2

pm1 pm2 n a q type period y p q
3 5 15 11 2048 T1 2 11 3 5
3 5 15 19 524288 T1 2 4 5 3
3 5 15 26 67108864 T1 2 11 3 5
3 13 39 14 16384 T1 2 14 3 13
5 11 55 21 2097152 T1 2 21 11 5
5 13 65 14 16384 T1 2 14 5 13
5 17 85 16 65536 T1 2 16 17 5
5 19 95 39 5,49E+11 T1 2 39 5 19
7 11 77 34 17179869184 T1 2 34 7 11
7 13 91 27 134217728 T1 2 27 7 13
7 17 119 50 1,1259E+15 T1 2 50 17 7
11 13 143 12 4096 T1 2 12 13 11
11 17 187 21 2097152 T1 4 67 17 11

In order to find the examples the above mentioned "Find Prime 2" Excel application is used.
In all those cases y = a ^ (r/2) = a
In reality the cases where period = 2 are rare.

Experiment

Although the circuit shown in Fig 2 is far simpler than the general Shor's Algorithm it is by no means trivial to implement this two-qubit circuit.
The question should be raised what it is purpose to build circuit's which can only be used to solve Shor's algorithm with a period of 2? IMO what you need is a register which contains the number n=55 and a register which contains the number a= 21.
But if you know that r = 2 you also know the parameter y, which is 21.
Calculating GCD(21+1,55) and GCD(21-1,55) show that p and q are equal to 5 and 11.
RSA - 768 is the largest number yet factored by a general-purpose classical algorithm.
IMO there will never be build any general-purpose quantum computer which can solve RSA-768 faster than by a general-purpose classical algorithm on a von Neumann based architecture (which all the PC's are)

Box 2 - RSA 768

The two prime numbers are approximate 3.3*10^114 and 3.6*10^114. n is equal to: 1.2*10^229
When you try to calculate n with the two prime number in the article, the result is wrong
The first prime number in the article is wrong.
The line with the number 4794983713768568912433889828837938780022876147116
should be: 47949837137685689124313889828837938780022876147116
A number 1 is missing.

Conclusions

Of course this should not be considered a serious demonstration of Shor's algorithm.
I fully agree it does not.
It does however illustrate the danger in 'compiled' demonstrations of Shor's algorithm.
The Excel program FindPrim.xls is a general purpose simulation of Shor's Algorithm using a classical PC. The basic limitations are that it can only be used for small numbers less than 2^26.
Any circuit build should be able to solve a multitude of similar examples.
Although there is no objection to having a classical computer help design a quantum circuit it is not legitimate for a compiler to know the answer to the problem being solved.
Of course there is nothing wrong to use a PC to design a quantum computer, but this should be a general purpose quantum computer to solve a range of composite numbers (with a certain size) correctly without any error and without any hardware modification in between . It does not make sense to design a Quantum Computer which only can solve the case: 3359*3697 = 12476071 (period=924)
As the case of RSA-768 suggest, very large numbers can be trivially factored if the 'compilation' depends on the answer found.
The word 'compilation' is misleading. A compiler is a word used in the software realm. A better word would be: specific hardware implementation. See Also Reflection part 3

Reflection part 1

Box 3 - Prescription

The text in Box 3 summarizes it all:
For example RSA 768 has been factored classically etc.
Here the length of the period found provides a good proxy for experimental difficulty but one ought to perform Shor's algorithm blindly, using random bases
The first part is correct, but not the second
The algorithm should be described as specific as possible with the quickest chance for success. Fermat's algorithm is slower for larger numbers compared to Shor's algorithm but it always gives the correct answer.
Similar experimental difficulties are also described in the document: Shor's Algorithm - 10 questions written 10 years ago.
A Quantum Computer is like an Analog Computer: When you want to modify your Application you have to modify the hardware. In fact you can not build one Quantum Computer to solve two different problems.
For a PC this is different. Each problem requires its own program. No hardware changes are required to switch between the two.

Reflection part 2

  1. Quantum computers are supposed to be fast, much faster than ordinary PC's. To test that Shor's algorithm is used. This algorithm calculates the two prime numbers p and q of the composite number N. In the case of p=29 and q=31 N=899.
    The central concept behind Shor's algorithm is the period p. When you have the period it is easy to calculate both p and q. The problem behind Shor's algorithm is that the Quantum Computer does not calculate the period p directly, but a smaller number p1 in such a way that p is a multiple of p1
    In the case of p=29 and q=31 the period is 420 and p1 could be for example 420, 210 and 42. The chance of getting 420 is 22% of 210 is 12% and of 140 11%
    In the case when p1= 210 you still have to perform two calculations: 21^210 Mod 899 and 21^420 Mod 899. Those calculations are called Modular Exponentiation. The result of the last calculation = 1. That means the period p = 420.
    In this particular case Modular Exponentiation involves a calculation which requires 9 loops. A different way to do factorization is not by using Shor's algorithm but by using Fermats Algorithm. Fermats Algorithm in this case requires 1 Loop, which outperforms Modular Exponentiation
    In the case when the prime numbers are roughly 100 and 200 both "algorithms" are approximately equal
    When both prime numbers are roughly 500 and 1000 Modular Exponentiation out performs Fermat's Algorithm. In that case if Shor's Algorithm also out performs Fermat's Algorithm is an open question because to do factorization using a Quantum Computer which executes Shor's Algorithm involves much more than only Modular Exponentiation.
    For more information about this issue read:
  2. digital PC's are build using the John Von Neumann architecture. The advantage of this architecture is when ever you execute the same program twice (based on certain constraints) using the same data, you always get the same results.
    For example if you use Sieve of Eratosthenes algorithm the result are always the same numbers.
    With a Quantum computer using Shor's algorithm this is not the case because the result (what is measured) depends on probabilities and does not always have to be the same (and could be wrong).
  3. If you consider table 1 in the nature article than all the present implementations are done on special purpose quantum computers solving special selected problems with only a very small number of qubits. The length of the tunnel to solve any implementation with both prime numbers larger than 100 is still very long.
What this means that IMO that the usefulness of Quantum computers is still very bleak.

Reflection part 3 - RSA-768

What the case of RSA-768 shows that it is presently possible to factorize large numbers in the order of 1*10^229 using a general-purpose classical algorithm. RSA-768 uses prime numbers in the order of 3*10^114. That means in reality you need prime numbers in the order of 10^130. The resulting composite number is easy to calculate but requires at present a Quantum Computer to solve in reasonable time. If you know the composite number and one of the prime numbers than the second prime number is also easy to calculate. This makes cryptography using two friendly parties save but also between two enemy parties.
To get an idea: If you know both the composite number "n" of roughly 10^230 and one prime number "pm1" of roughly 10^115 than it takes about 2 seconds to calculate the second prime number "pm2" by an from the shelf PC. This calculation involves a division pm2= n / pm1
The highests number on a standard PC is in the order of 10^308 after that the answer becomes infinity.
The article does not mention if this exercise is done on a general purpose PC or special purpose machine. For example Blue Gene supports 2048 CPU's. It is possible to calculate the period on such a computer (with the function: a^x Mod n, starting from x=1) on 2048 CPU's in parallel. The problem with this approach is that the more processors you have the larger numbers you can factorize using standard technology. This makes the usefulness of Quantum Computers again very bleak. The end of the tunnel becomes smaller.

See Also: Shor's Algorithm Reflection 5 - RSA-768.

Reflection part 4 - Factorization using Parallel Processing.

The document Quantum Factoring Performance Evaluation - Using Parallel Processing - VB2010 describes factorization using 4 CPU's in parallel. The largest number factorized is 1230186684560413680454744877 which is a combination of the two prime numbers 33478071699197 and 36746043667441. Execution time roughly 1 day and 3 hours.
Feedback received shows that execution time is roughly 3 seconds using the programming language Lisp (Maxima)

General performance increases linear with the length of the prime numbers involved. That means when the prime numbers are a factor 10 larger the performance also increases with a factor 10.
Using the Maxima package in order to factorize RSA-768 execution time is than roughly 10^100 seconds. This is extremely large.
This raises three issues:

Feedback

See Discussion in sci.math started 14 November 2013 Quantum Computers and Shor's algorithm 5 messages.

Created: 31 July 2013
Updated: 16 November 2013

Back to my home page Index
Back to Nature comments Nature Index