The conclusion is essentially the same. But, this update (compared to the March version), has reproduced more of the Dec. 2022 Schnorr+QAOA individual steps. The updated version says, “In this way, given that the QAOA provides a number of bottom eigen values of Hˆc, we verified and sr-pairs indeed can be obtained.” The March version suggested performance was closer to a random walk.

Figure 1c shows at least one very clear outlier run for ” Convergence of mean energy E to the minimal energy Emin” for use of 14 qubits to factor the 15 decimal digit number. It’s interesting there is no specific comment on that run, because IF true, that would suggest something potentially significant.

]]>Pitfalls of the sublinear QAOA-based factorization algorithm

https://arxiv.org/abs/2303.04656

Preprint, Wed, 8 Mar 2023 15:23:50 UTC

Several in-depth aspects including Schnorr’s algorithm.

Best regards

]]>https://arxiv.org/pdf/2303.04656.pdf ]]>

Very interesting recent preprint:

Computing 256-bit Elliptic Curve Logarithm in 9 Hours with 126133 Cat Qubits

https://arxiv.org/abs/2302.06639

Especially the end of the main part of this long preprint (39 pages):

extrapolation of their method for RSA-2048:

(…) we estimated that the implementation of Shor’s algorithm for the factorization of

2048-RSA integers would take 349 133 cat qubits and 4 days.

(…)

Thanks in advance for your impression on their specific implementation of Shor’s algorithm.

Best regards.

And as far as I can tell, there’s nothing really wrong with the classical version of Schnorr’s algorithm; it’s a good idea, it just doesn’t happen to run as fast as the Quadratic Sieve and the Number Field Sieve in practice.

]]>Wikipedia notes QS is fastest up to about 100 decimal digit numbers (~320 bits). IF that could be shown, the next place to look is evidence that the speed up continues scaling as numbers to factor grow even larger and also meaningfully faster than GNFS.

]]>