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.
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.
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.
The D_Wave quantum computer is an analog device that approximates optimal solutions to optimization problems. The traveling salesman problems in the TSP Library are too large to process on the D_Wave quantum computer DW_2000Q_6. We report favorable approximations for solving the smallest, symmetric traveling salesman problems in the TSP Library by two D_Wave hybrid solvers, Kerberos and LeapHybridSampler. This is useful work about results from new quantum tools on problems that have been studied. It is expected to show a quantum way forward with larger problems when the hardware is upgraded. Also this work demonstrates that the TSP Library is a source of benchmarks for quantum processing of combinatorial problems. The hybrid solvers combine quantum and classical methods in a manner that is D_Wave proprietary information. The results from Kerberos were closer to optimal than the results from LeapHybridSampler. We show that the error percent from optimal increases as the problem size increases, which is consistent with results on D-Wave_s quantum computer for other optimization problems. An appendix contains outcomes from the two hybrid solvers for two asymmetric traveling salesman problems that are in the TSP Library. Again, the Kerberos results were closer to optimal than those from LeapHybridSampler, which indicates that Kerberos is superior to LeapHybridSampler on traveling salesman problems.
The Traveling Salesman Problem is a classical NP-hard combinatorial optimization problem that has been extensively studied in operations research. A major challenge in Traveling Salesman Problem formulations is the large number of subtour elimination constraints required to ensure a valid tour. To address this issue, we adopt an iterative approach grounded in well-established operations research techniques, in which subtour elimination constraints are generated dynamically. In addition, we integrate a preprocessing phase to reduce the number of candidate arcs. In this work, we investigate both classical and quantum optimization approaches for solving the problem using the proposed framework. In particular, for quantum optimization we analyze quantum annealing techniques within the D-Wave framework, considering both direct quantum execution on the QPU and hybrid quantum classical solvers. Computational experiments show that the proposed strategies significantly reduce the model size and lead to positive improvements in computational performance across classical, direct quantum, and hybrid optimization approaches.
Academic and industrial sectors have been engaged in a fierce competition to develop quantum technologies, fueled by the explosive advancements in quantum hardware. While universal quantum computers have been shown to support up to hundreds of qubits, the scale of quantum annealers has reached three orders of magnitude (i.e., thousands of qubits). Therefore, quantum algorithms are becoming increasingly popular in a variety of fields, with optimization being one of the most prominent. This work aims to explore the topic of quantum optimization by comprehensively evaluating the technologies provided by D-Wave Systems. To do so, a model for the energy optimization of data centers is proposed as a benchmark. D-Wave quantum and hybrid solvers are compared, in order to identify the most suitable one for the considered application. To highlight its advantageous performance capabilities and associated solving potential, the selected D-Wave hybrid solver is then contrasted with CPLEX, a highly efficient classical solver.
Abstract This paper benchmarks quantum, classical, and hybrid solvers on NP-hard Max-Cut and QUBO problems, emphasizing solution quality relative to known global optima. We evaluate D-Wave’s fast annealing QPU and Hybrid solver against classical simulated annealing (SA) and Toshiba’s simulated bifurcation machine (SBM) using 139 Max-Cut instances (100 to 10,000 nodes). For small instances ( ≤ ≤ 250 nodes) with known global optima, Hybrid and SA consistently achieve optimal solutions, outperforming the QPU. For larger instances, SBM and slower SA yield superior solutions, while Hybrid and faster SA perform less effectively. Computation time varies across solvers.
Quantum annealing is a recent advancement in the field of optimization metaheuristics. Quantum annealers such as the D-Wave machines are primarily designed for solving discrete optimization problems. Solving nonlinear continuous optimization problems is also a very challenging task, in particular when nonconvex functions and multiple local optima are involved; nevertheless, convex problems can be solved efficiently using standard classical methods. It has not been explored in sufficient detail how quantum annealing could help in solving continuous optimization problems. In this work, we develop a prototype quantum-inspired solver for nonlinear continuous optimization problems. The solver is hybrid, as it has two pathways - classical and quantum-inspired. Given a continuous optimization problem via the web-based graphical interface that enables users to define and edit optimization problems, our solver computes a nonconvexity index for the problem, which determines the solution pathway. Problems with low nonconvexity indices are sent through the classical pathway and solved by standard separable programming techniques, while the others are transformed into mixed integer linear programming (MILP) problems via separable reformulations, which are restated as quadratic unconstrained binary optimization (QUBO) problems - the problem format compatible for quantum annealers, and eventually sent through the quantum pathway using D-Wave’s Neal sampler.