A Quantum Framework for Combinatorial Optimization Problem over Graphs
Abstract 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 se...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2025-01-01
|
| Series: | Data Science and Engineering |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s41019-024-00269-4 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849434299170816000 |
|---|---|
| author | Meng Shi Sai Wu Ying Li Gongsheng Yuan Chang Yao Gang Chen |
| author_facet | Meng Shi Sai Wu Ying Li Gongsheng Yuan Chang Yao Gang Chen |
| author_sort | Meng Shi |
| collection | DOAJ |
| description | Abstract 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. |
| format | Article |
| id | doaj-art-af4d7d276e08419fa55ecb079d1a7641 |
| institution | Kabale University |
| issn | 2364-1185 2364-1541 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | Data Science and Engineering |
| spelling | doaj-art-af4d7d276e08419fa55ecb079d1a76412025-08-20T03:26:43ZengSpringerOpenData Science and Engineering2364-11852364-15412025-01-0110224625710.1007/s41019-024-00269-4A Quantum Framework for Combinatorial Optimization Problem over GraphsMeng Shi0Sai Wu1Ying Li2Gongsheng Yuan3Chang Yao4Gang Chen5Bangsun TechnologyBangsun TechnologyBangsun TechnologyBangsun TechnologyBangsun TechnologyBangsun TechnologyAbstract 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.https://doi.org/10.1007/s41019-024-00269-4Quantum computingVariational quantum algorithmsCombinatorial optimization problemTraveling salesman problem |
| spellingShingle | Meng Shi Sai Wu Ying Li Gongsheng Yuan Chang Yao Gang Chen A Quantum Framework for Combinatorial Optimization Problem over Graphs Data Science and Engineering Quantum computing Variational quantum algorithms Combinatorial optimization problem Traveling salesman problem |
| title | A Quantum Framework for Combinatorial Optimization Problem over Graphs |
| title_full | A Quantum Framework for Combinatorial Optimization Problem over Graphs |
| title_fullStr | A Quantum Framework for Combinatorial Optimization Problem over Graphs |
| title_full_unstemmed | A Quantum Framework for Combinatorial Optimization Problem over Graphs |
| title_short | A Quantum Framework for Combinatorial Optimization Problem over Graphs |
| title_sort | quantum framework for combinatorial optimization problem over graphs |
| topic | Quantum computing Variational quantum algorithms Combinatorial optimization problem Traveling salesman problem |
| url | https://doi.org/10.1007/s41019-024-00269-4 |
| work_keys_str_mv | AT mengshi aquantumframeworkforcombinatorialoptimizationproblemovergraphs AT saiwu aquantumframeworkforcombinatorialoptimizationproblemovergraphs AT yingli aquantumframeworkforcombinatorialoptimizationproblemovergraphs AT gongshengyuan aquantumframeworkforcombinatorialoptimizationproblemovergraphs AT changyao aquantumframeworkforcombinatorialoptimizationproblemovergraphs AT gangchen aquantumframeworkforcombinatorialoptimizationproblemovergraphs AT mengshi quantumframeworkforcombinatorialoptimizationproblemovergraphs AT saiwu quantumframeworkforcombinatorialoptimizationproblemovergraphs AT yingli quantumframeworkforcombinatorialoptimizationproblemovergraphs AT gongshengyuan quantumframeworkforcombinatorialoptimizationproblemovergraphs AT changyao quantumframeworkforcombinatorialoptimizationproblemovergraphs AT gangchen quantumframeworkforcombinatorialoptimizationproblemovergraphs |