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

Hyakka Nakada; Shu Tanaka

REVIEW 4 major objections 6 minor 43 references

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

T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Nonlinear ML surrogate functions can be rewritten as QUBO forms through ReLU expansions, letting quantum annealers optimize them directly.

desk verdict The GMM/KR sign-bit construction is a real contribution, but the neural-network extension relies on a binarization that flips the sign of positive pre-activations, so the paper's headline claim of covering ML regressors does not hold as written. read the letter →

arxiv 2506.08448 v1 pith:5HIZSS6Q submitted 2025-06-10 quant-ph cs.LG

Hyakka Nakada , Shu Tanaka This is my paper

classification quant-phcs.LG

keywords QUBOquadratizationReLUexpansionquantumannealingblack-boxoptimizationGaussianmixturemodelkernelregressorneuralnetwork

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to show that a broad class of machine-learning surrogate functions—Gaussian mixture models, RBF kernel regressors, and one-hidden-layer ReLU networks—can be converted into quadratic unconstrained binary optimization (QUBO) forms, so that a quantum annealer can maximize them. The key move is to approximate each nonlinearity by a polyline written as a sum of ReLU bases, because a ReLU of a linear function has a quadratic binary representation. The paper establishes that the conversion is systematic and counts the auxiliary binary variables it needs; for example, a ReLU network needs only $K_p'' + K_n'' \log_2 N$ extra binaries. It verifies the approximation numerically on random Gaussian mixtures. If correct, this removes a bottleneck for quantum-annealing-based black-box optimization, where previous surrogate models were limited to quadratic polynomials.

What carries the argument

The central object is the ReLU-expansion identity, Eq. (7), which rewrites a polyline approximation of $f$ as $\hat{f}(q)=a_0 q+b_0+\sum_{m=1}^{M}(a_m-a_{m-1})R(q-\alpha_m)$. Each ReLU term is then made quadratic by one of two exact encodings: for positive coefficients, $R(q)=\max_{t\in\{0,1\}} t\,q$ (the Legendre representation); for negative coefficients, $R(q)=z_D q$ with the signed-binary constraint $q \simeq A\left(1-2^D+\sum_{j=0}^{D}2^j z_j\right)$. The sign bit $z_D$ is the load-bearing variable: it detects whether the ReLU input is nonnegative and turns an otherwise hard max-min problem into a quadratic penalty term.

What would settle it

On a small random ReLU network with binary inputs, compute the true maximizer of $F_{\mathrm{NN}}(x)$ by brute force, encode the network with the Appendix B sign-binarization using $D=1$ or $D=2$, solve the resulting QUBO, and compare: any instance where the encoded maximizer differs from the true maximizer, or where changing $D$ changes the encoded maximizer, would show the sign-binarization does not always preserve the optimum.

Watch

Extended reading notes

Core claim

The paper claims that maximizing $F(x)=\sum_{k=1}^{K} c_k f(q_k(x))$, with continuous nonlinear $f$ and linear maps $q_k$, can be reduced to a QUBO maximization after $f$ is approximated by a ReLU-expanded polyline. Each ReLU term is rewritten quadratically: positive-coefficient terms use the Legendre representation $R(q)=\max_{t\in\{0,1\}} t\,q$, and negative-coefficient terms use the signed-binary identity $R(q)=z_D q$ with a penalty enforcing the bit encoding of $q$. The resulting expression, Eq. (14), is a quadratic maximization over the original binary variables $x$, the binary ReLU-selector variables $t_{k,m}$, and the sign-bit variables $z_{k,m,j}$, so a trained surrogate can be handed directly to quantum annealing. The paper verifies the polyline approximation numerically on random mixtures of Gaussians and derives auxiliary-variable counts showing the construction is feasible for GMMs, RBF kernel regressors, and ReLU networks.

Load-bearing premise

For neural networks, the paper assumes that a finite binary approximation of each ReLU input gets the sign right; if the bit width is too small or the scale is off, the encoded network's best solution can differ from the real network's best solution.

Editorial extensions

If this is right

Any trained surrogate expressible as a sum of ReLU bases can be fed directly to a quantum annealer as a QUBO, without sequential monomial quadratization.
GMMs with $K$ clusters need only $MK$ auxiliary binaries and zero penalty terms, so the ReLU-expansion method is cheaper than one-hot discretization when the number of polyline pieces $M$ is below the problem size $N$.
RBF kernel regressors need at most $MK_p' + MK_n' \log_2 N$ auxiliary binaries, and support-vector sparsity reduces the effective number of nonzero coefficients.
One-hidden-layer ReLU networks become QUBO-representable with $K_p'' + K_n'' D$ auxiliary binaries, independent of the number of polyline pieces $M$.
A quantum-annealing-based black-box optimization loop can therefore use strongly nonlinear surrogate regressors instead of being restricted to quadratic polynomial surrogates.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper: if the signed-binary encoding of Appendix B is equipped with an explicit error bound and penalty-coefficient guidance, the same construction could be applied to ReLU networks with continuous inputs, not just binary $x$.
Beyond the paper: the variable counts suggest a practical rule of thumb—use the ReLU-expansion method when the number of polyline pieces $M$ is below roughly $(N+1)/\log_2 N$ for kernel regressors with about half negative coefficients.
Beyond the paper: composing the expansion recursively on hidden layers would extend the method to deeper networks, at the cost of additional sign-bit variables per layer.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the ReLU-expansion construction for models with integer-valued arguments (GMM, RBF kernels) is a real and usable contribution; the neural-network extension is not. The binarization in Appendix B (Eq. B.1) doesn't preserve the sign of q, and the paper gives no error bound, so the NN row in Table II is unverified.

What's actually new: the sign-bit encoding for negative ReLU coefficients (Eq. 13 with Eq. 11) is a neat trick, and it is exact when the argument q is integer-valued (or of the form A(q_int - α)). The auxiliary-variable accounting for GMM and RBF kernel regression is systematic and the counts in Table II are plausible. The polyline approximation via ReLU bases is standard, but tying it to QUBO with this clean per-k, per-m treatment is a useful packaging.

Soft spots: the neural-network case (Section 4.3) relies on the approximate binarization (B.1). As written, the scaling factor C = max(|max q|/2^D, |min q|/2^D - 1) fails to cover the most negative values (e.g., min q = -100, D=4 gives coverage only down to -78.75). More seriously, for any positive q < C, the grid points with z_D=1 are at C or larger, so the squared penalty is minimized by setting z_D=0, which encodes a positive pre-activation as a non-positive value and flips the ReLU to 0. That breaks R(q)=z_D q for exactly the regime the sign bit is supposed to handle. No error bound or penalty-coefficient guidance is provided, and the numerical test only fits a scalar curve; it doesn't solve a QUBO or run a QA. The paper also doesn't ship code or data, so the NN claim is entirely unsupported.

The GMM and kernel parts look sound to me, and the integer-argument sign-bit construction is correct. But the paper's headline claim of covering 'ML regressors' leans heavily on the NN case, which is the part that doesn't work. I'd send this to a serious referee: the core idea is worth fixing, and the integer-case construction might survive revision. But as it stands, the NN section needs either a corrected scaling with a provable grid covering the full pre-activation range, or removal from the claims.

Referee Report

4 major / 6 minor

Summary. This manuscript proposes two QUBO-construction methods for objective functions of the form F(x)=∑_k c_k f(q_k(x)): a one-hot discretization of the scalar argument q and a ReLU-expansion method in which f is approximated by a polyline and each ReLU term is quadratized. For positive coefficients the ReLU is encoded via the Legendre identity max_{t∈{0,1}} tq, and for negative coefficients via an integer binarization with a sign bit z_D. The authors derive Eq. (14) as the resulting QUBO, count auxiliary variables for GMMs, kernel regressors, and one-hidden-layer ReLU networks in Table II, and propose a QA-based black-box optimization loop. The numerical section evaluates the polyline fit to a scalar exponential, not the QUBO form.

Significance. If correct, the positive-coefficient branch would give a genuine QUBO for GMM and RBF-kernel regressors with O(MK) or O(MK log N) auxiliary variables, which is a useful practical contribution for annealing-based black-box optimization. However, the negative-coefficient branch is load-bearing for the claimed general applicability, and the manuscript's treatment of it contains concrete algebraic errors; the neural-network row of Table II is unverified as written. With corrections to the binarization and a genuine QUBO-level numerical test, the method could be significant, as it would extend annealing-based black-box optimization beyond quadratic surrogate models.

major comments (4)

[Eq. (14) vs. Eq. (11) and Appendix B] Equation (14) does not actually enforce the constraint under which Eq. (13) was derived. In Section 3.2 q is defined as q = A(q_int − α) and Eq. (11) binarizes q_int − ⌊α⌋, but the penalty in Eq. (14) is (q_k(x) − ⌊α_m⌋ − 1 + 2^D − ∑2^j z)^2, i.e. it constrains q_k(x) − ⌊α_m⌋ instead of q_int − ⌊α_m⌋. For q_k(x) = A(q_int − α) these differ by a factor A and by the fractional part of α, and for the non-integer case of Eq. (B·1) the correct penalty should contain the scale factor C. As written, the feasible set of Eq. (14) is not the set on which z_D has the claimed sign property, so the negative-coefficient terms do not equal c_k(a_m − a_{m−1}) R(q_k(x) − α_m).
[Eq. (12) and Appendix C] Equation (12) uses min(...) where the covering condition requires max(...). For example, for a kernel regressor with α = 0 and q_int ∈ {0, ..., N}, Eq. (12) gives D = log2(1) = 0, whereas representing values up to N requires D ≥ ceil(log2 N). The bound D ≤ log2 N advertised in Section 4.2 and Appendix C would follow from the corrected max version, but the printed formula is wrong and would make the bit width in Table II meaningless.
[Appendix B and Section 4.3] The scale factor in Eq. (B·1) is insufficient to cover min q: C = max(|max q|/2^D, |min q|/2^D − 1) yields a minimum representable value C(1 − 2^D), and with min q = −100, D = 4 this equals −78.75, not −100. Additionally, for any positive q < C the nearest grid point with z_D = 1 is at least C, so a squared-penalty optimum may choose z_D = 0 and represent q as a negative value; R(q) = z_D q then evaluates to 0 while the true ReLU is q. No error bound or λ-selection rule is given, so the neural-network construction in Section 4.3 is not established.
[Section 3.3] The numerical evidence verifies only the polyline approximation of a scalar f(q) = e^{−q} (Figs. 2 and 3); it never constructs Eq. (14), never solves the QUBO, and never tests a kernel regressor or neural network. Since the paper's central claim is that Eq. (14) is a valid QUBO for ML surrogates, a numerical check of the full encoding—including the negative-coefficient branch and a comparison of the QUBO optimum with the original F(x) optimum—is required.

minor comments (6)

[Eq. (2)] In the definition of R(q), the second line reads 'x for q ≥ 0'; it should be q, so that R(q) = q for q ≥ 0.
[Eq. (10)] The two constraint lines both read 'h1(t) ≤ 0'; the second should presumably be h2(t) ≤ 0.
[Eq. (14) caption] 'penalty fucntion' is a typo for 'penalty function'.
[Section 3.2] The phrase 'q /nequal0' is a LaTeX artifact and should read 'q ≠ 0'.
[Section 4.4] 'enlights the guidelines' should be 'sheds light on the guidelines' or similar.
[References] Reference 21 lists the arXiv identifier as 'arXiv:2 410.12747'; this should be 'arXiv:2410.12747'.

Circularity Check

0 steps flagged · score 2.0 of 10

No load-bearing circularity; numerical check is a fit-quality measure and self-citations are background only.

full rationale

The paper's central derivation chain is self-contained. Equation (14) is obtained by applying exact transformations — the Legendre representation of ReLU for positive coefficients (Eq. 3/15) and the sign-bit binarization for negative coefficients (Eq. 11/13) — to a piecewise-linear approximation f-hat of the scalar nonlinearity f. The polyline parameters in f-hat are fitted to the target function, but the QUBO encoding of the fitted polyline is exact; the approximation error is a separate, explicitly acknowledged design choice. The numerical test in Sec. 3.3 fits the polyline to F(x) and then measures fidelity to the same F(x), which is a fit-quality check, not an independent prediction, and the paper does not label it as a prediction. The two self-citations (refs. [21] and [28], which include the authors) are cited only as background for existing annealing-based black-box optimization and tensor-network solvers; neither is load-bearing for the proposed construction. No circularity pattern — self-definition, fitted-input-call-prediction, load-bearing self-citation, imported uniqueness, or smuggled ansatz — is exhibited with the required specificity. The weaknesses in Appendix B's scaling for non-integer q are correctness concerns, not circularity. The score of 2 reflects the minor self-referential flavor of the numerical validation and the presence of non-load-bearing self-citations, but the core derivation is not circular.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

No physical entities are introduced. The main burden is carried by approximation parameters (number and slopes of ReLU pieces, penalty weights, bit width) and by the assumption that the binary sign-bit encoding of real-valued pre-activations is exact enough to preserve the ReLU network's optimum. This last assumption is the least supported part of the paper.

free parameters (4)

M (number of ReLU pieces)
User-selected granularity in Algorithm 1; controls approximation error but no formula links M to optimization error.
Polyline parameters a_m, b_m, alpha_m = fitted via SLSQP in Section 3.3, e.g., M=4: a1=-0.4950, b1=0.8431, alpha1=0.3108
Chosen by optimizing residual error; no analytic expression is given for general f.
Penalty coefficients lambda (discretization and sign-bit penalties)
Needed to enforce one-hot and binary-sign constraints; no correctness interval is given, and ill-tuning shifts optima.
Bit width D and scale G for non-integer binarization
In Eq. (B.1), D and G set discretization resolution for NN pre-activations; no accuracy guarantee is derived.

assumptions (5)

standard math Binary variables satisfy x^k=x for k>=1.
Used to simplify q_k(x) in the GMM derivation and in the polynomial expansion of the introduction.
standard math Universal Approximation Theorem for one-hidden-layer networks.
Justifies representing arbitrary continuous f by ReLU-expanded polylines; Section 3.2 cites ref. 29.
standard math Legendre representation R(q)=max_{t in [0,1]} tq.
Core positive-coefficient quadratization, taken from refs. 24,25.
domain assumption R(q)=z_D q under the binary encoding of q (Eq. (13)).
For integer-grid q the equality is exact; for NN pre-activations Appendix B gives only an approximation with no error bound.
domain assumption Pre-activations are nonzero generic decimals avoiding exact zeros.
Used to justify binary t and sign-bit validity; relies on coefficient randomness rather than a proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions." pith.science (2026). https://pith.science/paper/5HIZSS6Q

@misc{pith2026250608448,
  author       = {Pith},
  title        = {Pith review of: Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5HIZSS6Q}},
  note         = {Machine review of arXiv:2506.08448}
}

read the original 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.

Figures

Figures reproduced from arXiv: 2506.08448 by the authors.

**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(x), which requires quadratization process after training. Originally nonlinear regressors are quadratized to F(x, t) by adding auxiliary variables t. Here, (x, t) T… view at source ↗

**Figure 2.** (Color online) Black line f(q) is approximated by a gray polyline. As an example, f(q) = e −q is depicted. The polyline is modeled by connecting the tangent lines (dashed lines). Algorithm 1 ReLU-expansion method Input: M, D, F(x) = PK k=1 ck f(qk(x)) Output: QUBO objective function 1: Model approximated f(q) by a polyline ˆf(q) (Eq. (6)) 2: Define residual error between f(q) and ˆf(q) 3: Tune model parameters by m… view at source ↗

**Figure 3.** (Color online) Target function F(x) is approximated by the ReLU-expansion method. Approximated functions are plotted as dashed lines with the total number of pieces M = 2, 3, and 4. F(x) = P5 k=1 ck exp(−(x − µk) 2 /2σ 2 k ) is generated randomly by uniform sampling ck ∈ {−0.5,−0.4, −0.3, . . . , 1.0}, µk ∈ {−2.0, −1.9, . . . , 2.0} and σk ∈ {0.5, 0.6, . . . , 1.0}, respectively. With only four pieces M = 4, strongl… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 41 canonical work pages

[1]

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

Introduction Combinatorial optimization problems have numerous real- world applications, spanning diverse ﬁelds including logi s- tics, materials science, and ﬁnance. In recent years, the si ze of these problems has increased with the volume of data traf- ﬁc, which leads to the di ﬃculty of solving them in a realistic time. To address this situation, quan...

work page Pith review arXiv 2025
[2]

Our target is maximizing F(x) = K∑ k=1 ck f (qk(x))

Related Work In this study, we propose a systematic and e ﬃcient QUBO formulation for functions with high-order and dense intera c- tions involving ML regressors. Our target is maximizing F(x) = K∑ k=1 ck f (qk(x)). (1) Here, we assume that qk : x → R1 is a scalar map and f is a continuous nonlinear function. As shown later, many ML re- gressors are model...

work page
[3]

The ﬁrst is to linearly discretize original func- tions by one-hot vectorization

Proposed Method We propose the following two quadratization methods for ML models. The ﬁrst is to linearly discretize original func- tions by one-hot vectorization. The second is to expand the function using ReLU functions. 3.1 Discretization method If q is discrete, f can be rigorously decomposed into f (q) → ∑L l=1 f (dl)sl by PLAs. 23) Here, we conside...

work page 1991
[4]

After substituting Eqs

We deﬁne the complement set as ∆n. After substituting Eqs. (3) and (13) into Eq. (8) and rearranging the terms, the following expression is obtained. max x F(x) ≃ max x max tk,m∈[0,1] max z j,k,m∈{0,1} {K∑ k=1 cka0qk(x) + ∑ (k,m)∈∆p ck(am − am−1)tk,m(qk(x) − αm) + ∑ (k,m)∈∆n { ck(am − am−1)zk,m,D(qk(x) − αm) − λk,m ( qk(x) − ⌊αm⌋ − 1 + 2D − D∑ j=0 2 jzk,m...

work page
[5]

The parameters for the middle tan- gent lines were optimized by maximizing the shaded area with sequential least quadratic programming, 31) in the fol- 4 J

The polyline parameters for the initial and ﬁnal tangent lines Tini, Tﬁn were designed to pass through points (0 , 1), and (4 , 0), respectively. The parameters for the middle tan- gent lines were optimized by maximizing the shaded area with sequential least quadratic programming, 31) in the fol- 4 J. Phys. Soc. Jpn. FULL PAPERS 4 3 2 1 0 1 2 3 4 x 0.0 0....

work page
[6]

We com- pare their costs, such as the number of auxiliary variables a nd that of penalty terms as shown in Table II

Application to ML Regressors Using the discretization method and the ReLU-expansion method, typical ML models are encoded to QUBO. We com- pare their costs, such as the number of auxiliary variables a nd that of penalty terms as shown in Table II. 4.1 Gaussian mixture model The ﬁrst problem is Gaussian Mixture Models (GMMs), 33) FGMM(x) = K∑ k=1 pk(π/σ2 k...

work page
[7]

Promoting the application of advanced quantum technology platforms to social issues

Conclusion In this study, we developed new quadratization methods for constructing QUBO forms for high-order and dense in- teractions. The ﬁrst is to linearly discretize original fun ctions by one-hot vectorization. The second is to expand the func- tion using ReLU functions. We revealed that these methods can formulate QUBO from typical objective functio...

work page
[8]

Finnila, M

A. Finnila, M. Gomez, C. Sebenik, C. Stenson, and J. Doll: C hem. Phy. Lett. 219 (1994) 343

work page 1994

Show all 43 references

[9]

Kadowaki and H

T. Kadowaki and H. Nishimori: Phys. Rev. E 58 (1998) 5355

1998
[10]

Das and B

A. Das and B. K. Chakrabarti: Rev. Mod. Phys. 80 (2008) 1061

2008
[11]

Tanaka, R

S. Tanaka, R. Tamura, and B. K. Chakrabarti: Quantum Spin Glasses, Annealing and Computation (Cambridge University Press, 2017)

2017
[12]

Tanahashi, S

K. Tanahashi, S. Takayanagi, T. Motohashi, and S. Tanaka: Journal of the Physical Society of Japan 88 (2019) 061010

2019
[13]

B. K. Chakrabarti, H. Leschke, P . Ray, T. Shirai, and S. Tan aka: Philo- sophical Transactions of the Royal Society A: Mathematical , Physical and Engineering Sciences 381 (2023) 20210419

2023
[14]

A. Glos, A. Krawiec, and Z. Zimbor´ as: npj Quantum Informa tion 8 (2022) 39

2022
[15]

V erch` ere, S

Z. V erch` ere, S. Elloumi, and A. Simonetto: 2023 IEEE Inte rnational Conference on Quantum Computing and Engineering (QCE), V ol . 1, 2023, pp. 19–25

2023
[16]

Boros and P

E. Boros and P . L. Hammer: Discrete Applied Mathematics 123 (2002) 155

2002
[17]

Dattani: arXiv preprint arXiv:1901.04405 (2019)

N. Dattani: arXiv preprint arXiv:1901.04405 (2019)

2019 arXiv
[18]

I. G. Rosenberg: Cahiers du Centre d ’Etudes de Recherche Opera- tionnelle, 17 (1975) 71

1975
[19]

Schmidbauer, K

L. Schmidbauer, K. Wintersperger, E. Lobe, and W. Mauere r: (2024) 35

2024
[20]

R. S. Sutton and A. G. Barto: Reinforcement learning: An introduction (MIT press, 2018)

2018
[21]

Snoek, H

J. Snoek, H. Larochelle, and R. P . Adams: Advances in neur al informa- tion processing systems 25 (2012)

2012
[22]

Glorot, A

X. Glorot, A. Bordes, and Y . Bengio: In G. Gordon, D. Dunso n, and M. Dud´ ık (eds), Proceedings of the F ourteenth International Confer- ence on Artiﬁcial Intelligence and Statistics , V ol. 15 of Proceedings of Machine Learning Research, 11–13 Apr 2011, pp. 315–323

2011
[23]

S. Y . Kung: Kernel Methods and Machine Learning (Cambridge Uni- versity Press, 2014)

2014
[24]

Kitai, J

K. Kitai, J. Guo, S. Ju, S. Tanaka, K. Tsuda, J. Shiomi, and R. Tamura: Phys. Rev. Res. 2 (2020) 013319

2020
[25]

Izawa, K

S. Izawa, K. Kitai, S. Tanaka, R. Tamura, and K. Tsuda: Phy s. Rev. Res. 4 (2022) 023062

2022
[26]

Inoue, Y

T. Inoue, Y . Seki, S. Tanaka, N. Togawa, K. Ishizaki, and S . Noda: Opt. Express 30 (2022) 43503

2022
[27]

K. Nawa, T. Suzuki, K. Masuda, S. Tanaka, and Y . Miura: Phy s. Rev. Appl. 20 (2023) 024044

2023
[28]

Y . Seki, H. Nakada, and S. Tanaka: arXiv preprint arXiv:2 410.12747 (2024)

2024
[29]

Minamoto and Y

Y . Minamoto and Y . Sakamoto: arXiv preprint arXiv:2501. 04225 (2025)

2025
[30]

Misener and C

R. Misener and C. Floudas: Journal of optimization theor y and applica- tions 145 (2010) 120

2010
[31]

G. Sato, M. Konoshima, T. Ohwa, H. Tamura, and J. Ohkubo: P hysical Review E 99 (2019) 042106

2019
[32]

Y okota, M

T. Y okota, M. Konoshima, H. Tamura, and J. Ohkubo: Journa l of the Physical Society of Japan 89 (2020) 034801

2020
[33]

V . S. Denchev, N. Ding, S. V . N. Vishwanathan, and H. Neven : ICML’12, 2012, p. 1003–1010

2012
[34]

Lopez-Piqueres, J

J. Lopez-Piqueres, J. Chen, and A. Perdomo-Ortiz: Machi ne Learning: Science and Technology 4 (2023) 035009

2023
[35]

Nakada, K

H. Nakada, K. Tanahashi, and S. Tanaka: arXiv preprint arXiv:2409.01699 (2024)

2024 arXiv
[36]

Leshno, V

M. Leshno, V . Y . Lin, A. Pinkus, and S. Schocken: Neural Ne tworks 6 (1993) 861

1993
[37]

De Boor: A Practical Guide to Splines (Applied Mathematical Sci- ences

C. De Boor: A Practical Guide to Splines (Applied Mathematical Sci- ences. Springer New Y ork, 1978), Applied Mathematical Sciences

1978
[38]

Nocedal and S

J. Nocedal and S. J. Wright: Numerical optimization (Springer, 1999)

1999
[39]

Virtanen, R

P . Virtanen, R. Gommers, T. E. Oliphant, et al.: Nature Me thods 17 (2020) 261

2020
[40]

D. A. Reynolds: Encyclopedia of biometrics 741 (2009)

2009
[41]

Farhi, J

E. Farhi, J. Goldstone, and S. Gutmann: arXiv preprint arXiv:1411.4028 (2014)

2014 arXiv
[42]

Zhou, S.-T

L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin: P hys. Rev. X 10 (2020) 021067

2020
[43]

C. E. Rasmussen and C. K. I. Williams: Gaussian Processes for Ma- chine Learning (The MIT Press, 2005). 7

2005

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

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

Introduction Combinatorial optimization problems have numerous real- world applications, spanning diverse ﬁelds including logi s- tics, materials science, and ﬁnance. In recent years, the si ze of these problems has increased with the volume of data traf- ﬁc, which leads to the di ﬃculty of solving them in a realistic time. To address this situation, quan...

work page Pith review arXiv 2025

[2] [2]

Our target is maximizing F(x) = K∑ k=1 ck f (qk(x))

Related Work In this study, we propose a systematic and e ﬃcient QUBO formulation for functions with high-order and dense intera c- tions involving ML regressors. Our target is maximizing F(x) = K∑ k=1 ck f (qk(x)). (1) Here, we assume that qk : x → R1 is a scalar map and f is a continuous nonlinear function. As shown later, many ML re- gressors are model...

work page

[3] [3]

The ﬁrst is to linearly discretize original func- tions by one-hot vectorization

Proposed Method We propose the following two quadratization methods for ML models. The ﬁrst is to linearly discretize original func- tions by one-hot vectorization. The second is to expand the function using ReLU functions. 3.1 Discretization method If q is discrete, f can be rigorously decomposed into f (q) → ∑L l=1 f (dl)sl by PLAs. 23) Here, we conside...

work page 1991

[4] [4]

After substituting Eqs

We deﬁne the complement set as ∆n. After substituting Eqs. (3) and (13) into Eq. (8) and rearranging the terms, the following expression is obtained. max x F(x) ≃ max x max tk,m∈[0,1] max z j,k,m∈{0,1} {K∑ k=1 cka0qk(x) + ∑ (k,m)∈∆p ck(am − am−1)tk,m(qk(x) − αm) + ∑ (k,m)∈∆n { ck(am − am−1)zk,m,D(qk(x) − αm) − λk,m ( qk(x) − ⌊αm⌋ − 1 + 2D − D∑ j=0 2 jzk,m...

work page

[5] [5]

The parameters for the middle tan- gent lines were optimized by maximizing the shaded area with sequential least quadratic programming, 31) in the fol- 4 J

The polyline parameters for the initial and ﬁnal tangent lines Tini, Tﬁn were designed to pass through points (0 , 1), and (4 , 0), respectively. The parameters for the middle tan- gent lines were optimized by maximizing the shaded area with sequential least quadratic programming, 31) in the fol- 4 J. Phys. Soc. Jpn. FULL PAPERS 4 3 2 1 0 1 2 3 4 x 0.0 0....

work page

[6] [6]

We com- pare their costs, such as the number of auxiliary variables a nd that of penalty terms as shown in Table II

Application to ML Regressors Using the discretization method and the ReLU-expansion method, typical ML models are encoded to QUBO. We com- pare their costs, such as the number of auxiliary variables a nd that of penalty terms as shown in Table II. 4.1 Gaussian mixture model The ﬁrst problem is Gaussian Mixture Models (GMMs), 33) FGMM(x) = K∑ k=1 pk(π/σ2 k...

work page

[7] [7]

Promoting the application of advanced quantum technology platforms to social issues

Conclusion In this study, we developed new quadratization methods for constructing QUBO forms for high-order and dense in- teractions. The ﬁrst is to linearly discretize original fun ctions by one-hot vectorization. The second is to expand the func- tion using ReLU functions. We revealed that these methods can formulate QUBO from typical objective functio...

work page

[8] [8]

Finnila, M

A. Finnila, M. Gomez, C. Sebenik, C. Stenson, and J. Doll: C hem. Phy. Lett. 219 (1994) 343

work page 1994