17
$\begingroup$

I'm studying Shor's quantum factoring algorithm. I was wondering what the largest integer is which they were able to factor with a small quantum computer. Does anybody has an idea about this?

$\endgroup$
  • 1
    $\begingroup$ See here. (not enough reputation to add as a comment) $\endgroup$ – Lying Dancer Jun 5 '18 at 9:07
  • $\begingroup$ Just a heads up: there are more ways to factor with a quantum computer than Shor's, you might want to extend your question to ask both "the largest integer factored with Shor's" and "the largest integer factored". $\endgroup$ – Ruben De Smet Jun 5 '18 at 9:48
26
$\begingroup$

wondering what the largest integer is which they were able to factor with a small quantum computer

Stunts

Before the present answer, the largest claim for quantum-related factoring seems to have been 4088459=2017×2027, by Avinash Dash, Deepankar Sarmah, Bikash K. Behera, and Prasanta K. Panigrahi, in [DSBP2018] Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer (arXiv:1805.10478, 26 May 2018) using 2 qubits (per their measure) of IBM quantum processors with 5-qubit and 16-qubit.

That's a pure stunt without application to cryptography, brought to a higher degree than in earlier work of Nikesh S. Dattani and Nathaniel Bryans, Quantum factorization of 56153 with only 4 qubits (arXiv:1411.6758, 2014) "factoring" e.g. 56153=233×241. The method applies only to a very narrow class of integers (those product of integers differing only by 2 bits, perhaps with some other constraints). 4088459 and 56153 are determined to fit the method.

The above "factorizations" extend, without requiring any experimental improvement, the earlier record of 143=11×13 by Nanyang Xu, Jing Zhu, Dawei Lu, Xianyi Zhou, Xinhua Peng, and Jiangfeng Du in Quantum Factorization of 143 on a Dipolar-Coupling Nuclear Magnetic Resonance System (Physical Review Letters, 2012). Their technique factors an integer product of two odd exactly-4-bit integers (thus with two unknown bits per factor). The scarcity of primes in range [8,15] makes 143 the only product of two distinct primes that the technique can factor. Their experimental setup iteratively minimizes a function with a 2-bit input.

An experimental improvement to 3-bit input, with application to 551=19×29, is claimed by Soham Pal, Saranyo Moitra, V. S. Anjusha, Anil Kumar, and T. S. Mahesh's Hybrid scheme for factorization: Factoring 551 using a 3-qubit NMR quantum adiabatic processor (arXiv:1611.00998, 2016). The authors acknowledge that the technique probably can't factor some larger 10-bit integers.

Breaking news: I hereby claim a new stunt record. I change the last line of equation (2) in [DSBP2018] from $p_i=q_i=1;i\in\{5,6,7,8,9\}$ to $p_i=q_i=1;i\in\{5,6,\dots,87\}$, and the very same quantum experiment yields the factorization of the 178-bit biprime 383123885216472214589586724601136274484797633168671371=618970019642690137449562081×618970019642690137449562091, or otherwise said that $2^{178}-(13\times2^{91})+651=(2^{89}-21)\times(2^{89}-31)$.


Adiabatic quantum computing records

For something non-stunt, as in aiming to factor a wide fraction of arbitrary composites up to some limit, the record may be Raouf Dridi and Hedayat Alghassi's Prime factorization using quantum annealing and computational algebraic geometry (in Nature scientific reports, 2017) factoring up to 223357=401×557 using the D-Wave 2000Q (an adiabatic quantum computer). The debate is still raging about the size of the true quantum computer that it could emulate.

Shuxian Jiang, Keith A. Britt, Travis S. Humble, and Sabre Kais in Quantum Annealing for Prime Factorization (arXiv:1804.02733, 8 Apr 2018) "present how to factorize" 376289=571×659, but I was pointed that it is not an experimental result, sorry for being careless and formerly reporting that as a non-stunt record.


CAUTION: None of the above techniques implement Shor's algorithm. They express factorization as a combinatorial minimization problem, solved using a variant of Grover's algorithm or adiabatic quantum computing. I have not seen much argumented hope that these approaches could scale to factorization of integers of cryptographic interest.


Shor's algorithm on quantum computers

We must separately consider the title's question:

Largest integer factored by Shor's algorithm?

I'm not aware of anything above 21=3×7 claimed by Enrique Martin-Lopez, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou, and Jeremy L. O'Brien in Experimental realisation of Shor's quantum factoring algorithm using qubit recycling (Nature Photonics, 2012).

This beats 15=3×5 first obtained by Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood and Isaac L. Chuang in Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance (Nature, 2001), then several others.

However it is debatable if these are really factoring, or rather confirming a known factorization. John A. Smolin, Graeme Smith and Alexander Vargo in Oversimplifying quantum factoring (Nature, 2013, formerly arXiv:1301.7007 with a different title) go as far as:

(there is) danger in ‘compiled’ demonstrations of Shor's algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice.

| improve this answer | |
$\endgroup$
  • $\begingroup$ How do you conclude factoring by Hamiltonian optimization is a variant of Grover's algorithm? And why is the factorization of 4088459 any more or less of a stunt than factorization of 143 by essentially the same method? $\endgroup$ – Squeamish Ossifrage Jun 5 '18 at 13:15
  • $\begingroup$ @SqueamishOssifrage: First, I confess I'm far out of my comfort zone. I base my "variant of Grover's algorithm" on "our work makes use of the generalized Grover’s algorithm" in the abstract for the first paper I cite, and my understanding that in the first two papers factorization is essentially finding unknown bits (like 4 or so) that solve a combinatorial problem, which is similar to what Grover’s algorithm does. I base my "stunt" on the small number of bits involved in this minimization, which restricts to special-form integers. $\endgroup$ – fgrieu Jun 5 '18 at 13:24
  • 1
    $\begingroup$ The classical reduction step depends on the form of the integer only to make it realizable in a prescribed concrete number of qubits, but the asymptotic growth is still polylogarithmic in $n$. The form of the integer may seem to be relevant in some cases because the relations obtained by reducing the binary multiplication are common to multiple integers with different solutions for the bits of the factors. The open question is how the quantum annealing step grows in cost with the number of bits. $\endgroup$ – Squeamish Ossifrage Jun 5 '18 at 13:33
  • 1
    $\begingroup$ All of this is to say: The simplifications done classically (reducing the relations between bits of factors and product), compiling a fixed bases to quantum circuits) were needed to fit the computation into numbers of qubits we have available now. They are not necessary if it is possible to scale up the quantum circuits or quantum annealers to thousands of qubits. The limit is in the number of qubits, not the factoring or period-finding method. Will the superpolynomial costs of classical factoring or discrete log algorithms correspond to superpolynomial costs in scaling to many qubits? Maybe! $\endgroup$ – Squeamish Ossifrage Jun 5 '18 at 13:57
  • 1
    $\begingroup$ @fgrieu 376289 was not actually factored in the first "non-stunt" paper you mention. They said in the abstract that they "show how to do it" which is misleading in my opinion because they actually "show how to" factor even RSA-4096 strictly speaking. At the end of the paper, they said that they were unable to factor 376289 because there was not enough qubits on the D-Wave machine. The record is still under 300000 in my opinion. $\endgroup$ – user1271772 May 10 at 18:18
4
$\begingroup$

According to L. Zyga et al, N. Dattani and N. Bryans factored $56\,153 = 233 \cdot 241$ in November 2014, using a 4-qubit minimization (adiabatic quantum computation?) algorithm. Researchers believe that the method could be extended to factor $291\,311$. As of that time, the largest factorization achieved by Shor's algorithm was $21 = 3 \cdot 7$, and even that relied on prior knowledge of the answer.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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