A general-purpose branch-and-cut solver certified 176 out of 180 benchmark instances of quadratic unconstrained binary optimization (QUBO) problems within a 600-second time limit, demonstrating a high degree of reliability for problems up to 48 variables. However, researchers at Duale Hochschule Baden-Württemberg (DHBW) found this solver’s performance dramatically shifted when presented with scrambled optimal solutions. At 48 variables, it located only four of ten optima.

In contrast, parallel tempering consistently found every optimum in every tested run within 60 seconds, highlighting the sensitivity of some solvers to initial conditions. The work compares classical, tensor-network and quantum approaches, finding that tested quantum approximate optimization algorithms offered no solution-quality improvement over classical methods.

Classical Branch-and-Cut Certifies QUBO Instances in Campaign A

This performance extended to larger instances, including 86 exceeding the scale of typical enumeration methods used in similar studies. The benchmarks comprised ten distinct problem families, each ranging from 14 to 48 variables, and the solver matched all reference energies across the entire set.

While the study developed diagnostics to rank tensor network representation demand and estimate runtime, these tools did not yield a reliable rule for selecting the optimal solver. “The preferred method therefore depends on the required outcome and the instance setting, not only on the variable count,” the researchers state, emphasizing the detailed relationship between problem characteristics and solver performance. Campaign A’s findings emphasise the importance of distinguishing between finding a solution and certifying its optimality when evaluating QUBO solvers.

Parallel Tempering Surpasses Branch-and-Cut on Randomized QUBO Optima

This sensitivity to initial conditions highlights a distinction between finding a solution and definitively proving its optimality. Researchers employed a diverse toolkit of solvers, including simulated annealing, a density-matrix renormalization group-based tensor network, and a fixed-schedule linear-ramp quantum approximate optimization algorithm, to compare against parallel tempering and the branch-and-cut approach.

The experimental setup involved 180 benchmark instances from ten families with 14–48 variables, supplemented by harder synthetic instances with known optimal solutions, extending to 128 variables. Diagnostic tools were developed to analyze structural characteristics, trajectory patterns and spectral properties, providing insights into the behavior of tensor networks and aiding in the estimation of runtime demands.

A treewidth bound, a measure of a graph’s complexity, demonstrated a strong correlation with the bond-dimension demand of tensor networks, achieving a Spearman ρ value of 0.78 for in-sample data and 0.73 for out-of-sample data. This suggests a quantifiable relationship between problem structure and computational cost, though the researchers found this metric insufficient to create a reliable rule for selecting the most efficient solver. Controlled experiments also identified instances of excited-state trapping during density-matrix renormalization group sweeps, a phenomenon mitigated by restarting the variational search.

DMRG Trajectory Diagnostics Reveal Excited-State Trapping

Controlled experiments demonstrated that restarting the variational search, essentially resetting the calculation, effectively mitigates this trapping phenomenon, improving the chances of finding a true minimum. Spectral diagnostics, performed on smaller instances, provided an independent verification of the DMRG energies and helped resolve the levels used in the excited-state trapping analysis, though these diagnostics did not bound entanglement in the LR-QAOA states. These findings emphasise the challenges in developing a universally effective optimization algorithm and highlight the importance of understanding the nuances of each approach.

Investigations into linear-ramp quantum approximate optimization algorithms (LR-QAOA) revealed no gains in solution quality when contrasted with classical methods for quadratic unconstrained binary optimization (QUBO). Simulations of 105 LR-QAOA runs showed no improvement over classical counterparts, suggesting limitations in this fixed-schedule quantum approach for the tested problem sizes.

Wishart Scaling Study Reveals Challenges for Classical Methods

Classical methods for solving quadratic unconstrained binary optimization (QUBO) problems faltered on larger instances, with none of the tested algorithms reaching the optimal solution for problems with 72 variables or more within established computational budgets. When the known optima are moved to randomly chosen bitstrings, the search comparison changes: at 48 variables the branch-and-cut solver finds only four of ten optima and certifies none, whereas parallel tempering reaches every optimum in every tested run at a 60-second budget.

QUBO Solution Quality vs. Optimality Certification Objectives

Establishing a provably optimal solution remains distinct from simply finding a low-energy state in quadratic unconstrained binary optimization (QUBO) problems, according to new research. This demonstrates a high degree of reliability in identifying provably optimal solutions for QUBO problems, though computational limits still apply. This suggests that while some solvers excel at verifying known solutions, others demonstrate greater robustness in navigating complex search spaces, even with altered initial conditions. The researchers note that “the comparison of QUBO solvers depends on whether the objective is to find a solution or to certify its optimality.”

Structural Features Do Not Yield a Solver-Selection Rule

Parallel tempering, in contrast, consistently found every optimum within 60 seconds under the same conditions, demonstrating a sensitivity to initial conditions not shared by all solvers. These experiments, detailed in sections 3.3 and 6, demonstrate that cost models, while informative, failed to produce a reliable means of predicting solver performance. The study’s outcome metrics, including the ability to prove optimality subject to numerical tolerances, were measured per solver run, providing a comprehensive comparison across different approaches.

Magic and Entanglement as Diagnostic Tools in QUBO Trajectories

Analyses of computational trajectories reveal these resources provide distinct descriptions of the states encountered during optimization, rather than interchangeable indicators of computational demand. Researchers measured entanglement by cutting the computational chain at a bond and performing Schmidt decomposition, quantifying the quantum correlation across that cut using the von Neumann entropy and the number of Schmidt components needed to retain 99% of the state’s weight. These diagnostic features, however, did not translate into a reliable method for selecting the best solver for a given problem.

Despite providing quantifiable data on the computational resources involved, the evaluated cost models failed to outperform a simple always-search-again (always-SA) baseline. The study extended classical comparisons to instances with 128 variables, finding that none of the tested classical methods could consistently reach the optimal solution when the difficulty parameter α reached 0.5, beginning at a variable count of 72.

This suggests a domain for further investigation into the limits of classical approaches as problem size increases. This finding, coupled with the limited correlation between entanglement and magic, emphasises the challenges in applying quantum resources to QUBO optimization. While diagnostic tools like entanglement and magic can illuminate aspects of the computational process, they alone cannot predict solver performance or guide effective solver selection. The work establishes a classical baseline and clarifies the capabilities of trajectory diagnostics, but highlights the need for additional evidence to achieve meaningful solver selection across different computational approaches.

👉 More information
🗞 Comparing classical and quantum QUBO solvers: optimality, trajectory diagnostics, and limits of solver selection
✍️ Gerhard Hellstern and Cedric Schacht (Duale Hochschule Baden-Württemberg (DHBW) Stuttgart, Stuttgart, Germany); Martin Zaefferer (Duale Hochschule Baden-Württemberg (DHBW) Ravensburg, Ravensburg, Germany)
🧠 ArXiv: https://arxiv.org/abs/2610.35126

More like this