7

With reference to a similar question here, I would like to know what is the maximal number which has been factored with Shor's algorithm so far on actual quantum hardware.

The reason I am asking a similar question as the link is that this question is from 2018 and I would expect that some progress has taken place since that time, especially in light of introducing a 65 qubits processor by IBM.

I also saw some other techniques for factoring integers to primes but these are based on converting the factorization problem to QUBO instead of period finding as in the case of Shor's algorithm:

These algorithms are able to factor integers in an order of ten or a hundred thousand but according to my knowledge, Shor's algorithm has been demonstrated on very simple cases like factoring 15, 21, and 35.

I also found adapted Shor's algorithm described in An Experimental Study of Shor's Factoring Algorithm on IBM Q, which should provide better performance on processors with a limited (small) number of qubits. However, again only numbers 15, 21, and 35 were factored in.

I would appreciate it if anyone can me provide a link to the paper(s) discussing progress in Shor's algorithm implementation.

R1-
  • 209
  • 4
  • 10
Martin Vesely
  • 15,244
  • 4
  • 32
  • 75

2 Answers2

5

None of the current implementations of Shor’s algorithm could actually be said to factor. These implementations used information about the factorization to factor (i.e, a known element of small order). Here’s a paper that explains and expands the ‘compiled’ version of Shor’s algorithm.

Anna Johnston
  • 51
  • 1
  • 1
4

For what it is worth, here is a paper by Craig Gidney on how to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Hopefully others will be able to add more related papers.

Correct me if I am wrong but I don't think those other algorithms like the Variational Quantum Factoring actually offers any advantage over classical algorithms.

KAJ226
  • 14,182
  • 2
  • 12
  • 34