13
$\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
24
$\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 claim seems to be up to 376289=571×659 by Shuxian Jiang, Keith A. Britt, Travis S. Humble, and Sabre Kais in Quantum Annealing for Prime Factorization (arXiv:1804.02733, 8 Apr 2018), 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.

This extends 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 with similar hardware.


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.

$\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
  • $\begingroup$ In particular, there are two parts to the optimization-based factoring approach: 1. Classically, write out the relations between the bits in the input and output of a multiplication table, and reduce them knowing the product but not the factors, to make it fit in the number of qubits available. 2. Quantumly, optimize the Hamiltonian obtained by expanding $(pq - n)^2$ thus. Note that the number of qubits required is $O(\log^2 n)$ or $O(\log n)$ depending on the type of annealing machine, with or without the classical reduction step. $\endgroup$ – Squeamish Ossifrage Jun 5 '18 at 13:27
  • 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
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.

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