In a technical paper titled Factoring larger integers with fewer qubits via quantum annealing with optimized parameters, Chinese scientists have disclosed they have successfully factored the number 1005973 into its two semi-prime numbers 997 and 1009. The factoring was performed on a D-Wave 2000Q quantum annealing machine and required 89 qubits. This is roughly a 20 binary bit number and surpasses the previous quantum factoring record of 376289 (about 19 binary bits) also performed on a D-Wave 2000Q. For comparison, the largest number that has been successful factored with a classical computer is RSA-768 (768 binary bits) which took two years using a large collection of parallel computers and totaled almost 2000 years of computing time.
Although factoring a 20 binary bit number using 89 qubits is still a long way off from the 2048 bit binary numbers used in the RSA code, if we hypothesize that the problem will scale linearly (which may or may not be correct), it would indicate that RSA-2048 might be factorable with a 10000 qubit quantum annealing machine. Although D-Wave’s next generation machine will only support a maximum of 5640 qubits, it may be possible to hit this level in a few generations after that.
We had previously reported that Zapata is also working on an alternative to Shor’s algorithm using an approach they called Variational Quantum Factoring. So it will be worth watching the progress of these two alternative approaches to see if they can ultimately surpass Shor’s algorithm as well as classical computers for factoring very large numbers.
For more information, you can view a preview of the article as published in Science China Physics, Mechanics & Astronomy here. There is a paywall to view the full article.