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

arXiv:1811.03829 · Physical review. E

Quadratic unconstrained binary optimization formulation for rectified-linear-unit-type functions

Go Sato, Makiko Konoshima, Takuya Ohwa, Hirotaka Tamura, Jun Ohkubo

Published Apr 4, 2019• 7 citations
arXivHTMLPDF

Abstract

We propose a quadratic unconstrained binary optimization (QUBO) formulation of rectified-linear-unit (ReLU) type functions. Different from the q-loss function proposed by Denchev et al. [in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, edited by J. Langford and J. Pineau (Omnipress, Madison, USA, 2012)], a simple discussion based on the Legendre duality is not sufficient to obtain the QUBO formulation of ReLU-type functions. In addition to the Legendre duality, we employ the Wolfe duality, and the QUBO formulation of ReLU type is derived. The QUBO formulation is available in Ising-type annealing methods, including quantum annealing machines.

DOI
10.1103/physreve.99.042106

Related papers

Derivation of QUBO Formulations for Sparse Estimation

Tomohiro Yokota, Makiko Konoshima, Hirotaka Tamura +1 more

We propose a quadratic unconstrained binary optimization (QUBO) formulation of the l1-norm, which enables us to perform sparse estimation of Ising-type annealing methods such as quantum annealing. The QUBO formulation is derived using the Legendre transformation and the Wolfe theorem, which have recently been employed to derive the QUBO formulations of ReLU-type functions. It is shown that a simple application of the derivation method to the l1-norm case results in a redundant variable. Finally a simplified QUBO formulation is obtained by removing the redundant variable.

arXiv:2001.03715•Journal of the Physical Society of Japan•Feb 27, 2020•2 citations

Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions

Hyakka Nakada, Shu Tanaka

Quantum Annealing (QA) can efficiently solve combinatorial optimization problems whose objective functions are represented by Quadratic Unconstrained Binary Optimization (QUBO) formulations. For broader applicability of QA, quadratization methods are used to transform higher-order problems into QUBOs. However, quadratization methods for complex problems involving Machine Learning (ML) remain largely unknown. In these problems, strong nonlinearity and dense interactions prevent conventional methods from being applied. Therefore, we model target functions by the sum of rectified linear unit bases, which not only have the ability of universal approximation, but also have an equivalent quadratic-polynomial representation. In this study, the proof of concept is verified both numerically and analytically. In addition, by combining QA with the proposed quadratization, we design a new black-box optimization scheme, in which ML surrogate regressors are inputted to QA after the quadratization process.

arXiv:2506.08448•Journal of the Physical Society of Japan•Jul 28, 2025•2 citations

A Tutorial on Formulating and Using QUBO Models

Fred Glover, Gary A. Kochenberger, Yu Du

The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing. Through these connections, QUBO models lie at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. Computational experience is being amassed by both the classical and the quantum computing communities that highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. This tutorial discloses the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. We show how many different types of constraining relationships arising in practice can be embodied within the "unconstrained" QUBO formulation in a very natural manner using penalty functions, yielding exact model representations in contrast to the approximate representations produced by customary uses of penalty functions. Each step of generating such models is illustrated in detail by simple numerical examples, to highlight the convenience of using QUBO models in numerous settings. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.

arXiv:1811.11538•Nov 13, 2018•164 citations

Compressed sensing based on QUBO formulation

Kazue Kudo

Abstract Ising machines efficiently solve the combinatorial optimization problems described by the Ising model or the quadratic unconstrained binary optimization (QUBO) formulation. A hybrid method based on the QUBO formulation for compressed sensing is proposed. The proposed method comprises alternative steps of discrete and continuous optimization. In the discrete optimization step, the objective function is described by the QUBO formulation. Successful examples obtained via the proposed method are demonstrated. The performance of the proposed method depends highly on the initial conditions.

Journal of Physics Conference Series•Mar 1, 2022•1 citation

Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network

Yuta Shikuri

Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on 16 instances, ranging from 37 to 223 variables, demonstrate that our approach requires fewer binary variables than quadratization by orders of magnitude. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.

arXiv:2006.06926•Proceedings of the AAAI Conference on Artificial Intelligence•Apr 11, 2025•5 citations

Sparse Signal Reconstruction with QUBO Formulation in l0-regularized Linear Regression

Ide, Naoki, Masayuki Ohzeki

An l0-regularized linear regression for a sparse signal reconstruction is implemented based on the quadratic unconstrained binary optimization (QUBO) formulation. In this method, the signal values are quantized and expressed as bit sequences. By transforming l0-norm to a quadratic form of these bits, the fully quadratic objective function is provided and optimized by the solver specialized for QUBO, such as the quantum annealer. Numerical experiments with a commercial quantum annealer show that the proposed method performs slightly better than conventional methods based on orthogonal matching pursuit (OMP) and the least absolute shrinkage and selection operator (LASSO) under several limited conditions.

arXiv:2202.00452•Jan 31, 2022•1 citation
We propose a quadratic unconstrained binary optimization (QUBO) formulation of rectified-linear-unit (ReLU) type functions. Different from the q-loss function proposed by Denchev et al. [in Proceedings of the 29th International Conference on Machine Learning, Edinburgh, edited by J. Langford and J. Pineau (Omnipress, Madison, USA, 2012)], a simple discussion based on the Legendre duality is not sufficient to obtain the QUBO formulation of ReLU-type functions. In addition to the Legendre duality, we employ the Wolfe duality, and the QUBO formulation of ReLU type is derived. The QUBO formulation is available in Ising-type annealing methods, including quantum annealing machines.
We propose a quadratic unconstrained binary optimization (QUBO) formulation of the l1-norm, which enables us to perform sparse estimation of Ising-type annealing methods such as quantum annealing. The QUBO formulation is derived using the Legendre transformation and the Wolfe theorem, which have recently been employed to derive the QUBO formulations of ReLU-type functions. It is shown that a simple application of the derivation method to the l1-norm case results in a redundant variable. Finally a simplified QUBO formulation is obtained by removing the redundant variable.
Quantum Annealing (QA) can efficiently solve combinatorial optimization problems whose objective functions are represented by Quadratic Unconstrained Binary Optimization (QUBO) formulations. For broader applicability of QA, quadratization methods are used to transform higher-order problems into QUBOs. However, quadratization methods for complex problems involving Machine Learning (ML) remain largely unknown. In these problems, strong nonlinearity and dense interactions prevent conventional methods from being applied. Therefore, we model target functions by the sum of rectified linear unit bases, which not only have the ability of universal approximation, but also have an equivalent quadratic-polynomial representation. In this study, the proof of concept is verified both numerically and analytically. In addition, by combining QA with the proposed quadratization, we design a new black-box optimization scheme, in which ML surrogate regressors are inputted to QA after the quadratization process.
The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing. Through these connections, QUBO models lie at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. Computational experience is being amassed by both the classical and the quantum computing communities that highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. This tutorial discloses the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. We show how many different types of constraining relationships arising in practice can be embodied within the "unconstrained" QUBO formulation in a very natural manner using penalty functions, yielding exact model representations in contrast to the approximate representations produced by customary uses of penalty functions. Each step of generating such models is illustrated in detail by simple numerical examples, to highlight the convenience of using QUBO models in numerous settings. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.
Abstract Ising machines efficiently solve the combinatorial optimization problems described by the Ising model or the quadratic unconstrained binary optimization (QUBO) formulation. A hybrid method based on the QUBO formulation for compressed sensing is proposed. The proposed method comprises alternative steps of discrete and continuous optimization. In the discrete optimization step, the objective function is described by the QUBO formulation. Successful examples obtained via the proposed method are demonstrated. The performance of the proposed method depends highly on the initial conditions.
Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on 16 instances, ranging from 37 to 223 variables, demonstrate that our approach requires fewer binary variables than quadratization by orders of magnitude. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.
An l0-regularized linear regression for a sparse signal reconstruction is implemented based on the quadratic unconstrained binary optimization (QUBO) formulation. In this method, the signal values are quantized and expressed as bit sequences. By transforming l0-norm to a quadratic form of these bits, the fully quadratic objective function is provided and optimized by the solver specialized for QUBO, such as the quantum annealer. Numerical experiments with a commercial quantum annealer show that the proposed method performs slightly better than conventional methods based on orthogonal matching pursuit (OMP) and the least absolute shrinkage and selection operator (LASSO) under several limited conditions.