A Quantum Framework for Combinatorial Optimization Problem over Graphs

作     者：Shi, Meng Wu, Sai Li, Ying Yuan, Gongsheng Yao, Chang Chen, Gang 

作者机构：Bangsun Technol Hangzhou Zhejiang Peoples R China 

出 版 物：《DATA SCIENCE AND ENGINEERING》 (Data Sci. Eng.)

年 卷 期：2025年第10卷第2期

页      面：246-257页

核心收录：

主　　题：Quantum computing Variational quantum algorithms Combinatorial optimization problem Traveling salesman problem 

摘      要：Combinatorial optimization problems over graphs, such as the traveling salesman problem, longest path problem, and maximum independent set problem, are well-known for being computationally costly, some even NP-hard problems. In this paper, we propose a general quantum algorithm framework searching for approximate solutions to combinatorial optimization problems with linear objective functions. Our framework provides APIs (application programming interfaces) that enable developers to encode weighted graph structures onto quantum circuits and utilize variational algorithms to generate approximate solutions. One key advantage of our framework is that it allows developers to design new graph algorithms for the graph problem represented as linear combinations of edge weights without requiring expertise in quantum programming. Besides, it only uses a logarithmic level of quantum bit scale, making our framework work on quantum computers with limited physical resources. Our experimental results demonstrate that our framework can provide good approximations for the traveling salesman problem compared to current quantum algorithm.