.png){kind=icon}
.png){kind=icon}
Return
A Quantum Framework for Combinatorial Optimization Problem over Graphs
.png){kind=icon}
OA
AI
DOI：10.1007/s41019-024-00269-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Quantum computing
Variational quantum algorithms
Combinatorial optimization problem
Traveling salesman problem
Journal
D
IF:
4.6
Papers:
246
Citations:
665
Organization
No organization information available