Quantum annealing for combinatorial optimization: a benchmarking study

Seongmin Kim

doi:10.1038/s41534-025-01020-1

Quantum annealing for combinatorial optimization: a benchmarking study

2025-05-16

0

OA

AI

Alexander W. Dowling *

L

Luo, Tengfei *

DOI：10.1038/s41534-025-01020-1

Original

Original request for help

Save

Abstract

En 中文

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 (similar to 0.013%) and a significantly faster problem-solving time (similar to 6561x) 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.

Keywords:

DESIGN

Quantum annealing for combinatorial optimization: a benchmarking study

Abstract

Journal

Organization