Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions
Hyakka Nakada 1,2 and Shu Tanaka 2,3,4,5 · 2025
Read Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions by Hyakka Nakada 1,2 and Shu Tanaka 2,3,4,5 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-08448.txt.
Introduction
Hyakka Nakada and Shu Tanaka work in 2025 on how to recast hard choice problems into a form that quantum annealers can solve. Those machines handle problems written with yes or no choices and pair terms only. Real problems in machine learning often have higher order terms and dense links, which the standard recasting tricks cannot handle.
The pair model the target with sums of a simple bent line function. That form can mimic any curve, and it also has an exact match in the pair term form the machines need. They prove the match holds and set out a step by step build. A clear, general route from messy problems to machine ready form would widen what quantum annealers can be tried on. The paper gives the math base for such a route.
Catalog record
| CREATOR | Hyakka Nakada 1,2 and Shu Tanaka 2,3,4,5 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-08448
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions Hyakka Nakada 1,2 and Shu Tanaka 2,3,4,5 Abstract 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. 1 Introduction Combinatorial optimization problems have numerous real-world applications, spanning diverse fields including logistics, materials science, and finance. In recent years, the size of these problems has increased with the volume of data traffic, which leads to the difficulty of solving them in a realistic time. To address this situation, quantum computing technology has been actively developed. Especially, Quantum Annealing (QA) [ 1 , 2 , 3 , 4 , 5 , 6 ] is a promising metaheuristic to obtain good solutions to combinatorial optimization problems efficiently. Some combinatorial optimization problems can be described by either the Ising model or Quadratic Unconstrained Binary Optimization (QUBO) formulations. The Ising model and QUBO are equivalent via a linear transformation of their variables. However, combinatorial optimization problems are generally formulated as High-Order Binary Optimization Problems (HOBO) [ 7 , 8 ] because numerous real-world phenomena exhibit strong nonlinearities. Thus, methods of quadratization [ 9 , 10 ] from HOBO to QUBO are widely studied to enable QA to handle such problems. Rosenberg’s method [ 11 ] is known to be one of the typical quadratization. More specifically, a product of two binary variables x_{i},x_{j}\ (\mathrm{for}\ i,j=1,2,\ldots,N) is replaced with an auxiliary binary variable y_{ij} along with a penalty term -\lambda(x_{i}x_{j}-2x_{i}y_{ij}-2x_{j}y_{ij}+3y_{ij}) for a maximization problem. Here, \lambda>0 and y_{ij}\in\{0,1\} denote the penalty coefficient and the auxiliary variable, respectively. N is the size of the problem. For sufficiently large \lambda , the penalty term enforces the binary variable assignments such that the constraint y_{ij}=x_{i}x_{j} is satisfied. This quadratization is iterated until all of the higher-order interactions are reduced to a quadratic polynomial. Several studies [ 9 , 12 ] have attempted to reduce the number of auxiliary variables by arranging the order of this quadratization. Figure 1: (Color online) Basic concept of QA-based black-box optimization by using ML surrogate regressors. Whereas conventional methods adopt ad-hoc QUBO regressors that can be directly input to QA, the ML regressors are usually higher-order nonlinear functions F(\bm{x}) , which requires quadratization process after training. Originally nonlinear regressors are quadratized to F(\bm{x},\bm{t}) by adding auxiliary variables \bm{t} . Here, (\bm{x},\bm{t})^{T} means transpose of a row vector in which \bm{x} and \bm{t} are concatenated, and Q is a QUBO matrix. Recently, much attention has been paid to the handling of strong nonlinearities in the field of Machine Learning (ML), such as surrogate regressors for a value function in reinforcement learning [ 13 ] and an acquisition function in Bayesian optimization [ 14 ] . For these black-box optimizations, good candidates can be predicted by searching for maximum points along the regressors. Finding such points is difficult when the black-box optimization treats a vast exploration space. QA has the potential to accelerate the optimization by efficiently searching for these candidates. However, because QA is specialized for handling QUBOs, the process of black-box optimization should be designed as shown in Fig. 1 . In other words, a quadratization step is essential to transfer trained regressors into QUBO forms because ML models are usually higher-order nonlinear. For example, they include non-polynomial basis such as Rectified Linear Unit (ReLU) function [ 15 ] and Radial Basis Function (RBF) kernel [ 16 ] . On the other hand, related studies on annealing-based black-box optimizations adopt surrogate regressors of a quadratic polynomial [ 17 , 18 , 19 , 20 , 21 , 22 ] . In these methods, the regressors can be directly inputted to QA without the quadratization step. However, as shown before, numerous real-world phenomena exhibit strong nonlinearities. For more practical and broader applicability, ML regressors with higher-order nonlinearity are desired as well as quadratic polynomials. Thus, as shown in Fig. 1 , we propose a new black-box optimization method. First, an ML regressor is trained with the available data. Then, the regressor is transferred into a QUBO form with a quadratization method. New candidates are selected with respect to an acquisition function based on the QUBO, by QA. Next, the scores of these candidates \bm{x} are evaluated. Training data (\bm{x},F_{0}(\bm{x})) are obtained and the regressor is retrained. Here, F_{0} means a true but unknown objective function to describe scores. These steps are repeated until the target score is achieved. The important issue in realizing this optimization is quadratization. Fortunately, in the discrete space \bm{x}\in X=\{0,1\}^{N} , many regressors can be reduced to a polynomial after expansion in a series thanks to x^{k}=x for any natural number k . For example, e^{x_{1}+x_{2}+x_{3}}=1+(e-1)(x_{1}+x_{2}+x_{3})+(e-1)^{2}(x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{1})+(e-1)^{3}x_{1}x_{2}x_{3} . However, since the number of monomials grows exponentially with the problem size N , directly encoding them to HOBO is difficult in a large problem. Similarly, encoding ML models is generally challenging. Even if they could be encoded, the subsequent transfer to QUBO becomes intractable with existing quadratization methods involving Rosenberg’s method because the quadratization is performed sequentially on each monomial. Therefore, in this study, the efficient quadratization step for such ML regressors is focused. The remainder of this paper is organized as follows. Section 2 provides a brief summary of related studies. Section 3 proposes our quadratization approach for dense and highly nonlinear functions involving ML regressors. Section 4 describes application to several typical ML regressors. Finally, Section 5 concludes this paper. 2 Related Work In this study, we propose a systematic and efficient QUBO formulation for functions with high-order and dense interactions involving ML regressors. Our target is maximizing F(\bm{x})=\sum^{K}_{k=1}c_{k}f(q_{k}(\bm{x})). (1) Here, we assume that q_{k}:\bm{x}\to R^{1} is a scalar map and f is a continuous nonlinear function. As shown later, many ML regressors are modeled by this type of function. As a standard technique for polynomial reduction, Piecewise-Linear Approximations (PLAs) [ 23 ] are well-established. However, PLAs for high-dimensional problems handled by ML remain largely unknown. Although ML models are not specifically targeted, several attempts to obtain QUBO formulations for activation functions have been reported. Previous studies [ 24 , 25 ] showed that ReLU functions R(q)\equiv\begin{cases}\begin{aligned} &0\ \text{for}\ q<0,\\ &x\ \text{for}\ q\geq 0\end{aligned}\end{cases} (2) can be transformed to R(q)=\max_{t\in[0,1]}\{tq\}. (3) t is the dual variable introduced through the Legendre transformation [ 26 ] , and ReLU functions become quadratic with respect to q,t . 3 Proposed Method We propose the following two quadratization methods for ML models. The first is to linearly discretize original functions by one-hot vectorization. The second