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

IEEE International Conference on Consumer Electronics - Taiwan (ICCE-Taiwan)

Gaussian Process Bayesian Optimization for QUBO Penalty Weight Auto-Setting on a Distributed Quantum and Quantum-Inspired Annealing Platform

Jehn‐Ruey Jiang, Dai-Lun Chiang, Wen‐Han Huang

Published Jul 1, 2026• 0 citations
Publisher

Abstract

This paper proposes the use of Gaussian process Bayesian optimization (GPBO) to address the challenging problem of penalty weight auto-setting (PWAS) in quadratic unconstrained binary optimization (QUBO) formulations on a distributed quantum and quantum-inspired annealing platform called National Central University Annealer (NCUA). The GPBO approach is compared with a PWAS method, namely maximum QUBO coefficient (MQC), to show its superiority.

DOI
10.1109/icce-taiwan71481.2026.11652773

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•5 citations

Bayesian Optimization for Simulated Annealing (BOSA) applied to the Capacitated Vehicle Routing Problem

Anupam Garg, Prateek Vishnoi

The Capacitated Vehicle Routing Problem (CVRP) involves finding the shortest possible routes for a fleet of vehicles, each with a fixed capacity limit, to serve a set of customers where every customer is visited exactly once. When CVRP is encoded as a Quadratic Unconstrained Binary Optimization (QUBO) model, one of the biggest practical hurdles is setting the penalty coefficients correctly — a process that is typically done by hand and has to be repeated for every new problem instance. This paper introduces a new technique called BOSA (Bayesian Optimization for Simulated Annealing), a framework that removes this manual step by using Gaussian Process-based Bayesian Optimization to find good penalty values automatically, while the underlying QUBO is solved using Simulated Annealing. Our hybrid approach integrates multi-start greedy construction and 2-opt local search to ensure solution feasibility when SA produces invalid routes. Experiments on 11 benchmark instances demonstrate solution distances of 12.04%- 33.26% relative to the best-known optima. On the two instances where comparison is possible, our proposed technique, BOSA achieves shorter routes than D-Wave (949 vs 1085 for A-n32-k5, and 2240 vs 2660 for A-n80-k10), suggesting that automated classical penalty tuning can match or exceed commercial quantum annealing solutions on these problem sizes without requiring quantum resources. Although not competitive with state-of-the-art CVRP solvers such as HGS and branch and cut algorithm, our automated tuning framework provides a foundation for future quantum-classical hybrid algorithms. It demonstrates the viability of BO-driven parameter optimization for QUBO-based combinatorial problems.

International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence (ISMSI)•Apr 24, 2026•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•4 citations

Formulation-Level Auto-Tuning for QUBO-Based Machine Learning: A Case Study Across Multiple Quantum-Inspired Annealers

Naoya Mizuki, Takahiro Katagiri, Daichi Mukunoki +1 more

This paper presents an Optuna-based formulation-level auto-tuning framework for support vector machines (SVMs) implemented on multiple quantum-inspired annealers. In an annealing-based SVM, continuous dual variables are discretized and converted into a quadratic unconstrained binary optimization (QUBO) model. This transformation introduces three coupled classes of parameters: representation parameters-the encoding base B and bit depth K-which determine numerical range, resolution, and QUBO size; the RBF kernel parameter γ, which determines classifier geometry; and the equality-constraint penalty ξ, which controls feasibility and coefficient balance. We formulate their joint selection as a mixed discrete-continuous black-box optimization problem. The framework has two optimization levels: an inner annealer minimizes the generated QUBO, while an outer Optuna loop reconstructs the formulation in every trial and maximizes validation accuracy. The same solver-agnostic procedure is applied to Fixstars Amplify Annealing Engine, Toshiba SQBM+, and Fujitsu Digital Annealer using TPE and Gaussian-process samplers and is compared with conventional grid search. Experiments on linear and nonlinear classification tasks with 0-20% label noise show mean gains over grid search of approximately 0.8 and 2.1 percentage points, respectively. The results demonstrate that formulation quality and backend capability must be evaluated jointly and that task-level feedback can compensate for discretization, penalty imbalance, and backend-dependent approximate optimization.

arXiv:2607.18774•Jul 21, 2026•0 citations

A QUBO Model for Gaussian Process Variance Reduction

Lorenzo Bottarelli, Alessandro Farinelli

Gaussian Processes are used in many applications to model spatial phenomena. Within this context, a key issue is to decide the set of locations where to take measurements so as to obtain a better approximation of the underlying function. Current state of the art techniques select such set to minimize the posterior variance of the Gaussian process. We explore the feasibility of solving this problem by proposing a novel Quadratic Unconstrained Binary Optimization (QUBO) model. In recent years this QUBO formulation has gained increasing attention since it represents the input for the specialized quantum annealer D-Wave machines. Hence, our contribution takes an important first step towards the sampling optimization of Gaussian processes in the context of quantum computation. Results of our empirical evaluation shows that the optimum of the QUBO objective function we derived represents a good solution for the above mentioned problem. In fact we are able to obtain comparable and in some cases better results than the widely used submodular technique.

arXiv:1901.10982•Jan 30, 2019•2 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
This paper proposes the use of Gaussian process Bayesian optimization (GPBO) to address the challenging problem of penalty weight auto-setting (PWAS) in quadratic unconstrained binary optimization (QUBO) formulations on a distributed quantum and quantum-inspired annealing platform called National Central University Annealer (NCUA). The GPBO approach is compared with a PWAS method, namely maximum QUBO coefficient (MQC), to show its superiority.
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.
The Capacitated Vehicle Routing Problem (CVRP) involves finding the shortest possible routes for a fleet of vehicles, each with a fixed capacity limit, to serve a set of customers where every customer is visited exactly once. When CVRP is encoded as a Quadratic Unconstrained Binary Optimization (QUBO) model, one of the biggest practical hurdles is setting the penalty coefficients correctly — a process that is typically done by hand and has to be repeated for every new problem instance. This paper introduces a new technique called BOSA (Bayesian Optimization for Simulated Annealing), a framework that removes this manual step by using Gaussian Process-based Bayesian Optimization to find good penalty values automatically, while the underlying QUBO is solved using Simulated Annealing. Our hybrid approach integrates multi-start greedy construction and 2-opt local search to ensure solution feasibility when SA produces invalid routes. Experiments on 11 benchmark instances demonstrate solution distances of 12.04%- 33.26% relative to the best-known optima. On the two instances where comparison is possible, our proposed technique, BOSA achieves shorter routes than D-Wave (949 vs 1085 for A-n32-k5, and 2240 vs 2660 for A-n80-k10), suggesting that automated classical penalty tuning can match or exceed commercial quantum annealing solutions on these problem sizes without requiring quantum resources. Although not competitive with state-of-the-art CVRP solvers such as HGS and branch and cut algorithm, our automated tuning framework provides a foundation for future quantum-classical hybrid algorithms. It demonstrates the viability of BO-driven parameter optimization for QUBO-based combinatorial problems.
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.
This paper presents an Optuna-based formulation-level auto-tuning framework for support vector machines (SVMs) implemented on multiple quantum-inspired annealers. In an annealing-based SVM, continuous dual variables are discretized and converted into a quadratic unconstrained binary optimization (QUBO) model. This transformation introduces three coupled classes of parameters: representation parameters-the encoding base B and bit depth K-which determine numerical range, resolution, and QUBO size; the RBF kernel parameter γ, which determines classifier geometry; and the equality-constraint penalty ξ, which controls feasibility and coefficient balance. We formulate their joint selection as a mixed discrete-continuous black-box optimization problem. The framework has two optimization levels: an inner annealer minimizes the generated QUBO, while an outer Optuna loop reconstructs the formulation in every trial and maximizes validation accuracy. The same solver-agnostic procedure is applied to Fixstars Amplify Annealing Engine, Toshiba SQBM+, and Fujitsu Digital Annealer using TPE and Gaussian-process samplers and is compared with conventional grid search. Experiments on linear and nonlinear classification tasks with 0-20% label noise show mean gains over grid search of approximately 0.8 and 2.1 percentage points, respectively. The results demonstrate that formulation quality and backend capability must be evaluated jointly and that task-level feedback can compensate for discretization, penalty imbalance, and backend-dependent approximate optimization.
Gaussian Processes are used in many applications to model spatial phenomena. Within this context, a key issue is to decide the set of locations where to take measurements so as to obtain a better approximation of the underlying function. Current state of the art techniques select such set to minimize the posterior variance of the Gaussian process. We explore the feasibility of solving this problem by proposing a novel Quadratic Unconstrained Binary Optimization (QUBO) model. In recent years this QUBO formulation has gained increasing attention since it represents the input for the specialized quantum annealer D-Wave machines. Hence, our contribution takes an important first step towards the sampling optimization of Gaussian processes in the context of quantum computation. Results of our empirical evaluation shows that the optimum of the QUBO objective function we derived represents a good solution for the above mentioned problem. In fact we are able to obtain comparable and in some cases better results than the widely used submodular technique.
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.