8
$\begingroup$

Since the original experimental contribution using the Shor's factoring algorithm to factorize the integer 15 some experiments have been performed in order to calculate the largest factorized number. But most of the experiments are particularly designed for a specific number ($N$) and not a general approach which could be used for any $<N$ integer. Example.

I am wondering which is, at the moment, the largest number that has been experimentally factorized in a general procedure by a quantum algorithm.

Improve this question
$\endgroup$
8
  • $\begingroup$ So, to be clear, you consider an approach 'general' if there is an integer $N$ such that all integers of size at most $N$ can be factored with the method, right? I think that asking for the largest such $N$ isn't a good idea, as that means answers to this question would be easily outdated. Therefore, I think it is better to ask whether there exists a general method with non-trivial $N$ (I'd say at least $6$ would do, as $4,6$ have a non-trivial factorisation ), as that answer wouldn't be invalidated by time and I think that answers part of your question. $\endgroup$
    – Discrete lizard
    Commented Apr 16, 2018 at 13:59
  • 1
    $\begingroup$ @Discretelizard: note that Shor's algorithm has a classical pre-processing step which filters out even numbers (required for technical reasons, but also notable for how easily one can find a factorisation). So in fact 15 is the smallest integer for which one can provide an interesting demonstration of Shor's algorithm. $\endgroup$
    – Niel de Beaudrap
    Commented Apr 16, 2018 at 16:10
  • $\begingroup$ @NieldeBeaudrap Ah, thanks for pointing that out. (although technically even numbers aren't nessecarily easy to factor (take 2*pq, p q large primes), merely easy to reduce to the odd case (pq)) Why do you skip $9$? Are squares considered trivial, or is there another reason? $\endgroup$
    – Discrete lizard
    Commented Apr 16, 2018 at 18:07
  • 1
    $\begingroup$ @DiscreteLizard: Good question about 9 as an input. However, for technical reasons, Shor's algorithm also requires that the input is not a prime power. This is easy to test (contradicting a certain plot point of the horror film Cube) by computing roots of the input and testing if any of those inputs are integers greater than 2. If so, one can use one's favourite deterministic or randomised primal it treat. (Of course, if the result is an integer but not prime, you've found a factorisation anyway.) At most logarithmically many such roots need be computed. So 9 is also 'trivial'. $\endgroup$
    – Niel de Beaudrap
    Commented Apr 16, 2018 at 18:48
  • 1
    $\begingroup$ @DiscreteLizard: Integer Factorisation is not the problem of finding a prime factorisation, but of finding a proper factorisation. If you can do the former then you can do the latter, but one of these problems is in some sense much easier than the other for almost all inputs (for a suitably carefully made definition of 'almost all'). $\endgroup$
    – Niel de Beaudrap
    Commented Apr 16, 2018 at 19:51

2 Answers 2

Reset to default
5
$\begingroup$

The answer is $N = 200\,099$.

Shor's algorithm is not the only way to factorize integers. In fact, it is also possible to factorize integers with an optimization approach. This approach even allows for integers with more than two prime-factors to be composed.

See this paper from D-Wave, Prime factorization using quantum annealing and computational algebraic geometry, in which the explain their approach and show the results of factoring multiple composite numbers, among which $N=200\,099$.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Actually, the D-Wave team released a paper just a few days ago, claiming to have been able to factorize $N=376289$. It can be found here arxiv.org/pdf/1804.02733v1.pdf $\endgroup$
    – Alex
    Commented Apr 17, 2018 at 18:58
  • $\begingroup$ Awesome! I didn't know this :) $\endgroup$
    – nippon
    Commented Apr 20, 2018 at 8:16
  • 1
    $\begingroup$ Between those, there was 291311: arxiv.org/abs/1706.08061 $\endgroup$
    – user1271772 No more free time
    Commented May 20, 2018 at 18:04
1
$\begingroup$

For Shor's algorthm: Every experiment has been designed for the specific number being factored. The largest number factored without cheating was 15 which is the smallest non-trivial semi-prime on which to apply Shor's algorithm. Major changes would be needed in the experiment (including in the number of qubits) in order to factor 21, for example. IBM's 50-qubit machine can implement Shor's algorithm on larger numbers, but the noise is so bad that you will only get the correct factors if you're very lucky, and that's why it hasn't been done yet.

For the annealing algorithm: 376289 has been factored with D-Wave's 2048-qubit annealer, and this is not a specific experiment but a general algorithm on an easily programmable machine, but we do not know how this will scale. A very crude upper limit to the number of qubits needed to factor RSA-230 is 5.5 billion qubits (but this can be brought down significantly by better compilers), while Shor's algorithm can do it with 381 qubits.

Improve this answer
$\endgroup$

Your Answer

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

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