22

Shor's algorithm is expected to enable us to factor integers far larger than could be feasibly done on modern classical computers.

At current, only smaller integers have been factored. For example, this paper discusses factorizing $15=5{\times}3$.

What is in this sense the state-of-art in research? Is there any recent paper in which it says some bigger numbers have been factorized?

Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112
Lying Dancer
  • 323
  • 2
  • 5

3 Answers3

16

The prime factorization of 21 (7x3) seems to be the largest done to date with Shor's algorithm; it was done in 2012 as detailed in this paper. It should be noted, however, that much larger numbers, such as 56,153 in 2014, have been factored using a minimization algorithm, as detailed here. For a convenient reference, see Table 5 of this paper:

$$ \begin{array}{c} \textbf{Table 5:}~\text{Quantum factorization records} \\ \hline \small{ \begin{array}{cccccc} \text{Number} & \text{# of factors} & \begin{array}{c}\text{# of qubits} \\ \text{needed} \end{array} & \text{Algorithm} & \begin{array}{c}\text{Year} \\ \text{implemented} \end{array} & \begin{array}{c}\text{Implemented} \\ \text{without prior} \\ \text{knowledge of} \\ \text{solution} \end{array} \\ \hline 15 & 2 & 8 & \text{Shor} & 2001~\left[2\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2009~\left[5\right] & \chi \\ & 2 & 8 & \text{Shor} & 2012~\left[6\right] & \chi \\ 21 & 2 & 10 & \text{Shor} & 2012~\left[7\right] & \chi \\ 143 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ 56153 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ \hline 291311 & 2 & 6 & \text{minimization} & \text{not yet} & \checkmark \\ 175 & 3 & 3 & \text{minimization} & \text{not yet} & \checkmark \end{array}} \end{array}_{\Large{.}} $$

auden
  • 3,489
  • 1
  • 21
  • 50
6

The size of the number factored is not a good measure for the complexity of the factorization problem, and correspondingly the power of a quantum algorithm. The relevant measure should rather be the periodicity of the resulting function which appears in the algorithm.

This is discussed in J. Smolin, G. Smith, A. Vargo: Pretending to factor large numbers on a quantum computer, Nature 499, 163-165 (2013). In particular, the authors also give an example of a number with 20000 binary digits which can be factored with a two-qubit quantum computer, with exactly the same implementation that had been used previously to factor other numbers.

It should be noted that the "manual simplifications" which the authors perform to arrive at this quantum algorithm is something which has also been done e.g. for the original experiment factoring 15.

Norbert Schuch
  • 8,142
  • 1
  • 19
  • 30
5

For Shor's algorthm: State of the art is still 15. In order to "factor" 21 in the paper Heather mentions, they had to use the fact that $21=7\times 3$ to choose their base $a$. This was explained in 2013 in the paper Pretending to factor numbers on a quantum computer, later published by Nature with a slightly friendlier title. The quantum computer did not factor 21, but it verified that the factors 7 and 3 are indeed correct.

For the annealing algorithm: State of the art is 376289. 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.