维普中文期刊产品整合服务

Quantum algorithm and experimental demonstration for the subset sum problem

查看全文 作　　者：Qilin [1]ZHENG;Pingyu [1]ZHU;Shichuan [1]XUE;Yang [1]WANG;Chao [1]WU;Xinyao [1]YU;Miaomiao [1]YU;Yingwen [1]LIU;Mingtang [1]DENG;Junjie [1]WU;Ping [1]XU 高影响力作者 机构地区：[1]Institute for Quantum Information and State Key Laboratory of High Performance Computing,College of Computer Science and Technology,National University of Defense Technology,Changsha 410073,China高影响力机构 出　　处：《Science China(Information Sciences)》索引2022年第65卷第8期,共14页高影响力期刊 基　　金：supported by National Key Research and Development Program of China(Grant Nos.2019YFA0308700,2017YFA0303700);National Natural Science Foundation of China(Grant No.11690031)。 摘　　要：To solve the subset sum problem,a well-known nondeterministic polynomial-time complete problem that is widely used in encryption and resource scheduling,we propose a feasible quantum algorithm that utilizes fewer qubits to encode and achieves quadratic speedup.Specifically,this algorithm combines an amplitude amplification algorithm with quantum phase estimation,and requires n+t+1 qubits and O(2(0.5+o(1))n)operations to obtain the solution,where n is the number of elements,and t is the number of qubits used to store the eigenvalues.To verify the performance of the algorithm,we simulate the algorithm with the online quantum simulator of IBM named ibmq simulator using Qiskit and then run it on two IBM quantum computers called ibmq santiago and ibmq bogota.The experimental results indicate that compared with the brute force algorithm,the proposed algorithm results in quadratic acceleration for the problem of a set S with four elements and two subsets whose sum equals target w.Using the iterator twice,we obtain success probabilities of 0.940±0.004,0.751±0.040,and 0.665±0.060 on the simulator,ibmq santiago,and ibmq bogota,respectively,and the fidelity between the theoretical and experimental quantum states is calculated to be 0.944±0.002,0.753±0.017,and 0.657±0.028,respectively.If the error rates of the experimental quantum logic gates can be reduced,the success probabilities of the proposed algorithm on real quantum devices can be further improved. 关 键 词：quantum algorithm subset sum quadratic speedup ENCRYPTION algorithm complexity
相关文献

参考文献(42)

引证文献(2)

网站首页 | 关于我们 | 联系我们 | 产品服务 | 客服中心 | 广告服务 | 版权声明 | 网站联盟 | 友情链接 | 售卡网点

版权所有© 渝B2-20050021-1　渝公网安备 50019002500403号　违法和不良信息举报中心

互联网出版许可证 新出网证(渝)字10号 全国400电话 - 免长途话费