Solving the subset sum problem by the quantum Ising model with variational quantum optimization based on conditional values at risk

作     者：Qilin Zheng Miaomiao Yu Pingyu Zhu Yan Wang Weihong Luo Ping Xu 

作者机构：Institute for Quantum Information and State Key Laboratory of High Performance ComputingCollege of Computer Science and TechnologyNational University of Defense TechnologyChangsha 410073China Hefei National LaboratoryHefei 230088China 

出 版 物：《Science China(Physics,Mechanics & Astronomy)》 (中国科学：物理学、力学、天文学（英文版）)

年 卷 期：2024年第67卷第8期

页      面：43-55页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0702[理学-物理学] 070101[理学-基础数学] 

基　　金：supported by the National Key R&D Program of China(Grant No.2019YFA0308700) the Innovation Program for Quantum Science and Technology(Grant No.2021ZD0301500) 

主　　题：subset sum problem quantum Ising model conditional values at risk variational quantum optimization 

摘      要：The subset sum problem is a combinatorial optimization problem,and its complexity belongs to the nondeterministic polynomial time complete(NP-Complete)*** problem is widely used in encryption,planning or scheduling,and integer *** accurate search algorithm with polynomial time complexity has not been found,which makes it challenging to be solved on classical *** effectively solve this problem,we translate it into the quantum Ising model and solve it with a variational quantum optimization method based on conditional values at *** proposed model needs only n qubits to encode 2ndimensional search space,which can effectively save the encoding quantum *** model inherits the advantages of variational quantum algorithms and can obtain good performance at shallow circuit depths while being robust to noise,and it is convenient to be deployed in the Noisy Intermediate Scale Quantum *** investigate the effects of the scalability,the variational ansatz type,the variational depth,and noise on the ***,we also discuss the performance of the model under different conditional values at *** computer simulation,the scale can reach more than nine *** selecting the noise type,we construct simulators with different QVs and study the performance of the model with *** addition,we deploy the model on a superconducting quantum computer of the Origin Quantum Technology Company and successfully solve the subset sum *** model provides a new perspective for solving the subset sum problem.