Iterative quantum algorithm for combinatorial optimization based on quantum gradient descent
Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. H...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-01-01
|
| Series: | Results in Physics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S221137972300997X |
| _version_ | 1797350957271482368 |
|---|---|
| author | Xin Yi Jia-Cheng Huo Yong-Pan Gao Ling Fan Ru Zhang Cong Cao |
| author_facet | Xin Yi Jia-Cheng Huo Yong-Pan Gao Ling Fan Ru Zhang Cong Cao |
| author_sort | Xin Yi |
| collection | DOAJ |
| description | Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. Here, an iterative quantum algorithm based on quantum gradient descent to solve combinatorial optimization problems is introduced, where the initial state of a quantum register evolves over several iterations to a good approximation of the Ising-Hamiltonian ground state. We verified the effectiveness of the proposed algorithm in solving the MaxCut problem for different types of undirected graphs by numerical simulations, and analyzed the robustness of the algorithm to errors by simulating random error and Gaussian error. We compared the performance of the algorithm with the quantum approximate optimization algorithm, and the results indicate that the proposed algorithm has comparable convergence performance. We also verified the feasibility of the algorithm by conducting experiments on a real quantum computer through the quantum cloud platform. Our work provides a potential method for solving combinatorial optimization problems on future quantum devices without the use of complex classical optimization loops. |
| first_indexed | 2024-03-08T12:52:35Z |
| format | Article |
| id | doaj.art-a08b9b3df7f14e968c1d41692f6e390a |
| institution | Directory Open Access Journal |
| issn | 2211-3797 |
| language | English |
| last_indexed | 2024-03-08T12:52:35Z |
| publishDate | 2024-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Results in Physics |
| spelling | doaj.art-a08b9b3df7f14e968c1d41692f6e390a2024-01-20T04:44:54ZengElsevierResults in Physics2211-37972024-01-0156107204Iterative quantum algorithm for combinatorial optimization based on quantum gradient descentXin Yi0Jia-Cheng Huo1Yong-Pan Gao2Ling Fan3Ru Zhang4Cong Cao5State Key Laboratory of Information Photonics and Optical Communications, Beijing University of Posts and Telecommunications, Beijing 100876, China; School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, ChinaState Key Laboratory of Information Photonics and Optical Communications, Beijing University of Posts and Telecommunications, Beijing 100876, China; School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, ChinaState Key Laboratory of Information Photonics and Optical Communications, Beijing University of Posts and Telecommunications, Beijing 100876, China; School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, ChinaSchool of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China; Beijing Key Laboratory of Space-Ground Interconnection and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, ChinaState Key Laboratory of Information Photonics and Optical Communications, Beijing University of Posts and Telecommunications, Beijing 100876, China; School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China; Beijing Key Laboratory of Space-Ground Interconnection and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, ChinaState Key Laboratory of Information Photonics and Optical Communications, Beijing University of Posts and Telecommunications, Beijing 100876, China; School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China; Beijing Key Laboratory of Space-Ground Interconnection and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, China; Corresponding author at: School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China.Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. Here, an iterative quantum algorithm based on quantum gradient descent to solve combinatorial optimization problems is introduced, where the initial state of a quantum register evolves over several iterations to a good approximation of the Ising-Hamiltonian ground state. We verified the effectiveness of the proposed algorithm in solving the MaxCut problem for different types of undirected graphs by numerical simulations, and analyzed the robustness of the algorithm to errors by simulating random error and Gaussian error. We compared the performance of the algorithm with the quantum approximate optimization algorithm, and the results indicate that the proposed algorithm has comparable convergence performance. We also verified the feasibility of the algorithm by conducting experiments on a real quantum computer through the quantum cloud platform. Our work provides a potential method for solving combinatorial optimization problems on future quantum devices without the use of complex classical optimization loops.http://www.sciencedirect.com/science/article/pii/S221137972300997XIterative quantum algorithmCombinatorial optimizationQuantum gradient descentIsing HamiltonianLinear combination of unitariesMaxCut problem |
| spellingShingle | Xin Yi Jia-Cheng Huo Yong-Pan Gao Ling Fan Ru Zhang Cong Cao Iterative quantum algorithm for combinatorial optimization based on quantum gradient descent Results in Physics Iterative quantum algorithm Combinatorial optimization Quantum gradient descent Ising Hamiltonian Linear combination of unitaries MaxCut problem |
| title | Iterative quantum algorithm for combinatorial optimization based on quantum gradient descent |
| title_full | Iterative quantum algorithm for combinatorial optimization based on quantum gradient descent |
| title_fullStr | Iterative quantum algorithm for combinatorial optimization based on quantum gradient descent |
| title_full_unstemmed | Iterative quantum algorithm for combinatorial optimization based on quantum gradient descent |
| title_short | Iterative quantum algorithm for combinatorial optimization based on quantum gradient descent |
| title_sort | iterative quantum algorithm for combinatorial optimization based on quantum gradient descent |
| topic | Iterative quantum algorithm Combinatorial optimization Quantum gradient descent Ising Hamiltonian Linear combination of unitaries MaxCut problem |
| url | http://www.sciencedirect.com/science/article/pii/S221137972300997X |
| work_keys_str_mv | AT xinyi iterativequantumalgorithmforcombinatorialoptimizationbasedonquantumgradientdescent AT jiachenghuo iterativequantumalgorithmforcombinatorialoptimizationbasedonquantumgradientdescent AT yongpangao iterativequantumalgorithmforcombinatorialoptimizationbasedonquantumgradientdescent AT lingfan iterativequantumalgorithmforcombinatorialoptimizationbasedonquantumgradientdescent AT ruzhang iterativequantumalgorithmforcombinatorialoptimizationbasedonquantumgradientdescent AT congcao iterativequantumalgorithmforcombinatorialoptimizationbasedonquantumgradientdescent |