International Joint Conference on Computer Science and Software Engineering

A Comparative study of D-Wave’s Quantum Hybrid Solvers: BQM vs CQM on Combinatorial Optimization

Wiwat Asawalertsak, Prapong Prechaprapranwong, Rajchawit Sarochawikasit

Published Nov 2, 2025• 0 citations

Abstract

This study compares the performance of D-Wave’s two quantum-classical hybrid optimization solvers, which integrate quantum computing principles with classical optimization techniques to solve complex optimization problems. It focuses on the Binary Quadratic Model (BQM) solver, which encodes optimization problems using a binary quadratic formulation, and the Constrained Quadratic Model (CQM) solver, which can incorporate constraints into the model. The solvers were tested on five combinatorial optimization problems: Traveling Salesman Problem (TSP), Quadratic Knapsack Problem (QKP), Quadratic Assignment Problem (QAP), Weighted Max-Cut Problem (WMP), and Maximum Clique Problem (MCP). The goal is to quantify the accuracy of solutions compared to the optimal ones. Experiments on multiple instances with known optimal solutions examined solver behavior and solution quality. At default execution durations, the CQM solver generally outperforms BQM with lower error and higher consistency. Across all test problem instances in TSP, QKP, QAP, and WMP, the CQM solver achieved lower average absolute errors by 48.38, 27.83, 21.29, and 0.05 percentage points, respectively, compared to the BQM solver. An exception was found in MCP, where the BQM solver outperformed the CQM solver by 0.75 percentage points. These findings provide a guide for end users to understand the characteristics of the solvers and to select the appropriate solver for their specific optimization problems.

DOI: 10.1109/jcsse67377.2025.11297943

Related papers

D-Wave’s Nonlinear-Program Hybrid Solver: Description and Performance Analysis

Eneko Osaba, Pablo Miranda-Rodriguez

The development of advanced quantum-classical algorithms is among the most prominent strategies in quantum computing. Numerous hybrid solvers have been introduced recently. Many of these methods are created ad hoc to address specific use cases. However, several well-established schemes are frequently utilized to address optimization problems. In this context, D-Wave launched theHybrid Solver Servicein 2020, offering a portfolio of methods designed to accelerate time-to-solution for users aiming to optimize performance and operational processes. Recently, a new technique has been added to this portfolio: theNonlinear-Program Hybrid Solver. This paper describes this solver and evaluates its performance through a benchmark of 45 instances across three combinatorial optimization problems: the Traveling Salesman Problem, the Knapsack Problem, and the Maximum Cut Problem. To facilitate the use of this relatively unexplored solver, we provide details of the implementation used to solve these three optimization problems.

arXiv:2410.07980IEEE AccessJan 1, 202520 citations

Quantum optimization for the warehouse layout problem

Kumar Gosh, Haitao Li

Abstract The warehouse layout problem (WLP), also known as warehouse slotting problem, aims to determine the assignment of products to storage locations while minimizing the total travel distance for picking operations. It is combinatorial in nature and well-known to be NP-hard. To obtain high-quality solutions to medium and large WLP instances efficiently remains a computational challenge, which has motivated our work on applying quantum optimization algorithms for this problem. We reformulate the classical quadratic assignment programming (QAP) model of the WLP to a quadratic unconstrained binary optimization (QUBO) model. Our QUBO model avoids adding slack variables and reduces additional overheads as in the typical QUBO reformulation approach, which facilitates the application of the D-Wave Leap Hybrid solver. Computational study is performed on a use case with 30 stock-keeping-units (SKUs) and 32 storage slots, for which the QUBO formulation has 960 binary decision variables. We show that the D-Wave Leap Hybrid solver finds better solution to the base scenario than the exact IBM CPLEX mixed-integer quadratic programming (MIQP) solver operating under a 60-second wall-clock limit, one-tenth of the 600-second budget allocated to CPLEX in this experimental design. A sensitivity analysis across 30 scenarios, generated by crossing five annual pick volume profiles with six co-picking matrix density levels (0.5 to 1.0), shows that the D-Wave hybrid solver outperforms CPLEX MIQP solver in 26 of 30 cases, with solution quality improvements of 0.4 to 12.1%. D-Wave’s advantage generally increases as the density of co-picking matrix decreases. These results demonstrate quantum utility for WLP and motivate further investigation of hybrid quantum-classical methods for combinatorial logistics optimization at industrial strength scales.

Scientific ReportsAug 15, 20260 citations

On good encodings for quantum annealer and digital optimization solvers

Alberto Ceselli, Marco Premoli

Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.

Scientific ReportsApr 6, 202310 citations

A CQM-based approach to solving a combinatorial problem with applications in drug design

B. Maurice Benson, Victoria M. Ingman, Agarwal, Abhay +1 more

The use of D-Wave's Leap Hybrid solver is demonstrated here in solving a Knapsack optimization problem: finding meal combinations from a fixed menu that fit a diner's constraints. This is done by first formulating the optimization problem as a Constrained Quadratic Model (CQM) and then submitting it to a quantum annealer. We highlight here the steps needed, as well as the implemented code, and provide solutions from a Chicken and Waffle restaurant menu. Additionally, we discuss how this model may be generalized to find optimal drug molecules within a large search space with many complex, and often contradictory, structures and property constraints.

arXiv:2303.15419Mar 27, 20231 citation

Optimizing the Production of Test Vehicles Using Hybrid Constrained Quantum Annealing

Adam Glos, Akash Kundu, Özlem Salehi

Abstract Optimization of pre-production vehicle configurations is one of the challenges in the automotive industry. Given a list of tests requiring cars with certain features, it is desirable to find the minimum number of cars that cover the tests and obey the configuration rules. In this paper, we model the problem in the framework of satisfiability and solve it utilizing the newly introduced hybrid constrained quadratic model (CQM) solver provided by D-Wave. The problem definition is based on the “Optimizing the Production of Test Vehicles” use-case given in the BMW quantum computing challenge. We formulate a constrained quadratic model for the problem and use a greedy algorithm to configure the cars. We benchmark the results obtained from the CQM solver with the results from the classical solvers like coin-or branch and cut and Gurobi solver. We conclude that the performance of the CQM solver is comparable to the classical solvers in optimizing the number of test vehicles, given the noise-prone quantum hardware. However, the CQM solver takes much more time, which prohibits obtaining useful quantum advantages. As an extension to the problem, we describe how the scheduling of the tests can be incorporated into the model.

arXiv:2203.15421SN Computer ScienceAug 11, 202310 citations

A Use-Case-Oriented Benchmark Framework for Classical, Quantum, Hybrid, and Quantum-Inspired Optimization

Dominik Leib, Tobias Seidel, Sebastian Velten +1 more

Abstract As interest in quantum and related optimization paradigms continues to grow, fairly and systematically comparing their performance across practical problem settings remains challenging. This challenge arises because these approaches often target different problem classes, use different mathematical representations, and are affected differently by modeling choices. As a result, observed performance depends not only on the solver itself, but also on how a problem is formulated, reformulated, and translated into a solver-specific input language. This work presents a publicly available and extensible benchmarking framework that unifies advances in quantum, quantum-hybrid, quantum-inspired, and classical optimization by enabling consistent comparison across use cases, solvers, and models. We address the diversity of solver “languages”—from mixed-integer programming (MIP) formulations for branch-and-bound methods over quadratic unconstrained binary optimization (QUBO) models for quantum annealers to constrained quadratic models (CQM) for hybrid approaches — as well as the influence of modeling choices, such as binary encodings and penalty formulations, on both performance and solution fidelity. By supporting systematic variation across the three dimensions of use case, solver, and model, the framework reveals trade-offs that single-dimension benchmarks overlook, clarifies when native formulations are preferable, and enables rigorous evaluation of practical combinatorial optimization problems. The two case studies, vehicle routing and maximum cut, illustrate this principle: their contrasting outcomes show that the effectiveness of a solver depends strongly on how well the chosen model representation matches the solver backend and the use case.

Jun 15, 20260 citations