Quantum annealing distributed integer decomposition study of local field coefficient h and coupling coefficient J with stability Ising model

The difficulty in factoring large integers is a security basis of Rivest-Shamir-Adleman public key cryptography. Quantum annealing, a completely different method as compared with that of Shor’s algorithm, can transform an integer factorization problem into a combinatorial optimization problem using the quantum tunneling effects of D-wave quantum annealing to leap from local minima. In this paper, a new distributed integer factorization algorithm based on quantum annealing, which transforms an arbitrary integer into a stable Ising model executable using a D-wave quantum computer, is proposed. The stability and range of the local field coefficient h and the coupling term coefficient J of the Ising model are important factors that affect the success rate of integer factorization. Compared with the algorithm of Purdue University’s Jiang et al., the proposed method reduces the number of logical bits and the parameters of h and J by more than 60% and 40%, respectively, and the ranges of the coefficients of the Ising model are stable. Compared with the algorithm of Lockheed Martin Warren, the parameters of the proposed method are reduced in the orders from 106 to 102 of magnitude when the Ising model is guaranteed to be stable. In addition, to prove the correctness of the algorithm, Warren traversed factorization within 1000 integers. The proposed method traverses all integers within 10000 and all of them are successfully factored. The experimental results of this paper exceed the results of Shor’s algorithm, Jiang’s algorithm and the maximum published factorization scale of Lockheed Martin Warren’s algorithm.