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

Asia-Pacific Conference on Communications (APCC)

Optimization of Penalty Weights in Quantum Annealing for Dynamic Spectrum Allocation

Yuhi Kurebayashi, Yui Yamashita, Yoshito Tobe

Published Nov 26, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.23919/apcc64555.2025.11279889

Related papers

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

Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer

Marcos Diez García, Mayowa Ayodele, Alberto Moraglio

Quadratic unconstrained binary optimisation (QUBO) problems is a general class of combinatorial optimisation problems, which regained popularity after recent advances in quantum computing. Quantum-inspired technologies like Fujitsu's Digital Annealer (DA), based on simulated annealing, can solve QUBO problems much faster than traditional computers. Penalty methods can convert constrained optimisation problems into QUBO problems. However, existing exact methods of determining penalty weights are limited to specific QUBO problems and require manual analysis by experts in QUBO. Empirical methods are general but become computationally prohibitive for large problem sizes and do not guarantee that penalty weights preserve the feasibility of global optima. We present a simple, efficient, general method applicable to any QUBO to determine exact penalty weights. Such weights are simple upper-bounds of the smallest penalty weight guaranteeing that unconstrained global optima are the same as the feasible global optima. These bounds can be iteratively improved by sequential penalty methods which we also present. Experimental results with the DA on minimum cut, travelling salesman and multi-dimensional knapsack problems show the viability of the novel methodology hybridising exact and sequential methods. This work contributes towards general, automatic and scalable penalty methods in QUBO.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•24 citations

Exact and sequential penalty weights in quadratic unconstrained binary optimisation with a digital annealer

MD Garcia (21941009), M Ayodele (21491936), A Moraglio (21844982)

Quadratic unconstrained binary optimisation (QUBO) problems is a general class of combinatorial optimisation problems, which regained popularity after recent advances in quantum computing. Quantum-inspired technologies like Fujitsu’s Digital Annealer (DA), based on simulated annealing, can solve QUBO problems much faster than traditional computers. Penalty methods can convert constrained optimisation problems into QUBO problems. However, existing exact methods of determining penalty weights are limited to specific QUBO problems and require manual analysis by experts in QUBO. Empirical methods are general but become computationally prohibitive for large problem sizes and do not guarantee that penalty weights preserve the feasibility of global optima. We present a simple, efficient, general method applicable to any QUBO to determine exact penalty weights. Such weights are simple upper-bounds of the smallest penalty weight guaranteeing that unconstrained global optima are the same as the feasible global optima. These bounds can be iteratively improved by sequential penalty methods which we also present. Experimental results with the DA on minimum cut, travelling salesman and multi-dimensional knapsack problems show the viability of the novel methodology hybridising exact and sequential methods. This work contributes towards general, automatic and scalable penalty methods in QUBO.

•Aug 1, 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

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo, Juan Marcos Ramírez, Farzam Nosrati +3 more

Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.

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

Evaluation of Sensitivity Analysis of Penalty Weights in QUBO

Jiajie Liu, Alberto Moraglio

This paper evaluates a framework which automatically sets penalty weights in QUBO (Quadratic Unconstrained Binary Optimization) through constraint sensitivity analysis. Combinatorial optimization problems need to be converted to QUBO form before being solved on quantum computers. Traditional QUBO models often use uniform penalty weights across constraints. The challenge of setting multiple penalty weights is that the weight combinations grow exponentially with the number of constraints. The proposed method first applies an exact and sequential method to obtain an initial weight, then adjusts individual weights based on their sensitivity, measured by the effect on the objective function. The constraint sensitivity analysis method was introduced very recently, and only preliminarily tested [10]. In this paper, we extend it to work on multiple (more than 2) constraints and test it on a wider problem benchmark. Experimental evaluations on the Quadratic Assignment Problem, Traveling Salesman Problem, and p-Median Facility Location Problem instances are presented. Results demonstrate that compared with Optuna and existing exact and sequential frameworks, the constraint sensitivity analysis method achieves superior solution quality and lower deviation from the optimal while maintaining acceptable feasibility rates.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•3 citations
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.
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.
Quadratic unconstrained binary optimisation (QUBO) problems is a general class of combinatorial optimisation problems, which regained popularity after recent advances in quantum computing. Quantum-inspired technologies like Fujitsu's Digital Annealer (DA), based on simulated annealing, can solve QUBO problems much faster than traditional computers. Penalty methods can convert constrained optimisation problems into QUBO problems. However, existing exact methods of determining penalty weights are limited to specific QUBO problems and require manual analysis by experts in QUBO. Empirical methods are general but become computationally prohibitive for large problem sizes and do not guarantee that penalty weights preserve the feasibility of global optima. We present a simple, efficient, general method applicable to any QUBO to determine exact penalty weights. Such weights are simple upper-bounds of the smallest penalty weight guaranteeing that unconstrained global optima are the same as the feasible global optima. These bounds can be iteratively improved by sequential penalty methods which we also present. Experimental results with the DA on minimum cut, travelling salesman and multi-dimensional knapsack problems show the viability of the novel methodology hybridising exact and sequential methods. This work contributes towards general, automatic and scalable penalty methods in QUBO.
Quadratic unconstrained binary optimisation (QUBO) problems is a general class of combinatorial optimisation problems, which regained popularity after recent advances in quantum computing. Quantum-inspired technologies like Fujitsu’s Digital Annealer (DA), based on simulated annealing, can solve QUBO problems much faster than traditional computers. Penalty methods can convert constrained optimisation problems into QUBO problems. However, existing exact methods of determining penalty weights are limited to specific QUBO problems and require manual analysis by experts in QUBO. Empirical methods are general but become computationally prohibitive for large problem sizes and do not guarantee that penalty weights preserve the feasibility of global optima. We present a simple, efficient, general method applicable to any QUBO to determine exact penalty weights. Such weights are simple upper-bounds of the smallest penalty weight guaranteeing that unconstrained global optima are the same as the feasible global optima. These bounds can be iteratively improved by sequential penalty methods which we also present. Experimental results with the DA on minimum cut, travelling salesman and multi-dimensional knapsack problems show the viability of the novel methodology hybridising exact and sequential methods. This work contributes towards general, automatic and scalable penalty methods in QUBO.
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.
Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.
This paper evaluates a framework which automatically sets penalty weights in QUBO (Quadratic Unconstrained Binary Optimization) through constraint sensitivity analysis. Combinatorial optimization problems need to be converted to QUBO form before being solved on quantum computers. Traditional QUBO models often use uniform penalty weights across constraints. The challenge of setting multiple penalty weights is that the weight combinations grow exponentially with the number of constraints. The proposed method first applies an exact and sequential method to obtain an initial weight, then adjusts individual weights based on their sensitivity, measured by the effect on the objective function. The constraint sensitivity analysis method was introduced very recently, and only preliminarily tested [10]. In this paper, we extend it to work on multiple (more than 2) constraints and test it on a wider problem benchmark. Experimental evaluations on the Quadratic Assignment Problem, Traveling Salesman Problem, and p-Median Facility Location Problem instances are presented. Results demonstrate that compared with Optuna and existing exact and sequential frameworks, the constraint sensitivity analysis method achieves superior solution quality and lower deviation from the optimal while maintaining acceptable feasibility rates.