具有稳定性Ising模型局部场系数h和耦合项系数J的量子退火分布式整数分解研究  

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

作　　者：王宝楠 姚皓南 胡风[1,2] 王潮 WANG BaoNan;YAO HaoNan;HU Feng;WANG Chao(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;State Key Laboratory of Cryptology,Beijing 100878,China;Center for Quantum Computing,Peng Cheng Laboratory,Shenzhen 518000,China)

机构地区：[1]上海大学,特种光纤与光接入网重点实验室,特种光纤与先进通信国际合作联合实验室,上海先进通信与数据科学研究院,上海200444 [2]密码科学技术国家重点实验室,北京100878 [3]鹏城实验室量子计算中心,深圳518000

出　　处：《中国科学：物理学、力学、天文学》2020年第3期127-137,共11页Scientia Sinica Physica,Mechanica & Astronomica

基　　金：国防创新特区项目;国家自然科学基金(编号:61572304,61272096,61332019);密码科学技术国家重点实验室开放课题基金资助

摘　　要：分解大整数的困难程度是RSA公钥密码的安全基础,量子退火破译RSA密码与Shor算法有着本质性的不同,将整数分解问题转化为组合优化问题,利用D-Wave量子退火特有的量子隧穿效应跳出局部亚优解.本文提出一种新的分布式量子退火整数分解算法,将任意整数转变为D-Wave量子计算机可执行的稳定性Ising模型的框架.Ising模型局部场系数h、耦合项系数J的稳定性和取值范围是影响到整数分解成功率的重要因素,与普渡大学Jiang等人的算法相比,本文算法在降低使用的逻辑比特数的同时,参数h,J降低程度达到60%和40%以上,且Ising模型系数取值范围稳定;与洛克希德·马丁公司Warren的算法相比,在保证可以达到Ising模型稳定的情况下,本文算法参数h,J从10^6降低到10^2数量级.此外,Warren为了证明其提出的算法的正确性,遍历分解1000以内的整数,本文的算法遍历10000以内的整数,均成功分解.本文算法实验结果超过了目前Shor算法、普渡大学Jiang等人和洛克希德·马丁公司Warren公开文献最大分解规模.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 10^6 to 10^2 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.

关 键 词：RSA 量子退火 分布式 

分 类 号：TN918.4[电子电信—通信与信息系统] O413[电子电信—信息与通信工程]