Source-linked AI summary
Quantum Annealing for Combinatorial Optimization: A Benchmarking Study
Seongmin Kim, Sang-Woo Ahn, In-Saeng Suh, Alexander W. Dowling, Eungkyu Lee, Tengfei Luo
TL;DR
Large, dense QUBO problems remain difficult for classical solvers and hardware-limited quantum approaches. This study benchmarks quantum, hybrid, and classical solvers on problems up to 10,000 variables, finding that HQA achieves higher accuracy and much shorter solving times. The paper therefore identifies hybrid quantum annealing as the strongest current approach within this benchmark, while noting that present QA hardware still limits pure QA methods.
Problem
Earlier benchmarking was constrained by limited qubit counts and connectivity, leaving the performance of QA on large, dense QUBOs insufficiently established.
Method
The study benchmarks quantum and classical solvers on large, dense QUBO problems representing real-world optimization tasks, evaluating solution quality and computational time.
Results
On 10,000-variable QUBOs, HQA delivers ~0.013% higher accuracy and ~6,561× faster solving than classical solvers.
Takeaways & Limitations
Hybrid quantum annealing is currently the most efficient tested solver for complex real-world problems requiring large, dense QUBOs.
Takeaways & Limitations
Pure QA and QA–QBSolv remain limited on large problems by current qubit counts and qubit connectivity.
Abstract
from arXiv · showhide
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.
Introduction
The study motivates benchmarking modern quantum annealing against classical solvers on large, dense QUBO problems, enabled by improved hardware connectivity and hybrid algorithms.
- Introduction: Quantum annealing uses adiabatic evolution to seek optimal binary decisions for quadratic unconstrained binary optimization problems.Entangled qubits evolve toward the ground state of a problem Hamiltonian.
- Introduction: Previous benchmarks often used low-dimensional or sparse QUBO matrices because earlier hardware had limited qubits and poor connectivity.These constraints restricted evaluation on dense, large-scale problems.
- Introduction: The study benchmarks quantum and classical solvers on large, dense QUBOs representing real-world optimization problems.It evaluates both solution quality and time required to solve the problems.
Results
Across large and dense QUBO benchmarks, hybrid quantum annealing generally provides higher solution quality and shorter solving times than classical methods, while pure QA and QA–QBSolv retain scale-dependent limitations.
- Computational time: At problem size 5,000, HQA solves in 0.0854 s, compared with 74.59 s for QA–QBSolv, 167.4 s for SA–QBSolv, and 195.1 s for PT-ICM–QBSolv.Quantum solvers remain faster than classical counterparts across the evaluated problem sizes.
- Accuracy: Classical solvers become inaccurate or inefficient as dense QUBO size increases, despite improvements from QUBO decomposition.At n = 7,000, an IP solution retained an optimality gap of ~17.73% after 2 hours.
- Computational time: At n = 10,000, HQA requires 0.0855 s, versus 101 s for QA–QBSolv and 561 s for SA–QBSolv.Classical solving times rise rapidly with problem size, while decomposition reduces but does not eliminate the speed difference.
- Accuracy: HQA consistently identifies the best solutions across problem sizes, whereas QA–QBSolv does not guarantee the best solution for problems larger than 4,000.Smaller sub-QUBOs can improve QA–QBSolv accuracy but increase the number of decomposed problems and solving time.
- Implication: HQA incorporates quantum and classical algorithms to address current quantum hardware limitations in dense, large QUBOs.The paper defines quantum advantage as high accuracy and substantially faster solving than classical solvers for large-scale optimization.
- Implication: Further hardware development is expected to improve QA accuracy and reduce QUBO solving time through more qubits and better connectivity.This expectation is presented as a prospective consequence of the current hybrid results.
Discussion
The benchmark reports a quantum advantage for large, dense QUBOs: HQA combines the highest accuracy with the shortest solution time, while pure QA approaches remain hardware-limited.
- Discussion: HQA improves accuracy by ~0.013% and accelerates solving by ~6,561× versus classical solvers on 10,000-variable QUBOs.The comparison covers large, dense QUBOs with fully connected interactions.
- Discussion: The study evaluates QUBOs up to 10,000 variables with fully connected interactions to represent large, dense optimization problems.These configurations are intended to approximate real-world problems requiring dense QUBO matrices.
- Discussion: Pure QA and QA–QBSolv remain limited on large problems by current hardware constraints, including qubit count and connectivity.The reported advantage is strongest for the hybrid HQA configuration.
Methods
The study formulates and benchmarks dense QUBO optimization problems using quantum, hybrid quantum, and classical solvers, evaluating solution quality and computational time. Relative accuracy compares solver objectives when global optimality cannot be established, while solver complexity and implementation settings define the computational comparison.
- Problem formulation: QUBO objectives map linear and quadratic coefficients to an energy function whose minimum identifies the optimal binary state.Linear coefficients describe individual-variable terms, while quadratic coefficients represent pairwise interactions.
- Solver methods: The benchmark considers seven methods: QA, hybrid QA, IP, SA, SD, TS, and PT-ICM.These methods represent quantum, hybrid quantum, integer-programming, and heuristic approaches to QUBO optimization.
- Quantum annealing: QA evolves from an initial Hamiltonian toward a problem Hamiltonian, using D-Wave Advantage 4.1 with 1,000 reads and a 20 µs annealing time.The selected QA solution is the lowest-energy state found across the reads.
- Benchmark design: The benchmark uses randomly generated QUBO matrices with problem sizes from 120 to 10,000 variables to approximate dense real-world optimization problems.The configuration is designed to systematically evaluate scalability.
- Evaluation metrics: Relative accuracy is the ratio of a solver’s objective value to the best objective found across all solvers, with 1.0 indicating the best-known value.The metric supports comparisons when the global optimum cannot be definitively found or proven for large instances.
- Computational cost: Classical solver runtimes exclude problem-reading time, while their theoretical complexities are O(n^7) for SA and O(n^6) for SD and TS.Theoretical quantum-solver time complexity is treated as constant in the study.
Author information
The authors are affiliated with universities and Oak Ridge National Laboratory in the United States and South Korea. Their contributions span study conception, benchmarking, implementation, analysis, and manuscript preparation.
- Affiliations: Contributors are affiliated with the University of Notre Dame, Kyung Hee University, and Oak Ridge National Laboratory.The affiliations span Indiana, South Korea, and Tennessee.
- Contributions: The team conceived the study, performed benchmarking, implemented the IP benchmark, analyzed data, and contributed to writing.Data analysis received advice from multiple coauthors, and all authors discussed the results.
- Correspondence: Correspondence is directed to Alexander W. Dowling, Eungkyu Lee, or Tengfei Luo.
Figures
The figures compare solver accuracy, solving time, decomposition effects, matrix structure, and coefficient statistics across QUBO problem settings.
- Solver performance: Figure 1 compares classical and quantum solvers using relative accuracy and solving time on material-science QUBO problems.The solver groups include IP, SA, SD, TS, PT-ICM, QBSolv-based classical methods, QA–QBSolv, and HQA.
- Accuracy scaling: Figure 2 reports relative accuracy across problem sizes for classical solvers, QA–QBSolv, and HQA.HQA is identified as the best solver for finding the highest-quality solution at all problem sizes.
- Time scaling: Figure 3 compares solver solving times as QUBO problem size increases, including a separate view of classical solvers on small problems.Its caption states that quantum solver time does not scale with increasing problem size, unlike classical counterparts.
- Decomposition: Figure 4 examines how QA–QBSolv accuracy and solving time vary with the size of decomposed sub-QUBOs.The decomposition-size comparison covers both relative accuracy and solving time.
- Problem structure: Supplementary matrices contrast dense, fully connected material-optimization QUBOs with sparse Max-Cut instances.The material-optimization examples use sizes 100, 500, and 3,000, while the Max-Cut examples are drawn from G-set instances.
- Coefficient statistics: Supplementary coefficient statistics summarize average and standard deviation across problem sizes, with averages near zero and standard deviations from 0.2 to 2.The table reports these statistics for QUBO coefficients in real-world optimization problems.