19
$\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
31
$\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, 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. The number factored depends on the molecule (dibromofluoromethane) used.

Zhaokai Li, Nikesh S. Dattani, Xi Chen, Xiaomei Liu, Hengyan Wang, Richard Tanburn, Hongwei Chen, Xinhua Peng, Jiangfeng Du's High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spinsystem: Application to the experimental factorization of 291311(arXiv:1706.08061, 2017) tackle 291311=523×557 using a different molecule ($^3C$-labeled diethyl-fluoromalonate).

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, defined as 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). A year later, the debate was still raging about the size of the true quantum computer that it could emulate.


CAUTION - All the above is practically pointless!

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. There is no argument for 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.


Update (Sept 2020)

More stunts factorizations have appeared (see my critic), but the one in this answer remains the true (if under-reported) champion in this dubious category.

The progress on experimental non-stunt implementations seems to have stopped, both for combinatorial approaches using quantum adiabatic computers² and Schoor's algorithm. We do better understand the limitations of current hardware: Mirko Amico, Zain H. Salee, and Muir Kumph's Experimental study of Shor’s factoring algorithm using the IBM Q Experience (in physical review A, July 2019) conclude their work "fails to factor N=35". Experimental quantum computing currently prefers to focus not on beating classical computers at existing problems, but rather on finding problems where that happens beyond simulation of quantum computers.

An interesting new line of work makes mental experiments in factorization on hypothetical quantum computers: see Craig Gidney, Martin Ekerå's How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (arXiv:1905.09749, Dec 2019).


¹ Shuxian Jiang, Keith A. Britt, Travis S. Humble, and Sabre Kais in Quantum Annealing for Prime Factorization (arXiv:1804.02733, 2018) "present how to factorize" 376289=571×659, but I was pointed that it is not an experimental result, sorry for having been careless.

² A close call was Baonan Wang, Feng Hu, Haonan Yao and Chao Wang's Prime factorization algorithm based on parameter optimization of Ising model (Scientic letter, April 2020) which claims a new combinatorial method factoring all integers to 10000, and in the stunt category 1028171=1009×1019, but got eliminated from both lists because that's on a simulation of a D-Wave quantum computer.

| 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.