Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Optimal Penalty Weights for CQM-to-BQM Conversion]{Towards QPU-only Quantum Annealing: Optimal Penalty Weights for CQM-to-BQM Conversion

Junwhan Cho, Minjae Lee, Insung Kim, Dongjin Lee

Published Apr 1, 2026• 0 citations
Publisher

Abstract

Abstract Quantum Annealing hardware, particularly D-Wave systems, requires problems to be formulated as Binary Quadratic Models (BQM). While hybrid solvers support Constrained Quadratic Models (CQM) with native constraint handling, Quantum Processing Unit-only execution remains an important research direction. CQMs can be transformed into BQMs by encoding constraints as penalty terms, with weights controlling the trade-off between optimization and constraint satisfaction. However, optimal penalty weight selection for general CQM-to-BQM transformation remains underexplored. This work investigates optimal penalty weights for such transformations. We focus on a restricted class of CQMs where constraints follow a specific structural form while the objective function remains general, and experimentally determine optimal weights using classical solvers. We present methods for encoding these constraints and conduct experiments to examine how optimal penalty weights vary with problem scale and constraint count. Through comprehensive analysis, we identify patterns and relationships that provide practical guidance for penalty weight selection.

DOI
10.21203/rs.3.rs-8842888/v1

Related papers

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

Wiwat Asawalertsak, Prapong Prechaprapranwong, Rajchawit Sarochawikasit

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.

International Joint Conference on Computer Science and Software Engineering•Nov 2, 2025•0 citations

Towards QPU-only Quantum Annealing: Optimal Penalty Weights for CQM-to-BQM Conversion

Junhwan Cho, MinJae Lee, Insung Kim +1 more

ACM Symposium on Applied Computing•Mar 23, 2026•0 citations

A Framework for Automatically Setting Multiple Penalty Weights in Quadratic Unconstrained Binary Optimization

Jiajie Liu, Alberto Moraglio

This paper proposes a novel framework for automatically setting penalty weights in the Quadratic Unconstrained Binary Optimization (QUBO) to handle problems with multiple constraints. Quantum computing and quantum-inspired methods have gained prominence, with QUBO models widely used for their unified representation of optimization problems. However, QUBO performance is highly sensitive to penalty weight settings, especially in multiple constraints scenarios, where setting different penalty weights to different constraints may further affect performance. Existing methods for setting common penalty weights for all constraints in QUBO can be generally categorized into manual methods based on expert experience, exact methods based on the objective function values, and sequential methods based on searching within an upper bound. This study introduces a novel framework for multiple constraints optimization that utilizes exact and sequential binary search methods to determine common penalty weight while integrating constraint sensitivity analysis to adjust each penalty weight dynamically. This approach enhances the efficiency and quality of QUBO solutions. Experimental results on the Travelling Salesman Problem show that the proposed framework achieves superior solution quality and feasibility on both the D-Wave quantum annealer and classical simulated annealing solvers, outperforming traditional methods and demonstrating strong adaptability.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•3 citations

Simple Constraint Embedding for Quantum Annealers

Tomáš Vyskočil, Hristo N. Djidjev

Quantum annealers such as the D-Wave 2X computer are designed to natively solve Quadratic Unconstrained Binary Optimization (QUBO) problems to optimality or near optimality. Most NP-hard problems, which are hard for classical computers, can be naturally described as quadratic binary problems that contain a quadratic binary objective function and one or more constraints. Since a QUBO cannot have constraints, each such constraint has to be added to the objective function as a penalty, in order to solve on D-Wave. For a minimization problem, for instance, such penalty can be a quadratic term that gets a value zero, if the constraint is satisfied, and a large value, if it is not. In many cases, however, the penalty can significantly increase the number of quadratic terms in the resulting QUBO and make it too large to embed into the D-Wave hardware. In this paper, we develop an alternative method for formulating and embedding constraints of the type Σi=1sxi=1, which is much more scalable than the existing ones, and analyze the properties of the resulting embeddings.

IEEE International Conference on Rebooting Computing (ICRC)•Nov 1, 2018•9 citations

Optimization of Penalty Weights in Quantum Annealing for Dynamic Spectrum Allocation

Yuhi Kurebayashi, Yui Yamashita, Yoshito Tobe

Quantum annealing offers a powerful means to solve combinatorial optimization problems formulated as Quadratic Unconstrained Binary Optimization (QUBO). In constrained problems, appropriate penalty weights are critical: too small yields infeasibility, too large harms solution quality. This paper proposes a rigorous method to determine lower bounds for penalty weights, ensuring constraint satisfaction without degrading optimization. Applied to the Dynamic Spectrum Allocation (DSA) problem with priority-aware extensions, the method leverages iterative quantum annealing to reduce tuning overhead. Experiments show improved efficiency and feasibility over conventional approaches.

Asia-Pacific Conference on Communications (APCC)•Nov 26, 2025•0 citations

Automaton-based methodology for implementing optimization constraints for quantum annealing

Hristo N. Djidjev

Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.

ACM International Conference on Computing Frontiers (CF)•May 11, 2020•1 citation
Abstract Quantum Annealing hardware, particularly D-Wave systems, requires problems to be formulated as Binary Quadratic Models (BQM). While hybrid solvers support Constrained Quadratic Models (CQM) with native constraint handling, Quantum Processing Unit-only execution remains an important research direction. CQMs can be transformed into BQMs by encoding constraints as penalty terms, with weights controlling the trade-off between optimization and constraint satisfaction. However, optimal penalty weight selection for general CQM-to-BQM transformation remains underexplored. This work investigates optimal penalty weights for such transformations. We focus on a restricted class of CQMs where constraints follow a specific structural form while the objective function remains general, and experimentally determine optimal weights using classical solvers. We present methods for encoding these constraints and conduct experiments to examine how optimal penalty weights vary with problem scale and constraint count. Through comprehensive analysis, we identify patterns and relationships that provide practical guidance for penalty weight selection.
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.
This paper proposes a novel framework for automatically setting penalty weights in the Quadratic Unconstrained Binary Optimization (QUBO) to handle problems with multiple constraints. Quantum computing and quantum-inspired methods have gained prominence, with QUBO models widely used for their unified representation of optimization problems. However, QUBO performance is highly sensitive to penalty weight settings, especially in multiple constraints scenarios, where setting different penalty weights to different constraints may further affect performance. Existing methods for setting common penalty weights for all constraints in QUBO can be generally categorized into manual methods based on expert experience, exact methods based on the objective function values, and sequential methods based on searching within an upper bound. This study introduces a novel framework for multiple constraints optimization that utilizes exact and sequential binary search methods to determine common penalty weight while integrating constraint sensitivity analysis to adjust each penalty weight dynamically. This approach enhances the efficiency and quality of QUBO solutions. Experimental results on the Travelling Salesman Problem show that the proposed framework achieves superior solution quality and feasibility on both the D-Wave quantum annealer and classical simulated annealing solvers, outperforming traditional methods and demonstrating strong adaptability.
Quantum annealers such as the D-Wave 2X computer are designed to natively solve Quadratic Unconstrained Binary Optimization (QUBO) problems to optimality or near optimality. Most NP-hard problems, which are hard for classical computers, can be naturally described as quadratic binary problems that contain a quadratic binary objective function and one or more constraints. Since a QUBO cannot have constraints, each such constraint has to be added to the objective function as a penalty, in order to solve on D-Wave. For a minimization problem, for instance, such penalty can be a quadratic term that gets a value zero, if the constraint is satisfied, and a large value, if it is not. In many cases, however, the penalty can significantly increase the number of quadratic terms in the resulting QUBO and make it too large to embed into the D-Wave hardware. In this paper, we develop an alternative method for formulating and embedding constraints of the type Σi=1sxi=1, which is much more scalable than the existing ones, and analyze the properties of the resulting embeddings.
Quantum annealing offers a powerful means to solve combinatorial optimization problems formulated as Quadratic Unconstrained Binary Optimization (QUBO). In constrained problems, appropriate penalty weights are critical: too small yields infeasibility, too large harms solution quality. This paper proposes a rigorous method to determine lower bounds for penalty weights, ensuring constraint satisfaction without degrading optimization. Applied to the Dynamic Spectrum Allocation (DSA) problem with priority-aware extensions, the method leverages iterative quantum annealing to reduce tuning overhead. Experiments show improved efficiency and feasibility over conventional approaches.
Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.