If you put together China, Quantum, and Factoring encryption keys you end up with a tremendous amount of fuel for the quantum hype machine. There has been a lot of clamor recently in the popular press caused by a new paper posted on arXiv by 24 researchers in China titled Factoring integers with sublinear resources on a superconducting quantum processor. This paper proposed a new approach to using a quantum computer to factor a large 2048 bit semi-prime number that they said could be achieved on a NISQ level computer with 372 physical qubits with a gate depth in the thousands. If this were achievable it would be jeopardize the RSA-2048 encryption code widely used today for asymmetric encryption in today’s internet and make insecure the worldwide digital communications infrastructure. For comparison, the well-known Shor’s algorithm would require about 4,000 logical qubits created with error correction which would translate to roughly 20 million physical qubits and a gate depth in the billions because of the overhead involved with error correction.
The approach described in a paper we reported on last year that starts with a classical algorithm proposed by Dr. Claus Peter Schnoor that is based upon an approach using a Shortest Vector Problem (SVP) algorithm which uses lattice reduction to factor integers. The new development in the China paper is that they have coupled the use of Schnoor’s algorithm with a heuristic quantum optimization algorithm called QAOA (Quantum Approximate Optimization Algorithm) to speed up Schnoor’s algorithm so it could theoretically solve the problem much faster.
Several responses have been posted by quantum experts casting some doubts about this approach. The first was posted by Scott Aaronson in his blog where he states that QAOA “has not yet been convincingly argued to yield any speedup” with only one possible exception. He also points out that the paper itself mentions that “quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA.” Moody’s Analytics has posted a paper which points out the “Schnorr technique was not shown to properly scale”. Other comments include the fact it is not clear that the QAOA algorithm itself may not be able to scale well and that even using this technique, it would require a NISQ computer with gate level fidelities of 99.999%. That level is more than two orders of magnitude better than the best machines we have today. Just getting to the 99.999% level may still require some use of error correction. And finally, we should point out that QAOA is not guaranteed to produce that absolute best optimization to some problem. In some use cases even if it provides the second or third best answer it may be still be useful if it can provide a better or faster answer than classical. But in factoring this is not the case. The answer must be exact and second best won’t work.
Additional information can be found in the original paper located here, Scott Aaronson’s blog post here, and Moody Analytics post here.
January 5, 2023