Chinese quantum team will crack RSA
In a recent study [1], researchers at Tsinghua University and others have created an algorithm that achieves 48-bit factorization using only 10 superconducting quantum bits, and say that a quantum circuit with 372 physical quantum bits and thousands of depths could challenge the RSA-2048 cipher, a mainstream cipher used by humans to keep information secure.
Peter Shor retweeted a tweet saying that there are apparently possible problems with this paper. Shor was the first person to suggest that quantum computers could be used to break RSA, and he invented the quantum algorithm known as Shor's algorithm.
The original tweet was posted by Craig Gidney, a quantum software engineer at Google, who said that the paper did go to great lengths, but did not mention the expected number of circuit executions it would require. It's crucial to the whole premise of the paper to have a small limit on that number, and as far as I know, they don't talk about it. Very bad.
Scott Aaronson, winner of the 2020 ACM Award for Computing and author of the theory of the superiority of bosonic sampling and quantum computing, criticized the paper even more vociferously.
Aaronson published his opinion on his personal blog [2] under the title "Cargo Cult Quantum Factoring". The following is a paraphrase of his article.
If experience has taught me anything, it is that the quantum hype train never slows down.
In the last 24 hours, at least four people have emailed me about a new paper entitled "Decomposing Integers Using Sublinear Resources on Superconducting Quantum Processors", including security expert Bruce Schneier.
The paper claims that ...... has made decisive progress in how to decompose large integers to break the RSA cryptosystem using recent quantum computers. Note that not by using Shor's algorithm, but by using the deceptively similarly named Schnorr's algorithm, a classical lattice based algorithm that was subsequently "enhanced" by the authors using a heuristic quantum optimization method called QAOA.
For those of you who don't want to read further, I'll just say: no means no.
Here is my slightly longer comment.
Schnorr ≠ Shor. Even though Schnorr's algorithm is dubiously "enhanced" using QAOA - which is a quantum algorithm - incredibly, despite hundreds of papers on it, there is no convincing reason that it can produce any speedup for any problem (except for the problem of replicating its own error patterns).
In this new paper, the authors spend page after page saying, without hesitation, that using a NISQ (i.e., non-fault-tolerant) quantum computer will likely be able to crack RSA-2048 soon. they do so through two time-tested strategies.
Exploration of irrelevant details (mainly optimizing the number of quantum bits while ignoring the number of gates), and silence on a key point.
Finally, they make a key point clear in a sentence in the conclusion section.
It is important to note that the quantum acceleration ratio of the algorithm is not known due to the uncertainty of the convergence of QAOA.
The word "unclear" here is a huge understatement. In my opinion, it would take a miracle for the approach in this paper to yield any benefit over the classical Schnorr algorithm that can be run on a laptop. If the latter could crack RSA, it would have done so already.
All in all, this is one of the most misleading quantum computing papers I have seen in 25 years. That said, this is not the first time I have encountered the strange idea that what we know about integer decomposition exponential quantum acceleration from Shor's algorithm should somehow "rub off" on quantum optimization heuristics that do not reflect the actual insights of Shor's algorithm. Since this idea needs a name, I propose here Cargo Cult Quantum Factoring.
[1]https://arxiv.org/abs/2212.12372
[2]https://scottaaronson.blog/?p=6957#comments
