35
$\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 have an idea about this?

$\endgroup$
2
  • 1
    $\begingroup$ See here. (not enough reputation to add as a comment) $\endgroup$ Jun 5, 2018 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$ Jun 5, 2018 at 9:48

2 Answers 2

53
$\begingroup$

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

This answer starts with stunt records. See final paragraph for the the largest meaningful record. None of these use Shor's algorithm, part of the question's title.


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 of qubit, which influences what integers can be 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). However they still use 3 qubits, and I think it's more some pre-screening of the integer factored, rather than change in molecule (which seems aimed at improving experimental accuracy), that explains the larger value.

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

Any of the stunt factorizations above can be obtained¹ using the first step of Fermat's method: let $n$ be the integer to factor; let $u=\left\lceil\sqrt n\,\right\rceil$ ; if $v=\sqrt{u^2-n}$ is an integer, then $u-v$ and $u+v$ are factors of $n$. Try It Online (in Python)!


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² up to late 2022 may have been 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?

No numbers have been factored using Shor's original algorithm.

Since 2001, various authors have published papers claiming to factor 15, and then 21 using Shor's algorithm on quantum hardware, but it was later discovered that they were using a specific base $a$ such that fewer qubits would be needed. In order to know this value of $a$, you would need to know the factors (i.e. you would need to know that 21 = 7 x 3). Without knowing the factors in advance, you would need to check all values of $a$, which for factoring 15 with Shor's original algorithm, would require 8 qubits, yet the largest that was ever used was 7.

It turns out that if you know the factors in advance, you can factor any number with a small number of qubits, and the paper "Pretending to factor large numbers on a quantum computer" demonstrates "Shor's algorithm" factoring RSA-768 with only 2 qubits, and also a 20,000 digit number with only 2 qubits (see Table 1 on Page 4). The paper explains that all implementations of Shor's algorithm to date were done using knowledge of the prime factors (something you can't do in real life if you want to factor an RSA number whose factors are unknown).

The paper ended up getting published in Nature with the title Oversimplifying quantum factoring (2013) by John A. Smolin, Graeme Smith and Alexander Vargo.


Minor update (Sep. 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 Schor'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).


Update (Jan. 2023): new record; new hope?

A new approach to factoring using quantum computers has recently been proposed: Bao Yan, Ziqi Tan, Shijie Wei, Haocong Jiang, Weilong Wang, Hong Wang, Lan Luo, Qianheng Duan, Yiting Liu, Wenhao Shi, Yangyang Fei, Xiangdong Meng, Yu Han, Zheng Shan, Jiachen Chen, Xuhao Zhu, Chuanyu Zhang, Feitong Jin, Hekang Li, Chao Song, Zhen Wang, Zhi Ma, H. Wang, Gui-Lu Long, Factoring integers with sublinear resources on a superconducting quantum processor (arXiv.2212.12372). They report factoring any 48-bit integer, including experimentally factoring 261980999226229=15538213×16860433 with help of a 10-bit quantum computer, by an algorithm which required number of qbits is nearly linear (even slightly sub-linear) with the bit size of the integer factored. They perform on a quantum computer the hard part (a Short Vector Problem) of some known factorization method. The approach is discussed here.


¹ Any factorization method limited to $n$ that one step of Fermat tackles is pointless from a cryptographic standpoint. The converse is not true.

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

$\endgroup$
7
  • $\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$ Jun 5, 2018 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, 2018 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$ Jun 5, 2018 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$ Jun 5, 2018 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$ May 10, 2020 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.

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