PaperlayerView exact revision on arXiv

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

arXiv:2504.06201v1quant-phcs.CE

TL;DR

Whether quantum annealing can outperform classical solvers on large, dense optimization problems remains an open benchmarking question. This study compares quantum and classical solvers on large, dense QUBOs, finding that HQA improves accuracy by ~0.013% and accelerates solution time ~6,561×.

  • Problem

    Whether quantum solvers can outperform classical methods on large, dense QUBOs remains a practical benchmarking question, as classical decomposition can remain too slow for massive problems.

    Source: Results · p. 3

  • Method

    The study benchmarks quantum and classical solvers on large, dense QUBO problems, comparing solution quality and solving time.

    Source: Introduction · p. 2

  • Results

    HQA achieves the highest accuracy (~0.013% improvement) and shortest solution time (~6,561× acceleration) among the compared solvers.

    Source: Discussion · p. 5

  • Takeaways & Limitations

    HQA is currently the most efficient solver for complex real-world problems requiring large, dense QUBOs.

    Source: Results · p. 4

    The benchmark uses fully connected dense QUBOs as an approximation of real-world optimization problems.

    Source: Methods · p. 9

Abstract

from arXiv · show

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

This study benchmarks quantum and classical solvers on large, dense QUBO problems intended to represent real-world optimization tasks, comparing solution quality and solving time.

Introduction

  • Quantum annealing uses an adiabatic process in which entangled qubits evolve toward a Hamiltonian’s ground state to identify an optimal vector of binary decisions for a QUBO.The introduction presents QA as able to explore high-dimensional combinatorial spaces and handle a wide range of optimization tasks.Source: Introduction · pp. 1–2
  • Previous benchmarks often used low-dimensional or sparse QUBOs because of hardware limits; reported comparisons found similar quality and solving time, while integer programming was faster for small problems.Examples include O’Malley et al. 17, limited to 35 binary variables; Tasseff et al. 18, studying sparse problems with up to 5,000 variables and 40,000 quadratic terms; and Haba et al. 19, reporting faster integer programming for problems with about 100 variables.Source: Introduction · p. 2
  • More than 5,000 qubits, improved connectivity, hybrid algorithms, and QUBO decomposition motivate benchmarking dense, high-dimensional problems on state-of-the-art QA hardware.The introduction says improved connectivity can make embedding more efficient, while QBSolv divides large QUBOs into subQUBOs that fit within hardware limits.Source: Introduction · p. 2
  • The study compares several quantum and classical solvers on large, dense QUBO benchmark problems, evaluating solution quality and the time required to solve them.The authors frame these problems as representations of real-world optimization tasks.Source: Introduction · p. 2

Results

Across dense, large QUBO benchmarks, quantum solvers—especially HQA—delivered stronger solution quality and shorter solving times than classical counterparts. Smaller QUBO decomposition improved accuracy but increased runtime.

Results

  • Quantum solvers consistently found high-quality solutions across problem sizes, while SA–QBSolv still failed to find high-quality solutions above 4,000 variables.IP and SA were more accurate than SD and TS but failed to identify the optimal state for large problems; at n = 7,000, IP's optimality gap remained ~17.73% after 2 hours.Source: Results · pp. 3–4
  • At 5,000 variables, HQA solving time was 0.0854 s and QA–QBSolv was 74.59 s, versus 167.4 s for SA–QBSolv and 195.1 s for PT-ICM–QBSolv.SA and PT-ICM struggled to handle problems with more than 3,000 variables because of excessive solving times or computational constraints such as memory limits.Source: Results · p. 3
  • At n = 10,000, HQA solving time was 0.0855 s, versus 101 s for QA–QBSolv and 561 s for SA–QBSolv, while HQA consistently found the best solution across problem sizes.The study reports that HQA reliably identified the best solution regardless of problem size.Source: Results · p. 4
  • Classical solving times increased rapidly with problem size; decomposition reduced runtime, but quantum solvers remained faster than classical counterparts, including at n = 10,000.IP could be faster than other classical solvers but still required significant time for large problems, such as n > 5,000.Source: Results · pp. 3–4
  • Smaller QA–QBSolv sub-QUBOs fit the hardware better and improved accuracy, but increased the number of subproblems and total solving time; QA–QBSolv did not guarantee the best solution above 4,000 variables.Standalone QA accuracy was 1.0 for problem size 30 and 0.9956 for size 100.Source: Results · p. 4
  • The study defines “Quantum Advantage” as a quantum-enhanced solver achieving high accuracy and significantly faster solving time than classical solvers on large-scale optimization problems.The authors identify HQA, which combines QA with classical algorithms to address current hardware limitations, as currently the most efficient solver for complex real-world problems requiring dense, large QUBOs; they expect more qubits and better connectivity to further improve QA accuracy and speed.Source: Results · pp. 4–5

Discussion

For large, dense QUBO problems, HQA outperformed classical solvers, while pure QA and decomposition-assisted QA remained limited by current hardware constraints.

  • ~0.013% improvement in accuracy and ~6,561× acceleration in solution time made HQA the strongest solver for 10,000-dimensional QUBO problems.The comparison covered large, dense QUBOs with up to 10,000 variables and fully connected interactions.Source: Discussion · p. 5
  • Classical solvers struggled on large-scale problems, and QUBO decomposition improved their performance but did not prevent declining accuracy and efficiency as problem size increased.Source: Discussion · p. 5
  • Pure QA and decomposition-assisted QA remained limited on large problems by current hardware constraints, including qubit count and connectivity.The authors expect ongoing hardware development to let QA eventually reach HQA's efficiency and demonstrate quantum advantage.Source: Discussion · p. 5

Methods

The methods formulate optimization tasks as QUBOs and compare quantum, hybrid, and classical solvers on real-world and synthetic dense problems. The study defines relative accuracy and solve time to evaluate solution quality and computational cost.

Definition of a QUBO

  • The methods use QUBOs to encode binary decisions, with linear terms for individual-variable costs or benefits and quadratic terms for pairwise interactions.A QUBO objective is minimized over binary vectors; in the material-optimization application, learned coefficients represent the system’s optimization landscape.Source: Methods · pp. 5–6

Methods to Solve a QUBO

  • The benchmark compares seven QUBO solvers: QA, HQA, IP, SA, SD, TS, and PT-ICM.QA used 1,000 reads and a 20 µs annealing time; QBSolv decomposition used sub-QUBOs of size 30 unless otherwise specified, while HQA decomposes and aggregates subproblems.Source: Methods · p. 6

Integer Programming

  • The study uses Gurobi IP with a 0.1% global optimality gap, a two-hour limit, and a 240 GB memory limit per problem.The QUBO is implemented in Pyomo; larger-gap experiments are not reported.Source: Methods · p. 7

Classical solver implementations

  • The classical heuristics use solver-specific search mechanisms and configurations, including 1,000 reads for SA, SD, and TS, and 10 replicas for PT-ICM.SA uses 1,000 sweeps and a geometric temperature schedule; SD uses random initial states; TS has a 100 ms timeout; PT-ICM uses 1,000 sweeps and 10 iterations.Source: Methods · p. 7

Benchmarking Problems: Real-world problems

  • Material-optimization instances model planar multilayer optical films, using transfer-matrix calculations and factorization-machine-learned coefficients to generate dense QUBOs.Layer configurations and their figures of merit train the factorization machine; the films use silicon dioxide, silicon nitride, aluminum oxide, and titanium dioxide.Source: Methods · p. 8

Benchmarking Problems

  • Random QUBOs span sizes 120–10,000, four coefficient standard deviations, and fully connected matrices designed to approximate dense real-world optimization problems.The standard deviations are 0.001, 0.01, 0.1, and 1; the study also describes sparse Max-Cut instances with densities of 0.02%–6%, in contrast to 100%-dense real-world QUBOs.Source: Methods · pp. 8–9

Performance Metrics: Relative Accuracy and Computational Time

  • Relative accuracy is each solver’s objective value divided by the best objective found across all solvers, with 1.0 indicating the best-known value.The metric is used when the global optimum cannot be definitively found or proven; plotted averages use three material-optimization QUBOs or four QUBOs per problem size, depending on the figure.Source: Methods · p. 9
  • Solve time excludes problem reading, queue, and communication time, while QA and HQA timing includes QPU programming and sampling.QPU access time is used for QA and HQA; classical solvers run on a workstation, whereas Gurobi runs on a cluster node.Source: Methods · pp. 9–10

Figures

The figures compare classical and quantum solvers on real-world material-science QUBOs. They identify HQA as the highest-accuracy solver across problem sizes and report that quantum solvers do not scale in solving time as size increases.

Performance analysis

  • Fig. 1 compares relative accuracy and solving time for seven classical and two quantum solvers on real-world material-science optimization QUBOs.The classical solvers are IP, SA, SD, TS, PT-ICM, SA–QBSolv, and PT-ICM–QBSolv; the quantum solvers are QA–QBSolv and HQA.Source: Figure 1 · p. 15

Relative accuracy

  • HQA is the best solver for finding the highest-quality solution across all given QUBO problem sizes.The relative-accuracy comparison includes classical IP, SA, SD, TS, and SA–QBSolv, and quantum QA–QBSolv and HQA.Source: Figure 2 · p. 16

Solving time

  • Quantum solvers do not scale in solving time as problem size increases, which the figure describes as an advantage over classical counterparts.The figure compares classical and quantum solver times and separately plots classical SA, SD, and TS times for small QUBOs.Source: Figure 3 · p. 16

Decomposition size

  • QA–QBSolv performance is plotted for different decomposition sizes, with relative accuracy and solving time shown for different sub-QUBO sizes.Source: Figure 4 · p. 17

QUBO properties

  • Material-science QUBO matrices are dense, unlike the sparse Max-Cut instances with density lower than 6%; real-world QUBO coefficient averages are near zero and standard deviations range from 0.2 to 2.Source: Figure S1 · p. 18, Table S2 · p. 20, Table S1 · p. 20
Loading 2504.06201v1…