Prime factorization algorithm based on parameter optimization of Ising model

https://www.nature.com/articles/s41598-020-62802-5 Prime factorization algorithm based on parameter optimization of Ising model - [Baonan Wang](https://www.nature.com/articles/s41598-020-62802-5#auth-1), - [Feng Hu](https://www.nature.com/articles/s41598-020-62802-5#auth-2), - [Haonan Yao](https://www.nature.com/articles/s41598-020-62802-5#auth-3) &Chao Wang [Published: 28 April 2020](https://www.nature.com/articles/s41598-020-62802-5#article-info) Abstract This paper provides a new (second) way, which is completely different from Shor’s algorithm, to show the optimistic potential of a D-Wave quantum computer for deciphering RSA and successfully factoring all integers within 10000. Our method significantly reduced the local field coefficient and coupling term coefficient by more than 33% and 26%, respectively, of those of Ising model, which can further improve the stability of qubit chains and improve the upper bound of integer factorization. In addition, our results obtained the best index (20-bit integer (1028171)) of quantum computing for deciphering RSA via the quantum computing software environment provided by D-Wave. Furthermore, Shor’s algorithm requires approximately 40 qubits to factor the integer 1028171, which is far beyond the capacity of universal quantum computers. Thus, post quantum cryptography should further consider the potential of the D-Wave quantum computer for deciphering the RSA cryptosystem in future. Introduction The majority of scholars think that Shor’s algorithm is a unique and powerful quantum algorithm for the cryptanalysis of RSA. Therefore, the current state of the post quantum cryptography (constructing post quantum public key cryptosystems that would be secure against quantum computers) research has exclusively studied the potential threats to Shor’s algorithm. The security of the RSA cryptography system is based on the high complexity and security of the integer factorization problem. Shor’s algorithm[1](https://www.nature.com/articles/s41598-020-62802-5#ref-CR1) can attack the RSA cryptosystem in polynomial time. There have been many simulations about quantum computers[2](https://www.nature.com/articles/s41598-020-62802-5#ref-CR2) and attempts to implement Shor’s algorithm on quantum computing hardware[3](https://www.nature.com/articles/s41598-020-62802-5#ref-CR3),[4](https://www.nature.com/articles/s41598-020-62802-5#ref-CR4),[5](https://www.nature.com/articles/s41598-020-62802-5#ref-CR5),[6](https://www.nature.com/articles/s41598-020-62802-5#ref-CR6),[7](https://www.nature.com/articles/s41598-020-62802-5#ref-CR7). Researchers have developed classic emulators based on reconfigurable technology, enabling efficient simulation of various quantum algorithms and circuits, and they have the potential to simulate number of quits than software based simulators[2](https://www.nature.com/articles/s41598-020-62802-5#ref-CR2). Nuclear Magnetic Resonance (NMR) is the technology that we have for the implementation of small quantum computers. Vandersypen et al.[8](https://www.nature.com/articles/s41598-020-62802-5#ref-CR8) and Lu et al.[9](https://www.nature.com/articles/s41598-020-62802-5#ref-CR9) applied Shor’s algorithm to factor the integer 15 via NMR and an optical quantum computer, respectively. Enrique et al. implemented a scalable version of Shor’s algorithm via the iterative approach to factor 21[10](https://www.nature.com/articles/s41598-020-62802-5#ref-CR10). Based on the characteristics of the Fermat number[11](https://www.nature.com/articles/s41598-020-62802-5#ref-CR11), Geller et al. used 8 qubits to successfully factor 51 and 85. The real physical realizations of Shor’s algorithm cannot breakthrough the scale of factorization beyond 100 for the moment, as shown by principle-of-proof simulations and experiments[12](https://www.nature.com/articles/s41598-020-62802-5#ref-CR12). Actually, the number of qubits for performing Shor’s algorithm to factor an n-bit integer still remains approximately 2n qubits[13](https://www.nature.com/articles/s41598-020-62802-5#ref-CR13). Shor’s algorithm requires not only a large number of qubits but also a general-purpose quantum computer with high precision. Achieving practical quantum applications will take longer, perhaps much longer, as said by John Martinis, the physicist who leads Google’s efforts[14](https://www.nature.com/articles/s41598-020-62802-5#ref-CR14), and Science[15](https://www.nature.com/articles/s41598-020-62802-5#ref-CR15) commented that it will be years before code-cracking is achieved. Matthias Troyer said that “code-cracking and searching databases, are not good enough”[16](https://www.nature.com/articles/s41598-020-62802-5#ref-CR16). The newest report by the National Academies of Sciences, “Quantum Computing: Progress and Prospects”, stated that the current state of quantum computing and progress is highly unlikely to be able to attack RSA 2048 within the next decade. Therefore, in the case where Shor’s algorithm cannot be practically applied, it is of great importance to find a more generalized and scalable way with the potential for practical attacks on integers while using fewer quantum resources. The quantum adiabatic theorem was first introduced in 2001 by Burges[17](https://www.nature.com/articles/s41598-020-62802-5#ref-CR17). The main idea is to construct the corresponding Hamiltonian based on the multiplication table[18](https://www.nature.com/articles/s41598-020-62802-5#ref-CR18),[19](https://www.nature.com/articles/s41598-020-62802-5#ref-CR19),[20](https://www.nature.com/articles/s41598-020-62802-5#ref-CR20). Xu, N. et al. realized an experimental realization of factoring 143 via an NMR quantum processor[18](https://www.nature.com/articles/s41598-020-62802-5#ref-CR18). By further employing the properties of some class of large integers, Dattani et al. factored the integer 56153 with only 4 qubits[19](https://www.nature.com/articles/s41598-020-62802-5#ref-CR19) and Li et al. factored 291311 with 3 qubits by combining the theoretical reductions and Hamiltonian transformation[20](https://www.nature.com/articles/s41598-020-62802-5#ref-CR20). However, these methods are only available for integers with special properties and cannot be generalized to large integers, which can merely be seen as a principle-of-proof experiment. In adiabatic quantum computation, some researchers[21](https://www.nature.com/articles/s41598-020-62802-5#ref-CR21),[22](https://www.nature.com/articles/s41598-020-62802-5#ref-CR22) realize the reduction of multiple terms to quadratic terms without introducing auxiliary qubits, but too many restrictions increase the complexity of the model. Thus, it is of great importance to find a more generalized way to conduct prime factorization. D-Wave quantum computer is based on the quantum annealing principle. It has been widely used in sampling, optimization, machine learning, etc.[23](https://www.nature.com/articles/s41598-020-62802-5#ref-CR23),[24](https://www.nature.com/articles/s41598-020-62802-5#ref-CR24),[25](https://www.nature.com/articles/s41598-020-62802-5#ref-CR25),[26](https://www.nature.com/articles/s41598-020-62802-5#ref-CR26),[27](https://www.nature.com/articles/s41598-020-62802-5#ref-CR27),[28](https://www.nature.com/articles/s41598-020-62802-5#ref-CR28),[29](https://www.nature.com/articles/s41598-020-62802-5#ref-CR29). Raouf Dridi et al.[27](https://www.nature.com/articles/s41598-020-62802-5#ref-CR27) applied the computational algebraic geometry to transform the factorization problem to the QUBO model to be solved by the cell algorithm and the column algorithm respectively. The experiments via the D-Wave 2X show that dividing the columns to construct the Hamiltonian that is to be solved via quantum annealing can factor the integer 200099. Jiang et al.[30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30) constructed a general model to factor the integer 376289 with 94 logical qubits via a D-Wave 2000Q System. However, it is still limited by the hardware restrictions of the quantum machine[31](https://www.nature.com/articles/s41598-020-62802-5#ref-CR31). Peng et al.[32](https://www.nature.com/articles/s41598-020-62802-5#ref-CR32) further promoted Jiang et al.’s work by reducing the number of qubits according to the constraints of the target values and the number of carrying numbers involved in the multiplication table. XinMei Wang[33](https://www.nature.com/articles/s41598-020-62802-5#ref-CR33) commented that Peng et al.[32](https://www.nature.com/articles/s41598-020-62802-5#ref-CR32) supported the optimistic potential of a D-Wave quantum computer for deciphering the RSA cryptosystem in the future. In 2019, Lockheed Martin’s Warren, R.H.[34](https://www.nature.com/articles/s41598-020-62802-5#ref-CR34) proposed a chain factorization algorithm to factor all integers within 1000 by setting the upper limit of the factorability. However, this model uses more logical qubits, which means there is qubit redundancy. In this work, we put forward a new independent model for prime factorization with few qubits to be solved by QA, and it successfully factors 1028171 via 88 qubits with the qbsolv software environment (the quantum computing software environment provided by D-Wave). This is superior to the results obtained by any other quantum algorithm, including Shor’s algorithm (factor up to 85) via different platforms (like the Hua-Wei quantum computing platform), quantum adiabatic computation via NMR (291311), and quantum annealing via the D-Wave platform (376289). Compared with ref. [30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30), in this paper, the local field coefficient h and coupling term coefficientJ of Ising model are optimized to reduce the range of the model parameters, which reduces the coupling strength between qubits, further improves the stability of qubit chains and further improves the upper bound of the integer factorization. Our method has obtained the best index (20-bit integers (1028171)) of quantum computing for deciphering RSA, and it also exceeded the theoretical maximum (10-bit integers) of the IBM Q System OneTM with Shor’s algorithm, the work of Shuxian Jianget al. (376289), and the maximum scale (7781) of Lockheed Martin’s Warren, R.H. It supports the optimistic potential of the quantum annealing algorithm and D-Wave quantum computer for deciphering the RSA cryptosystem in the future. The D-Wave provides a new (second) way, which is a completely different way than Shor’s algorithm, and may be closer to cracking practical RSA codes than a general-purpose quantum computer using Shor’s algorithm. The rest of this paper is organized as follows. First, we describe the basic ideas of quantum annealing and the multiplication table for factorization. Second, we compare the methods and results with those of Shor’s algorithm, NMR, and integer factorization by a D-Wave. Third, we illustrate the optimistic potential of the quantum annealing algorithm and D-Wave quantum computer for deciphering the RSA cryptosystem. Finally, we point out that post quantum cryptography should not only consider the potential attacks from universal quantum algorithms, such as Shor’s algorithm but also consider real attacks from a D-Wave quantum computer in the near future. Methods Quantum annealing Quantum annealing, as the core algorithm of a D-Wave quantum computer, has the potential to approach or even achieve the global optima in an exponential solution space, corresponding to the quantum evolution towards the ground state of the Hamiltonian problem[24](https://www.nature.com/articles/s41598-020-62802-5#ref-CR24). The quantum processing units (QPUs), which are the core components for performing quantum annealing, are designed to solve quadratic unconstrained binary optimization (QUBO) problems[25](https://www.nature.com/articles/s41598-020-62802-5#ref-CR25),[26](https://www.nature.com/articles/s41598-020-62802-5#ref-CR26), where each qubit represents a variable, and the couplers between qubits represent the costs associated with qubit pairs. The objective form of the QUBO that the QPU is designed to minimize is as follows: Obj(x,Q)=xT⋅Q⋅x, (1) where Obj represents objective function of QUBO,x is a vector of binary variables of sizeN , and Q is an N×N real-valued matrix characterizing the relationship between the variables. Thus, any problem given in such a form can be solved by the D-Wave quantum annealer. Multiplication table for factorization Quantum annealing uses the quantum effects generated by quantum fluctuations to realize the global optimal solution of the objective function. The integer factorization problem can be transformed into a combination optimization problem that can be handled by the quantum annealing algorithm, and the minimum energy value can be output through the quantum annealing algorithm. At this time, the minimum value is the successful solution of integer factorization. To clarify the integer factorization method via quantum annealing, we introduce a multiplication table to illustrate the feasibility of mapping the integer factorization problem to Ising model (a model can be processed by a D-Wave quantum computer). We illustrate the factorization of the integer multiplication table by factoring N=p×q , where p andq are prime numbers. Table [1](https://www.nature.com/articles/s41598-020-62802-5#Tab1) shows the factorization of 143=11×13 . In Table [1](https://www.nature.com/articles/s41598-020-62802-5#Tab1), pi andqi represent the bits of the multipliers, andzij is the carried bits fromi th bit to the j th bit. All the variables pi , qi , and zij in the equations are binary. Table 1 Multiplication table for 143 = 11 × 13 in binary. Full size table Note: All of the variables involved in Table [1](https://www.nature.com/articles/s41598-020-62802-5#Tab1) can only take the values of {0,1} . Adding each column leads to the following equations: p1+q1=1+2z12 (2) p2+p1q1+q2+z12=1+2z23+4z24 (3) 1+p2q1+p1q2+1+z23=1+2z34+4z35 (4) q1+p2q2+p1+z34+z24=0+2z45+4z46 (5) q2+p2+z45+z35=0+2z56+4z57 (6) 1+z56+z46=0+2z67 (7) z67+z57=1. (8) Because each of the variables should be 0 or 1, we can get z12=0 andp1q1=0 according to the equationp1+q1=1+2z12 . By applying similar judgments, we can get a simplified set of equations, as follows: p1+q1−1=0 (9) p2+q2−1=0 (10) p2q1+p1q2−1=0. (11) Obviously, (p1+q1−1)2 , (p2+q2−1)2 , and (p2q1+p1q2−1)2 . The objective function is defined as the sum of squares of the three equations. It can be given as follows: f=(p1+q1−1)2+(p2+q2−1)2+(p2q1+p1q2−1)2. (12) It can be seen from the above that the minimum value of Eq. [(12)](https://www.nature.com/articles/s41598-020-62802-5#Equ12) is 0, that is, (p1,p2,q1 , and q2) are the values that minimize Eq. [(12)](https://www.nature.com/articles/s41598-020-62802-5#Equ12), and it is also the solution of Eqs. [(9)](https://www.nature.com/articles/s41598-020-62802-5#Equ9)–[(11)](https://www.nature.com/articles/s41598-020-62802-5#Equ11). This means that the values of (p1,p2,q1 , and q2) represent the solution to the factorization problem. The improved multiplication table for factorization In the improved multiplication table for 143, c1 , c2 , c3 andc4 are the carried bits from the previous column. All the variables have a value of 0 or 1. Shuxian Jianget al.[30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30) divided the multiplication table into 4 columns (from right to left are column 1, column 2, column 3, and column 4), as shown in Table [2](https://www.nature.com/articles/s41598-020-62802-5#Tab2). Table 2 Improved multiplication table for 143=11×13 in binary. Full size table The equation for each column is as follows: (p2+p1q1+q2−(c2×4+c1×2))×2+(p1+q1)=(11)2=3 (13) (q1+p2q2+p1+c2−(c4×4+c3×2))×2+(1+p2q1+p1q2+1+c1)=(01)2=1 (14) (1+c4)×2+(q2+p2+c3)=(100)2=4 (15) Equations [(13)](https://www.nature.com/articles/s41598-020-62802-5#Equ13)–[(15)](https://www.nature.com/articles/s41598-020-62802-5#Equ15) are further simplified to the following 2p2+2p1q1+2q2−8c2−4c1+p1+q1−3=0 (16) 2q1+2p2q2+2p1+2c2−8c4−4c3+p2q1+p1q2+c1+1=0 (17) q2+p2+c3+2c4−2=0 (18) We define the objective function as the sum of the squares of all the columns as follows: f=(2p2+2p1q1+2q2−8c2−4c1+p1+q1−3)2+(2q1+2p2q2+2p1+2c2−8c4−4c3+p2q1+p1q2+c1+1)2+(q2+p2+c3+2c4−2)2. (19) Since Ising model can only deal with the interaction of two variables, it is necessary to process polynomials greater than the 2-local term. According to the properties p2=p , q2=q , and c2=c (the values ofp , q andc are 0 or 1), Eq. [(19)](https://www.nature.com/articles/s41598-020-62802-5#Equ19) is expanded and simplified, and the polynomials of more than 2-local term are replaced by the following equation[30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30) (for more information about factorization refer to ref. [30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30)): ⎧⎩⎨⎪⎪⎪⎪⎪⎪x1x2x3=minx4(x4x3+2(x1x2−2x1x4−2x2x4+3x4))−x1x2x3=−minx4(x4x3+2(x1x2−2x1x4−2x2x4+3x4)). (20) We replace p1q1 , p1q2 , p2q2 , and p2q1 witht1 , t2 , t3 , and t4 , respectively. In Eq. [(20)](https://www.nature.com/articles/s41598-020-62802-5#Equ20), the variable xi is used to represent the rule that the cubic term is reduced to the 2-local term. For example, the expansion termp1q1q2 in Eq. [(19)](https://www.nature.com/articles/s41598-020-62802-5#Equ19) is replaced by t1q2+2(p1q1−2p1t1−2q1t1+3t1) . Then, we perform variable replacement to transform the variables into the domain 0,1 by usingxi=(1−si)/2,i=1,2,3,⋯ if we letx1=p1 , x2=p2 , x3=q1 , x4=q2 , x5=c1 , x6=c2 , x7=c3 , x8=c4 , x9=t1 , x10=t2 , x11=t3 , and x12=t4 . Finally, via the correspondence p1=s1 , p2=s2 , q1=s3 , q2=s4⋯ , t3=s11 , and t4=s12 , Eq. [(19)](https://www.nature.com/articles/s41598-020-62802-5#Equ19) finally simplifies to the following: f′==(p1,p2,q1,q2,c1,c2,c3,c4,t1,t2,t3,t4)(261s1)/2+(215s2)/2+(261s3)/2+(215s4)/5−41s5−82s6+3s7+6s8−137s9−81s10−107s11−81s12+2s1s2+79s1s3+(95s1s4)/2+(95s2s3)/2−2s1s5+71s2s4−4s1s6−8s2s5+2s3s4−8s1s7−16s2s6−2s3s5−16s1s8+s2s7−4s3s6−8s4s5−148s1s9+2s2s8−8s3s7−16s4s6−84s1s10+6s2s9−16s3s8+s4s7+34s5s6+6s2s10−148s3s9+2s4s8−4s5s7−124s2s11+6s4s9−8s5s8−8s6s7−84s2s12−84s4s10−8s5s9−16s6s8−84s3s12−124s4s11+s5s10−16s6s9+34s7s8+6s4s12+2s5s11+2s6s10+s5s12+4s6s11−4s7s10+2s6s12−8s7s11−8s8s10−4s7s12−16s8s11−8s8s12+s9s11+794 (21) The local field h represents the coefficient value of the single term of allsi variables, and the couplingJ is the coefficient value of the 2-local term for allsisj variables. The final model can be given as follows: h=[130.5107.5130.5107.5−41−8236−137−81−107−81] (22) J=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢27947.547.5712−2−8−2−8−4−16−4−1634−81−81−4−8−162−162−8−1634−1486−1486−8−1600−8460−8412−4−800−1240−12424−8−16100−84−84612−4−8000⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥ (23) Then, the model given in Eqs. [(22)](https://www.nature.com/articles/s41598-020-62802-5#Equ22)-[(23)](https://www.nature.com/articles/s41598-020-62802-5#Equ23) can be directly solved by the D-Wave machine or the qbsolv software environment can be used to perform the quantum annealing algorithm. In this way, the model for the factorization can be generalized to any integer. Furthermore, it is a scalable model for any large integer in theory and it is a real potential application for D-Wave. In the case when the factorization increases in Shuxian Jiang et al.[30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30), the growing number of qubits and the huge coupler strength in the theoretical quantum model will result in a nontrivial impact on the QA precision in the real D-Wave machine. Especially for limit-connectivity hardware, too high of costs regarding the number of qubits greatly limits the generalization and scalability of the factorization in large cases. In addition, the reduction from the 3-local term to the 2-local term increases the coupler strength and local field coefficient, especially for large integers. This paper proposes a new model that addresses two perspectives: saving qubit resources and simplifying the quantum model to factor larger integers with fewer qubits. Using this way, we can reduce the number of involved qubits and the range of the coupler strength between qubits without any loss of generalization. It is expected to solve larger integers with fewer qubits so that the D-Wave can provide a more powerful capacity to factor large integers in the future. Optimization of model parameters In Ising model in ref. [30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30), they did not consider the restrictions on the final model derived from the target values, which may cause too many carries to be involved in the model. Here we introduce the constraints derived from the difference between the target values and the maximal output of each column. The carries involved can be directly removed in some cases. As shown in the improved multiplication table of Table [2](https://www.nature.com/articles/s41598-020-62802-5#Tab2), because all variables have values of 0,1 , according to the first entry p1+q1=1 of column 2,p1q1=0 can be obtained. The second entryp2+p1q1+q2=1 in column 2 is simplified top2+q2=1 . Therefore, there is no carry from column 2 to column 3, that is, c1=0 andc2=0 . Thus, only two carries (c3 andc4 ) are needed to represent the carry from column 3 into column 4. In addition, we can get p1=1−q1 andp2=1−q2 according top1+q1=1 andp2+q2=1 , respectively. Finally, the factorization of 143 only requires 5 qubits, a significant improvement compared to the original model with 12 qubits[30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30). Based on the optimization of ref. [32](https://www.nature.com/articles/s41598-020-62802-5#ref-CR32), the final parameters of the model are as follows: h=[−25−506060−120] (24) J=⎡⎣⎢⎢⎢34−4−8−4−841816−96−96⎤⎦⎥⎥⎥ (25) Actually, the method of ref. [32](https://www.nature.com/articles/s41598-020-62802-5#ref-CR32) is designed to reduce the number of qubits, and thus the improvements to the complexity of the model are limited. The main reason is that there is a “2” in Eq. [(20)](https://www.nature.com/articles/s41598-020-62802-5#Equ20), which leads to many high coupler strengths and local field coefficients in the final Hamiltonian resulting in fragile quantum states. Therefore, another optimization should be proposed to solve the above problem without the loss of generalization and scalability. As mentioned above, we mainly focus on the optimization of the model parameters. Jiang et al.[30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30) a way to reduce the 3-local term to a 2-local term, which increased the local field coefficient and coupler strength parameters, especially for large integers. In the integer factorization problem based on quantum annealing, the reduction of the model parameters is beneficial to reducing the hardware requirements and the precision of quantum annealing. To reduce the 3-local term to a 2-local term in the integer factorization process, inspired by ref. [35](https://www.nature.com/articles/s41598-020-62802-5#ref-CR35), we optimize Eq. [(20)](https://www.nature.com/articles/s41598-020-62802-5#Equ20) of ref. [32](https://www.nature.com/articles/s41598-020-62802-5#ref-CR32) and form a new dimension reduction method from the 3-local term to 2-local term, as shown in Eq. [(26)](https://www.nature.com/articles/s41598-020-62802-5#Equ26) ⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪x1x2x3=minx4(x4x3+x1x2−x1x4−x2x4+x4))−x1x2x3=−minx4(x4x3+2(x1x2−2x1x4−2x2x4+3x4)). (26) The negative term −x1x2x3=−minx4(x4x3+2(x1x2−2x1x4−2x2x4+3x4)) is the same as ref. [30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30). We mainly prove our optimization of the positive term, that is, why the positive term x1x2x3=minx4(x4x3+x1x2−x1x4−x2x4+x4) holds. x1x2x3=minx4(x4x3+x1x2−x1x4−x2x4+x4) (27) Table [3](https://www.nature.com/articles/s41598-020-62802-5#Tab3) is a combination of 16 values of x1 , x2 , x3 , and x4 . The values of x1 , x2 , x3 , and x4 are 0 or 1. The output of is given in the last column, followed by√ or× to represent whetherx1x2x3 equalsminx4(x4x3+x1x2−x1x4−x2x4 + x4) or not. As mentioned earlier, the integer factorization problem is the problem of finding the minimum value of a function. In other words, solving the minimum value of x1x2x3 is the same as solvingminx4(x4x3+x1x2−x1x4−x2x4+x4) ). Take the first two rows of the Table [3](https://www.nature.com/articles/s41598-020-62802-5#Tab3) as an example for the following illustration. Table 3 The truth table for the dimension reduction. Full size table In this case, where x1=0 , x2=0 , and x3=0 are fixed,x1x2x3=0 ; when x4=0 , x4x3+x1x2−x1x4−x2x4 + x4 = 0; when x4=1 , x4x3+x1x2−x1x4−x2x4+x4=1 . Therefore, minx4(x4x3+x1x2−x1x4−x2x4+x4)=0 . At this time, x1x2x3 is equivalent tominx4(x4x3+x1x2−x1x4−x2x4+x4) , and so x1x2x3=minx4(x4x3+x1x2−x1x4−x2x4+x4) . The dimension reduction method in this paper is not only applicable to the integer 143, but it is also applicable to the case where the polynomial of the objective function of any integer is greater than the quadratic term, such as the factorization of the 20-bit integer 1028171. A detailed analysis of the factorization is shown in the supplemental material. The method is universal and extensible. We do the following analysis. Assume that the objective function of the integer factorization is as follows: S(x)min=g(x)+f(xi,xj,xk), (28) where g(x) andf(xi,xj,xk) are polynomials composed of two-local terms and 3-local terms, respectively. Then, it can be transformed based on Eq. [(27)](https://www.nature.com/articles/s41598-020-62802-5#Equ27) as follows: S′(x)minxn=g(x)+minxn(xnxk+xixj−xixn−xjxn+xn). (29) Therefore, the minimum value that solves the objective function S(x)min is equivalent to the minimum value of solving the 3-local termf(x) , namely, the value of minxn(xnxk+xixj−xixn−xjxn+xn) . Therefore, the objective function S(x)min has the same solution asS′(x)minxn . Similarly, we analyze the 4-local term in the function. f(xi,xj,xk,xl) is a polynomial composed of 4-local terms. We considerxk andxl as a whole, and obtain Eq.[(30)](https://www.nature.com/articles/s41598-020-62802-5#Equ30) via minxn(xnxk+xixj−xixn−xjxn+xn) . f(xi,xj,xk,xl)=minxn(xnxkxl+xixj−xixn−xjxn+xn). (30) For the 3-local term xnxkxl in Eq.[(30)](https://www.nature.com/articles/s41598-020-62802-5#Equ30), the dimensionality reduction formula minxn(xnxk+xixj−xixn−xjxn+xn) is used again to obtain the following: f(xn,xk,xl)=minxm(xmxl+xnxk−xnxm−xkxm+xm). (31) Finally, the final 4-local term is reduced to a 2-local term as follows: f(xi,xj,xk,xl)=minxn(minxm(xmxl+xnxk−xnxm−xkxm+xm)+xixj−xixn−xjxn+xn). (32) In this way, the minimum value of the 3-local term and 4-local term can be transformed to a simpler polynomial with simple connections characterized by quadratic terms. The coupler strength and local field coefficient can be reduced further and the theoretical model can work better to describe the original problem with high precision in the simulations. Simulations All the simulations are performed via MATLAB 2014 and Python 3.6 with the qbsolv software environment (provided by D-Wave), which can successfully factor 1028171. For more information about the integer 1028171, please refer to the supplemental material. Table S[1](https://www.nature.com/articles/s41598-020-62802-5#MOESM1) of the supplemental material shows the factorization of integer 1028171. The qbsolv software environment is a decomposition solver that finds the minimum value given by a QUBO problem by splitting it into pieces that are solved either via a D-Wave system or a classical tabu solver. For more information about the tool, please refer to http://github.com/dwavesystems/qbsolv. The simulations are based on the combination of the two optimizations, which can be divided into the following steps. - Step 1. Give the improved multiplication table of Jiang et al.[30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30) that is divided into several columns. It’s complexity is less than O(log2(N)) - . - Step 2. Give the original model based on the optimization in ref. [32](https://www.nature.com/articles/s41598-020-62802-5#ref-CR32). The complexity of this step is less than O((log2(N))3) - . - Step 3. Give the final QUBO model based on the optimization of the model parameters. It’s complexity is less than O((log2(N))3) - . - Step 4. Transform it to Ising model via xi=(1−si)/2,i=1,2,3,⋯ , which is required for the quantum computing software environment. Note: xi variables are mapped tosi variables that could be processed by Ising model by the formulaxi=(1−si)/2,i=1,2,3,⋯ . The complexity of this step is O(1)- . - Step 5. Perform the simulations using the quantum computing software environment. By inputting the parameter values of h andJ in theqbsolv quantum computing software, the quantum annealing algorithm factors the integers. It’s complexity is less than O((log2(N))2) - . In the above simulations, Steps 1–4 are classical calculations, and the complexity is less than O((log2(N))3) . Step 5 performs a quantum annealing calculation. The complexity increases as the integer to be factored becomes larger, and the overall complexity is less than O((log2(N))2) . This algorithm realizes the hybrid computing structure of quantum and classical, and exerts the optimal computing power of the distributed processing problem of both quantum and classical. Take the factorization on 143 as an example, the final input is given as follows: h=[−12−50−2512−24] (33) J=⎡⎣⎢⎢⎢34−4−8−4−817816−24−24⎤⎦⎥⎥⎥ (34) Results Due to the accuracy of the error correcting and quantum manipulation technique, the short-time decoherence, the susceptibility to various noises, etc., the progress of universal quantum devices is slow, which limits the development and practical applications of Shor’s algorithm. The maximum factorization ability of Shor’s algorithm is currently the integer 85. However, D-Wave quantum computers have rapidly developed, and the number of qubits has been doubling every other year. Based on the quantum annealing method, we factor the integer 1028171. Although our method requires more qubits than Shor’s algorithm to factor the same integer, Shor’s algorithm is highly dependent on high-precision hardware. Actually, Science, Nature, and the National Academies of Sciences (NAS) are consistent in that it will be years before code-cracking by a universal quantum computer is achieved. The existing works based on NMR utilize the special properties of certain primes to perform principle-of-proof experiments. The maximum integer of factorization based on an NMR platform is 291311. The integer factorization method based on the NMR platform is not applicable to all integers and is not universal and scalable. Actually, our method is general and can factor up to 20-bit (1028171) integers, making it superior to the results obtained by any other physical implementations, including general-purpose quantum platforms (the Hua-Wei quantum computing platform), and far beyond the theoretical value (factor up to 10-bit integers) that can be obtained by the latest IBM Q System OneTM if it can run Shor’s algorithm. Table [4](https://www.nature.com/articles/s41598-020-62802-5#Tab4) shows the parameter values of Jiang et al.’s method[30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30) for integer factorization (please note that all the data of ref. [30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30) are given via our simulations, just for reference). Table [5](https://www.nature.com/articles/s41598-020-62802-5#Tab5) shows the factorization results of our method for the integers 143, 59989, 376289, 1005973 and 1028171. It can be seen from Table [5](https://www.nature.com/articles/s41598-020-62802-5#Tab5) that our method can successfully factor the integers 1005973 and 1028171. Jiang et al.’s method can factor up to the integer 376289, whereas ours method can achieve the factorization of the integer 1028171, making it superior to the results obtained by any other physical implementations. The reduction of the qubits can reduce the hardware requirements of the quantum annealing machine and further boost the accuracy of quantum annealing, which has great practical significance. In the case of the hardware restrictions of the quantum machine, our goal is to achieve the factorization of a larger-scale integer 1028171 with fewer qubits, which is the best integer factorization result solved by the quantum algorithm. Table 4 The parameter values of Jiang et al.’s[30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30) method for integer factorization. Full size table Tables [4](https://www.nature.com/articles/s41598-020-62802-5#Tab4) and [5](https://www.nature.com/articles/s41598-020-62802-5#Tab5) show that the optimization model can further reduce the weight of the qubits and the range of the coupler strength involved in the problem model, which can advance the large-scale integers in the D-Wave machine. Table 5 The parameter values of our method for integer factorization. Full size table Table [6](https://www.nature.com/articles/s41598-020-62802-5#Tab6) shows a comparison of the different algorithms when factoring the integer 7778 = 31×251 . Table 6 Comparison of different algorithms when factoring the integer 31×251 = 7781. Full size table Note: The values of the local field coefficient h and coupler strengthJ are the absolute values of the parameter ranges. Table [6](https://www.nature.com/articles/s41598-020-62802-5#Tab6) takes the maximum integer 7718 that was factored by Warren, R.H.[34](https://www.nature.com/articles/s41598-020-62802-5#ref-CR34) as an example and compares the coefficients of Ising model and qubits. In the actual quantum annealing experiment, the excessive coupling strength between the qubits reduces the possibility of reaching the ground state, and finally reduces the success rate of the integer factorization. It can be seen from Table [6](https://www.nature.com/articles/s41598-020-62802-5#Tab6) that the proposed method achieves the lowest local field coefficient h and coupling coefficientJ , reduces the ranges of the coefficients of Ising model, and uses far fewer qubits than Warren, R.H.[34](https://www.nature.com/articles/s41598-020-62802-5#ref-CR34). The reduction of the parameter value ranges can reduce the demand for qubit coupling strength, make the physical qubit flip unified, effectively increase the possibility of quantum annealing reaching the global optimal, and improve the success rate of integer factorization. In the case of insufficient precision and the immature development of existing quantum devices, the proposed method can effectively reduce the hardware requirements and improve the success rate of deciphering RSA via quantum annealing. In addition, our method successfully factors all integers within 10000, whereas Warren, R.H.[34](https://www.nature.com/articles/s41598-020-62802-5#ref-CR34) traversed and factored all integers within 1000. Discussion The integer factorization method based on the NMR platform uses the special properties of integers, and the method is not universal. The quantum annealing method based on a D-Wave quantum computer for integer factorization is limited by the hardware connection limitations of the D-Wave quantum computer, which are not enough to apply the method to larger integers. This paper shows the optimistic potential of the quantum annealing algorithm for deciphering the RSA cryptosystem. A D-Wave using quantum annealing provides a new (second) way, which is a completely different way from Shor’s algorithm. The latest IBM Q System OneTM can theoretically factor up to 10-bit integers using Shor’s algorithm, whereas our simulations showed the huge advantages of factoring 20-bit integers (1028171) using the quantum computing software environment provided by D-Wave. Our results are superior to the results obtained by any other quantum algorithm. Compared with ref. [32](https://www.nature.com/articles/s41598-020-62802-5#ref-CR32), the local field coefficient h and coupling term coefficientJ of Ising model are optimized to reduce the range of the model parameters by more than 33% and 26%, respectively, which reduces the coupling strength between qubits, further improves the stability of qubit chains and further improves the upper bound of integer factorization. With the slow progress of general-purpose quantum computers and the limitation of D-Wave quantum computer’s topological connections, the stability of Ising model can be improved by reducing the local field coefficienth and coupling coefficientJ of Ising model, which can effectively improve the upper bounds of the decomposed integers. From the perspective of practical code-cracking and generalization, we proposed a new general quantum spin model, which is a novel and further scalable way to conduct prime factorization with few qubits and QA. Lockheed Martin’s Warren, R.H.[34](https://www.nature.com/articles/s41598-020-62802-5#ref-CR34) traversed and factored all integers within 1000. Our method successfully factors all integers within 10000 and has obtained the best index (20-bit integers (1028171)) of quantum computing for factoring integers. The result exceeded the work of Shuxian Jiang et al. (factor up to 376289)[30](https://www.nature.com/articles/s41598-020-62802-5#ref-CR30) and Warren, R.H.[34](https://www.nature.com/articles/s41598-020-62802-5#ref-CR34) (factor up to 7781). At present, the fastest classical integer factorization algorithm is the number field sieve method. Its complexity is O(exp(c(logN)13)(loglogN)23) and its complexity is exponential. In theory, Shor’s algorithm requires 2n qubits to factor n-bit integers, where n is the number of binary digits of the integer[13](https://www.nature.com/articles/s41598-020-62802-5#ref-CR13). The complexity of our method is less than O(log2(N)) , where N is the number to be factored. In terms of theoretical complexity, the complexity of Shor’s algorithm is better than the algorithm proposed in this paper. In terms of factoring the maximum integer index, due to the slow development of general quantum devices, Shor’s algorithm currently factor up to integer 85, and the maximum number that can be factored by the integer factorization method based on quantum annealing of our method is integer 1028171. To achieve the factorization of the integer 1028171, Shor’s algorithm requires more than 40 universal qubits, and the number of qubits and the precision of the quantum bits are far beyond the current hardware level. Therefore, through the analysis of the factored maximum integer index, the integer factorization method based on quantum annealing has more realistic attack power than Shor’s algorithm, which is expected to result in more advantages when using the real D-Wave quantum computing platform. The current state of post quantum cryptography research exclusively referred to the potential threatens of Shor’s algorithm. From the above analysis, it can be seen that quantum annealing (the core principle of the D-Wave quantum computer) for prime factorization may be closer to cracking practical RSA codes than Shor’s algorithm. Furthermore, the experts of the post quantum cryptography international standard organization (in the 6th ETSI/IQC Quantum Safe Workshop) expressed great interest in our method. They analyzed the reason for neglecting the attacks from the D-Wave machine in post quantum cryptography research since the D-Wave computers, which have been purchased by Lockheed Martin, Google, etc., have been initially used for image processing, machine learning, combinatorial optimization, software verification, etc. Thus, post quantum cryptography research should further consider the potential of the D-Wave quantum computer for deciphering the RSA cryptosystem in future. The structure of large integers will have an impact on the complexity of the model. Future research work will further study the effects of the structure of large integers on the model and the scalability of the integer factorization when using a D-Wave quantum computer to achieve larger-scale integer factorization. Data availability All other data used in this study are available from the corresponding authors upon reasonable request. References - 1. Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings 35th annual symposium on foundations of computer science 1, 124–134 (Murray Hill, NJ, USA, 1994). - 2. Mahmud, N., El-Araby, E. & Caliga, D. Scaling reconfigurable emulation of quantum algorithms at high precision and high throughput. Quantum Engineering 1, e19 (2019). [Article](https://doi.org/10.1002%2Fque2.19) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Scaling%20reconfigurable%20emulation%20of%20quantum%20algorithms%20at%20high%20precision%20and%20high%20throughput&journal=Quantum%20Engineering&volume=1&publication_year=2019&author=Mahmud%2CN&author=El-Araby%2CE&author=Caliga%2CD) - 3. Lucero, E. et al. Computing prime factors with a josephson phase qubit quantum processor. Nat. Phys. 8, 719–723 (2012). [CAS](https://www.nature.com/articles/cas-redirect/1%3ACAS%3A528%3ADC%252BC38Xht1a...) [Article](https://doi.org/10.1038%2Fnphys2385) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Computing%20prime%20factors%20with%20a%20josephson%20phase%20qubit%20quantum%20processor&journal=Nat.%20Phys.&volume=8&pages=719-723&publication_year=2012&author=Lucero%2CE) - 4. Politi, A., Matthews, J. C. & O’brien, J. L. Shoras quantum factoring algorithm on a photonic chip. Science 325, 1221–1221 (2009). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2009Sci...325.1221P) [MathSciNet](http://www.ams.org/mathscinet-getitem?mr=2566812) [CAS](https://www.nature.com/articles/cas-redirect/1%3ACAS%3A528%3ADC%252BD1MXhtVO...) [Article](https://doi.org/10.1126%2Fscience.1173731) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Shoras%20quantum%20factoring%20algorithm%20on%20a%20photonic%20chip&journal=Science&volume=325&pages=1221-1221&publication_year=2009&author=Politi%2CA&author=Matthews%2CJC&author=O%E2%80%99brien%2CJL) - 5. Lanyon, B. et al. Experimental demonstration of a compiled version of shor’s algorithm with quantum entanglement. Phys. Rev. Lett. 99, 250505 (2007). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2007PhRvL..99y0505L) [CAS](https://www.nature.com/articles/cas-redirect/1%3ASTN%3A280%3ADC%252BD1c%252F...) [Article](https://doi.org/10.1103%2FPhysRevLett.99.250505) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Experimental%20demonstration%20of%20a%20compiled%20version%20of%20shor%E2%80%99s%20algorithm%20with%20quantum%20entanglement&journal=Phys.%20Rev.%20Lett.&volume=99&publication_year=2007&author=Lanyon%2CB) - 6. Monz, T. et al. Realization of a scalable shor algorithm. Science 351, 1068–1070 (2016). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2016Sci...351.1068M) [MathSciNet](http://www.ams.org/mathscinet-getitem?mr=3495185) [CAS](https://www.nature.com/articles/cas-redirect/1%3ACAS%3A528%3ADC%252BC28XjsVa...) [Article](https://doi.org/10.1126%2Fscience.aad9480) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Realization%20of%20a%20scalable%20shor%20algorithm&journal=Science&volume=351&pages=1068-1070&publication_year=2016&author=Monz%2CT) - 7. Dang, A., Hill, C. D. & Hollenberg, L. C. L. Optimising Matrix Product State Simulations of Shor’s Algorithm, arXiv:1712.07311v2 (2017). - 8. Vandersypen, L. M. et al. Experimental realization of shoras quantum factoring algorithm using nuclear magnetic resonance. Nature 414, 883–887 (2001). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2001Natur.414..883V) [CAS](https://www.nature.com/articles/cas-redirect/1%3ACAS%3A528%3ADC%252BD38XhtlO...) [Article](https://doi.org/10.1038%2F414883a) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Experimental%20realization%20of%20shoras%20quantum%20factoring%20algorithm%20using%20nuclear%20magnetic%20resonance&journal=Nature&volume=414&pages=883-887&publication_year=2001&author=Vandersypen%2CLM) - 9. Lu, C. Y., Browne, D. E., Yang, T. & Pan, J. W. Demonstration of a compiled version of shor’s quantum factoring algorithm using photonic qubits. Phys. Rev. Lett. 99, 250504 (2007). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2007PhRvL..99y0504L) [Article](https://doi.org/10.1103%2FPhysRevLett.99.250504) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Demonstration%20of%20a%20compiled%20version%20of%20shor%E2%80%99s%20quantum%20factoring%20algorithm%20using%20photonic%20qubits&journal=Phys.%20Rev.%20Lett.&volume=99&publication_year=2007&author=Lu%2CCY&author=Browne%2CDE&author=Yang%2CT&author=Pan%2CJW) - 10. Martíin-López, E. et al. Experimental realization of shor’s quantum factoring algorithm using qubit recycling. Nat. Photonics 6, 773–776 (2012). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2012NaPho...6..773M) [Article](https://doi.org/10.1038%2Fnphoton.2012.259) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Experimental%20realization%20of%20shor%E2%80%99s%20quantum%20factoring%20algorithm%20using%20qubit%20recycling&journal=Nat.%20Photonics&volume=6&pages=773-776&publication_year=2012&author=Mart%C3%ADin-L%C3%B3pez%2CE) - 11. Geller, M. R. & Zhou, Z. Factoring 51 and 85 with 8 qubits. Sci. reports 3 (2013). - 12. Smolin, J. A., Smith, G. & Vargo, A. Oversimplifying quantum factoring. Nature 499, 163–165 (2013). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2013Natur.499..163S) [CAS](https://www.nature.com/articles/cas-redirect/1%3ACAS%3A528%3ADC%252BC3sXhtVy...) [Article](https://doi.org/10.1038%2Fnature12290) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Oversimplifying%20quantum%20factoring&journal=Nature&volume=499&pages=163-165&publication_year=2013&author=Smolin%2CJA&author=Smith%2CG&author=Vargo%2CA) - 13. Gidney, C. Factoring with n + 2 clean qubits and n-1 dirty qubits, arXiv:1706.07884 (2017). - 14. Adrian, C. DOE pushes for useful quantum computing. Science 359, 141–142 (2018). [MathSciNet](http://www.ams.org/mathscinet-getitem?mr=3727801) [Article](https://doi.org/10.1126%2Fscience.359.6372.141) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=DOE%20pushes%20for%20useful%20quantum%20computing&journal=Science&volume=359&pages=141-142&publication_year=2018&author=Adrian%2CC) - 15. What’s coming up in 2018. Science 359, 10–12 (2018). - 16. Gibney, E. Quantum Computer Quest. Nature 516, 24 (2014). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2014Natur.516...24G) [CAS](https://www.nature.com/articles/cas-redirect/1%3ACAS%3A528%3ADC%252BC2cXitVa...) [Article](https://doi.org/10.1038%2F516024a) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Quantum%20Computer%20Quest&journal=Nature&volume=516&publication_year=2014&author=Gibney%2CE) - 17. Farhi, E. et al. A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science 292, 472–475 (2001). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2001Sci...292..472F) [MathSciNet](http://www.ams.org/mathscinet-getitem?mr=1838761) [CAS](https://www.nature.com/articles/cas-redirect/1%3ACAS%3A528%3ADC%252BD3MXjtVe...) [Article](https://doi.org/10.1126%2Fscience.1057726) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=A%20quantum%20adiabatic%20evolution%20algorithm%20applied%20to%20random%20instances%20of%20an%20np-complete%20problem&journal=Science&volume=292&pages=472-475&publication_year=2001&author=Farhi%2CE) - 18. Xu, N. et al. Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system. Phys. Rev. Lett. 108, 130501 (2012). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2012PhRvL.108m0501X) [Article](https://doi.org/10.1103%2FPhysRevLett.108.130501) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Quantum%20factorization%20of%20143%20on%20a%20dipolar-coupling%20nuclear%20magnetic%20resonance%20system&journal=Phys.%20Rev.%20Lett.&volume=108&publication_year=2012&author=Xu%2CN) - 19. Dattani, N. S. & Bryans, N. Quantum factorization of 56153 with only 4 qubits. arXiv:1411.6758 (2014). - 20. Li, Z. et al. High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: Application to the experimental factorization of 291311. arXiv:1706.08061 (2017). - 21. Tanburn, R., Okada, E. & Dattani, N. S. Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. part 1: The “deduc-reduc” method and its application to quantum factorization of numbers. arXiv:1508.04816 (2015). - 22. Okada, E., Tanburn, R. & Dattani, N. S. Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. part 2: The “split-reduc” method and its application to quantum determination of ramsey numbers. arXiv:1508.07190 (2015). - 23. King, A. D. et al. Observation of topological phenomena in a programmable lattice of 1,800 qubits. Nature 560, 456–460 (2018). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2018Natur.560..456K) [CAS](https://www.nature.com/articles/cas-redirect/1%3ACAS%3A528%3ADC%252BC1cXhsFO...) [Article](https://doi.org/10.1038%2Fs41586-018-0410-x) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Observation%20of%20topological%20phenomena%20in%20a%20programmable%20lattice%20of%201%2C800%20qubits&journal=Nature&volume=560&pages=456-460&publication_year=2018&author=King%2CAD) - 24. Das, A. & Chakrabarti, B. K. Colloquium: Quantum annealing and analog quantum computation. Reviews of Modern Physics 80, 1061 (2008). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2008RvMP...80.1061D) [MathSciNet](http://www.ams.org/mathscinet-getitem?mr=2443721) [Article](https://doi.org/10.1103%2FRevModPhys.80.1061) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Colloquium%3A%20Quantum%20annealing%20and%20analog%20quantum%20computation&journal=Reviews%20of%20Modern%20Physics&volume=80&publication_year=2008&author=Das%2CA&author=Chakrabarti%2CBK) - 25. Neukart, F. et al. Traffic flow optimization using a quantum annealer. Frontiers in ICT 4, 29 (2017). [Article](https://doi.org/10.3389%2Ffict.2017.00029) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Traffic%20flow%20optimization%20using%20a%20quantum%20annealer&journal=Frontiers%20in%20ICT&volume=4&publication_year=2017&author=Neukart%2CF) - 26. Perdomo-Ortiz, A., Dickson, N., Drew-Brook, M., Rose, G. & Aspuru-Guzik, A. Finding low-energy conformations of lattice protein models by quantum annealing. Sci. Reports 2, 571 (2012). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2012NatSR...2E.571P) [Article](https://doi.org/10.1038%2Fsrep00571) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Finding%20low-energy%20conformations%20of%20lattice%20protein%20models%20by%20quantum%20annealing&journal=Sci.%20Reports&volume=2&publication_year=2012&author=Perdomo-Ortiz%2CA&author=Dickson%2CN&author=Drew-Brook%2CM&author=Rose%2CG&author=Aspuru-Guzik%2CA) - 27. Dridi, R. & Alghassi, H. Prime factorization using quantum annealing and computational algebraic geometry. Sci. Reports 7 (2017). - 28. Hu, F., Wang, B., Wang, N. & Wang, C. Quantum machine learning with D-wave quantum computer. Quantum Engineering 1, e12 (2019). [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Quantum%20machine%20learning%20with%20D-wave%20quantum%20computer&journal=Quantum%20Engineering&volume=1&publication_year=2019&author=Hu%2CF&author=Wang%2CB&author=Wang%2CN&author=Wang%2CC) - 29. Wang, B., Zhang, H. F., Wang, H. & From, C. Evolutionary Cryptography to Quantum Artificial Intelligent Cryptography (in Chinese). Journal of Computer Research and Development 56, 2112–2134 (2019). [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Evolutionary%20Cryptography%20to%20Quantum%20Artificial%20Intelligent%20Cryptography%20%28in%20Chinese%29&journal=Journal%20of%20Computer%20Research%20and%20Development&volume=56&pages=2112-2134&publication_year=2019&author=Wang%2CB&author=Zhang%2CHF&author=Wang%2CH&author=From%2CC) - 30. Jiang, S., Britt, K. A., McCaskey, A. J., Humble, T. S. & Kais, S. Quantum Annealing for Prime Factorization. Sci. Reports 8, 17667 (2018). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2018NatSR...817667J) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Quantum%20Annealing%20for%20Prime%20Factorization&journal=Sci.%20Reports&volume=8&publication_year=2018&author=Jiang%2CS&author=Britt%2CKA&author=McCaskey%2CAJ&author=Humble%2CTS&author=Kais%2CS) - 31. Hu, F. et al. Quantum computing cryptography: Unveiling cryptographic Boolean functions with quantum annealing. arXiv: 1806.08706 (2018). - 32. Peng, W. et al. Factoring larger integers with fewer qubits via quantum annealing with optimized parameters. SCIENCE CHINA Physics, Mechanics & Astronomy. 62, 60311 (2019). [ADS](http://adsabs.harvard.edu/cgi-bin/nph-data_query?link_type=ABSTRACT&bibcode=2019SCPMA..6260311P) [Article](https://doi.org/10.1007%2Fs11433-018-9307-1) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Factoring%20larger%20integers%20with%20fewer%20qubits%20via%20quantum%20annealing%20with%20optimized%20parameters&journal=SCIENCE%20CHINA%20Physics%2C%20Mechanics%20%26%20Astronomy.&volume=62&publication_year=2019&author=Peng%2CW) - 33. Wang, X. Quest towards “factoring larger integers with commercial D-Wave quantum annealing machines”. SCIENCE CHINA Physics, Mechanics & Astronomy. 62, 960331 (2019). [Article](https://doi.org/10.1007%2Fs11433-018-9337-5) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Quest%20towards%20%E2%80%9Cfactoring%20larger%20integers%20with%20commercial%20D-Wave%20quantum%20annealing%20machines%E2%80%9D&journal=SCIENCE%20CHINA%20Physics%2C%20Mechanics%20%26%20Astronomy.&volume=62&publication_year=2019&author=Wang%2CX) - 34. Warren, R. H. Factoring on a quantum annealing computer. Quantum Information and Computation 19, 0252–0261 (2019). [MathSciNet](http://www.ams.org/mathscinet-getitem?mr=3937556) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Factoring%20on%20a%20quantum%20annealing%20computer&journal=Quantum%20Information%20and%20Computation&volume=19&pages=0252-0261&publication_year=2019&author=Warren%2CRH) - 35. Boros, E. & Hammer, P. L. Pseudo-boolean optimization. Discret. applied mathematics 123, 155–225 (2002). [MathSciNet](http://www.ams.org/mathscinet-getitem?mr=1922334) [MATH](http://www.emis.de/MATH-item?1076.90032) [Google Scholar](http://scholar.google.com/scholar_lookup?&title=Pseudo-boolean%20optimization.%20Discret&journal=applied%20mathematics&volume=123&pages=155-225&publication_year=2002&author=Boros%2CE&author=Hammer%2CPL) Download references Acknowledgements This work was supported by the Key Program of National Natural Science Foundation of China (Grant No. 61332019), the National Natural Science Foundation of China (Grant Nos. 61572304, 61272096), Open Research Fund of State Key Laboratory of Cryptology, and the grant of the Special Zone Project of National Defense Innovation. Author information Affiliations - Key laboratory of Specialty Fiber Optics and Optical Access Networks, Joint International Research Laboratory of Specialty Fiber Optics and Advanced Communication, Shanghai Institute for Advanced Communication and Data Science, Shanghai University, Shanghai, 200444, China Baonan Wang, Feng Hu, Haonan Yao & Chao Wang - State Key Laboratory of Cryptology, P. O. Box 5159, Beijing, 100878, China Baonan Wang, Feng Hu, Haonan Yao & Chao Wang - Center for Quantum Computing, Peng Cheng Laboratory, Shenzhen, 518000, China Chao Wang Contributions B.W. designed the algorithm. B.W. and H.Y. conceived the experiments and analysed the results. B.W., F.H., H.Y. and C.W. wrote and reviewed the manuscript. Corresponding author Correspondence to [Chao Wang](https://www.nature.com/articles/s41598-020-62802-5/email/correspondent/c1/ne...). Ethics declarations Competing interests The authors declare no competing interests. Additional information Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.