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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Martin Vesely
    Oct 27, 2020 at 8:15
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ A couple years after the paper that you mentioned, 15 was factored again and this time without prior knowledge of the factor, but they used a semi-classical QFT which requires long coherence times. $\endgroup$
    – user1271772
    Jun 13 at 10:19
  • $\begingroup$ Could you please reference that paper. I think there must be some confusion as, according to a 2021 paper, in the ‘Compiled Shor’s algorithm’ section, it would take ‘9000 elementary quantum gates acting on 26 qubits’. Compiled versions of Shor’s algorithm take advantage of known order(s) — which is essentially knowledge of the factors. $\endgroup$
    – Anna Johnston
    Jun 14 at 19:22
  • $\begingroup$ Anna, you can look at my SE network profile, then look at the highest voted question that I asked on Theoretical Computer Science SE. If you're going to upvote Peter Shor's answer, please do not do it blindly just because it's by Shor. Some people told me that they did that and can't change their vote now even though they want to. What's swept under the rug in the paper and Shor's answer is that coherence times will have to be much longer, to implement Shor's algorithm in the way that they did. However they didn't assume knowledge of the factors. I'm on a phone so can't send you the paper. $\endgroup$
    – user1271772
    Jun 15 at 1:07
  • $\begingroup$ user1271772: If you can type that much on your phone, you can copy and paste a link to a paper. Compiled versions of Shor’s algorithm use fixed elements with known, very small orders - most commonly order 2 where the element is not -1 modulo N. This is, with a little elementary number theory, pre-knowledge of the factors. $\endgroup$
    – Anna Johnston
    Jun 15 at 20:04
  • $\begingroup$ You do not get to decide what people do here. $\endgroup$
    – user1271772
    Jun 16 at 18:22

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.