6
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for the paper. Yes, you are right that the advantage on Variational Algorithm or others based on QUBO is not very significant, or at least we are currently not sure how big the advantage is. It seems that solving QUBO problems on gate-based quantum computer or quantum annealer is better only in constant and the complexity is still exponential. However, this is still under investigation. $\endgroup$ Oct 27, 2020 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.