Quantum annealing for combinatorial optimization: a benchmarking study
Abstract Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did n...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2025-05-01
|
| Series: | npj Quantum Information |
| Online Access: | https://doi.org/10.1038/s41534-025-01020-1 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849309812706246656 |
|---|---|
| author | Seongmin Kim Sang-Woo Ahn In-Saeng Suh Alexander W. Dowling Eungkyu Lee Tengfei Luo |
| author_facet | Seongmin Kim Sang-Woo Ahn In-Saeng Suh Alexander W. Dowling Eungkyu Lee Tengfei Luo |
| author_sort | Seongmin Kim |
| collection | DOAJ |
| description | Abstract Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems. |
| format | Article |
| id | doaj-art-bb9767b8eae949e2a040a39d208eaf2f |
| institution | Kabale University |
| issn | 2056-6387 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | npj Quantum Information |
| spelling | doaj-art-bb9767b8eae949e2a040a39d208eaf2f2025-08-20T03:53:57ZengNature Portfolionpj Quantum Information2056-63872025-05-011111810.1038/s41534-025-01020-1Quantum annealing for combinatorial optimization: a benchmarking studySeongmin Kim0Sang-Woo Ahn1In-Saeng Suh2Alexander W. Dowling3Eungkyu Lee4Tengfei Luo5Department of Aerospace and Mechanical Engineering, University of Notre DameDepartment of Electronic Engineering, Kyung Hee UniversityNational Center for Computational Sciences, Oak Ridge National LaboratoryDepartment of Chemical and Biomolecular Engineering, University of Notre DameDepartment of Electronic Engineering, Kyung Hee UniversityDepartment of Aerospace and Mechanical Engineering, University of Notre DameAbstract Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.https://doi.org/10.1038/s41534-025-01020-1 |
| spellingShingle | Seongmin Kim Sang-Woo Ahn In-Saeng Suh Alexander W. Dowling Eungkyu Lee Tengfei Luo Quantum annealing for combinatorial optimization: a benchmarking study npj Quantum Information |
| title | Quantum annealing for combinatorial optimization: a benchmarking study |
| title_full | Quantum annealing for combinatorial optimization: a benchmarking study |
| title_fullStr | Quantum annealing for combinatorial optimization: a benchmarking study |
| title_full_unstemmed | Quantum annealing for combinatorial optimization: a benchmarking study |
| title_short | Quantum annealing for combinatorial optimization: a benchmarking study |
| title_sort | quantum annealing for combinatorial optimization a benchmarking study |
| url | https://doi.org/10.1038/s41534-025-01020-1 |
| work_keys_str_mv | AT seongminkim quantumannealingforcombinatorialoptimizationabenchmarkingstudy AT sangwooahn quantumannealingforcombinatorialoptimizationabenchmarkingstudy AT insaengsuh quantumannealingforcombinatorialoptimizationabenchmarkingstudy AT alexanderwdowling quantumannealingforcombinatorialoptimizationabenchmarkingstudy AT eungkyulee quantumannealingforcombinatorialoptimizationabenchmarkingstudy AT tengfeiluo quantumannealingforcombinatorialoptimizationabenchmarkingstudy |