  Quantum computing has the potential to revolutionize cryptography by breaking
classical public-key cryptography schemes, such as RSA and Diffie-Hellman.
However, breaking the widely used 2048-bit RSA using Shor's quantum factoring
algorithm is expected to require millions of noisy physical qubits and is well
beyond the capabilities of present day quantum computers. A recent proposal by
Yan et. al. tries to improve the widely debated Schnorr's lattice-based integer
factorization algorithm using a quantum optimizer (QAOA), and further claim
that one can break RSA 2048 using only 372 qubits. In this work, we present an
open-source implementation of the algorithm proposed by Yan et. al. and show
that, even if we had a perfect quantum optimizer (instead of a heuristic like
QAOA), the proposed claims don't hold true. Specifically, our implementation
shows that the claimed sublinear lattice dimension for the Hybrid
quantum+classical version of Schnorr's algorithm successfully factors integers
only up to 70 bits and fails to find enough factoring relations for random 80
bit integers and beyond. We further hope that our implementation serves as a
playground for the community to easily test other hybrid quantum + classical
integer factorization algorithm ideas using lattice based reductions.

Quantum Physics