Quantum Annealing for Combinatorial Optimization: A Benchmarking Study
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908307336200192 |
|---|---|
| author | Kim, Seongmin Ahn, Sang-Woo Suh, In-Saeng Dowling, Alexander W. Lee, Eungkyu Luo, Tengfei |
| author_facet | Kim, Seongmin Ahn, Sang-Woo Suh, In-Saeng Dowling, Alexander W. Lee, Eungkyu Luo, Tengfei |
| contents | 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 5,000 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 (~6,561x) 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 | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06201 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum Annealing for Combinatorial Optimization: A Benchmarking Study Kim, Seongmin Ahn, Sang-Woo Suh, In-Saeng Dowling, Alexander W. Lee, Eungkyu Luo, Tengfei Quantum Physics Computational Engineering, Finance, and Science 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 5,000 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 (~6,561x) 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. |
| title | Quantum Annealing for Combinatorial Optimization: A Benchmarking Study |
| topic | Quantum Physics Computational Engineering, Finance, and Science |
| url | https://arxiv.org/abs/2504.06201 |