{"id":"e9d6c52c-20c6-4a12-80b4-bd7c08f4499f","arxiv_id":"2506.08448","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A systematic QUBO construction via ReLU expansion and binary sign-bit encoding for Gaussian mixture, RBF kernel, and ReLU-network surrogates, enabling quantum-annealing-based black-box optimization.","lead":"Quantum annealers can only solve problems written as quadratic binary formulas, while most machine-learning models are highly nonlinear. This paper gives a recipe for rewriting such models, including neural networks, into that form by approximating them with sums of simple kink functions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The NN case (Eq. B.1) has a scaling error and no error bound; the sign-bit trick does not preserve q, so the Table II NN row is unverified.","rationale":"I read the paper in good faith: the core ReLU-expansion construction is a legitimate synthesis of the Legendre-transform trick for positive coefficients and a sign-bit encoding for negative ones, with reasonable auxiliary-variable counts for GMMs and KRs. The reader's CONDITIONAL verdict is appropriate. My stress-test finds the same weakest assumption as the reader did - the NN case rests on Eq. (B.1) - and identifies a concrete arithmetic problem: the printed scaling factor does not cover the negative half-range and can encode small positive pre-activations as negative. Even if this is a typo and the intended denominator is 2^D - 1, the method still supplies no error bound and no penalty-coefficient guidance, so the QUBO optimum of Eq. (14) is not guaranteed to match the original ReLU network's optimum. Because the NN row of Table II is a central advertised application, this is load-bearing. However, the paper's other contributions (exact positive-ReLU encoding, GMM/KR resource counts, and the scalar polyline demonstration) remain plausible, so a conditional acceptance with requested revisions is the right verdict rather than outright rejection. I agree with the reader's identification of the approximate binarization as the key risk; my analysis sharpens it into a specific scaling failure.","tokens_in":12564,"tokens_out":8373,"duration_ms":100298,"concrete_test":"Take a small NN instance (e.g., N = 6, D = 4, random w_ki, theta_k, c_k as in Section 4.3), compute the true set {q_k(x) : x in {0,1}^N}, and evaluate Eq. (B.1) with the printed scaling factor. Check whether every q_k(x) has a grid point C*S with sign(z_D) = sign(q_k(x)) and |C*S - q_k(x)| bounded by, say, C/2; if coverage fails, the sign-bit encoding is not an approximation. Then solve Eq. (14) by exhaustive enumeration over (x, t, z) for lambda = 1, 10, 100 times the largest quadratic coefficient, and compare the argmax and optimal value with the argmax of the original F_NN. If the argmax differs for all lambda, the Section 4.3 claim is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central deliverable is Eq. (14): a QUBO whose optimum should match max_x F(x) for ML surrogates. The construction is exact for positive ReLU coefficients via t in {0,1}, and the GMM/KR analyses are plausible. The load-bearing step is the negative-coefficient branch, where Eq. (13) replaces R(q) with z_D q under the binarization constraint. For the NN case (Section 4.3), q_k(x) is not integer-valued, and Appendix B substitutes the approximate binarization (B.1). As written, the scaling factor C = max(|max q|/2^D, |min q|/2^D - 1) is insufficient: the most negative representable value is C(1 - 2^D), and covering min q requires C >= |min q|/(2^D - 1), which the printed second term does not provide (e.g., min q = -100, D = 4 gives C = 5.25 and coverage only down to -78.75). Moreover, for typical positive q below C, the closest grid point with z_D = 1 is >= C, so the optimal assignment for the squared penalty has z_D = 0 and encodes positive q as negative - the opposite sign. Because Eq. (14) imposes the binarization only through a soft penalty lambda(q - C S)^2 and gives no lambda selection rule, sign consistency is not guaranteed at the QUBO optimum. No error bound links the QUBO optimum to the ReLU network's optimum; the numerical test (Section 3.3) fits a scalar e^{-q}, not an NN or a QA run. The authors themselves note in Section 4.4 that a D upper bound is not guaranteed for NNs, but the failure here is more basic: the printed formula does not encode the pre-activation range.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12976,"tokens_out":10649,"duration_ms":120599,"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":[{"comment":"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).","section":"Eq. (14) vs. Eq. (11) and Appendix B"},{"comment":"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.","section":"Eq. (12) and Appendix C"},{"comment":"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":"Appendix B and Section 4.3"},{"comment":"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.","section":"Section 3.3"}],"minor_comments":[{"comment":"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.","section":"Eq. (2)"},{"comment":"The two constraint lines both read 'h1(t) ≤ 0'; the second should presumably be h2(t) ≤ 0.","section":"Eq. (10)"},{"comment":"'penalty fucntion' is a typo for 'penalty function'.","section":"Eq. (14) caption"},{"comment":"The phrase 'q /nequal0' is a LaTeX artifact and should read 'q ≠ 0'.","section":"Section 3.2"},{"comment":"'enlights the guidelines' should be 'sheds light on the guidelines' or similar.","section":"Section 4.4"},{"comment":"Reference 21 lists the arXiv identifier as 'arXiv:2 410.12747'; this should be 'arXiv:2410.12747'.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The referee report already contains the main technical points. I would add that if the authors cannot repair the non-integer binarization of Appendix B with a provable error bound, they should either remove the neural-network claim from the abstract and Table II or relegate it to a clearly labeled conjecture. The current numerical section is too weak for a JPSJ full paper even after the algebra is fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nSoft 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.\n\nThe 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.","headline":"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.","tokens_in":13509,"tokens_out":6346,"would_cite":false,"duration_ms":69984,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Nonlinear ML surrogate functions can be rewritten as QUBO forms through ReLU expansions, letting quantum annealers optimize them directly.","keywords":["QUBO","quadratization","ReLU expansion","quantum annealing","black-box optimization","Gaussian mixture model","kernel regressor","neural network"],"falsifier":"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.","tokens_in":12345,"feed_emoji":"🧮","tokens_out":10135,"duration_ms":106270,"temperature":0.7,"pith_summary":"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.","feed_headline":"ReLU bases turn ML surrogates into QUBO forms","feed_subtitle":"Quantum annealing can now optimize GMM, RBF-kernel, and ReLU-network surrogates after a systematic quadratization.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It supplies the Legendre representation $R(q)=\\max_t t\\,q$ that carries the positive-coefficient ReLU encodings in Eq. (3).","marker":"24"},{"why":"It supplies the Wolfe-duality encoding for minimizing with ReLU terms, the max-min difficulty that motivates the paper's sign-binarization for negative coefficients.","marker":"25"},{"why":"It provides the universal approximation result for one-hidden-layer ReLU networks that justifies approximating arbitrary continuous $f$ by sums of ReLU bases.","marker":"29"},{"why":"It supplies the standard substitution-based quadratization of higher-order binary products that the paper positions as too expensive for dense nonlinear interactions.","marker":"11"},{"why":"It supplies the piecewise-linear approximation background used by the discretization method and by the polyline fitting in the ReLU-expansion method.","marker":"23"}],"fun_headline_variants":["ReLU quadratization feeds ML surrogates to quantum annealing","Quantum annealing gets ML surrogates via ReLU quadratization","ML surrogates to QUBO via systematic ReLU quadratization","Quantum annealing now handles ML surrogates via ReLU QUBO"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["ReLU quadratization feeds ML surrogates to quantum annealing","Quantum annealing gets ML surrogates via ReLU quadratization","ML surrogates to QUBO via systematic ReLU quadratization","Quantum annealing now handles ML surrogates via ReLU QUBO"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000729,"raw_usage":{"total_tokens":3260,"prompt_tokens":935,"completion_tokens":2325,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":551,"completion_tokens_details":{"reasoning_tokens":2259}},"tokens_in":551,"tokens_out":2325,"duration_ms":19065,"temperature":1.0,"reasoning_tokens":2259,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:12:30.457495+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Kitai, J","cited_arxiv_id":null,"evidence_quote":"It supplies the Legendre representation $R(q)=\\max_t t\\,q$ that carries the positive-coefficient ReLU encodings in Eq. (3)."},{"cited_title":"Izawa, K","cited_arxiv_id":null,"evidence_quote":"It supplies the Wolfe-duality encoding for minimizing with ReLU terms, the max-min difficulty that motivates the paper's sign-binarization for negative coefficients."},{"cited_title":"Minamoto and Y","cited_arxiv_id":null,"evidence_quote":"It provides the universal approximation result for one-hidden-layer ReLU networks that justifies approximating arbitrary continuous $f$ by sums of ReLU bases."},{"cited_title":"Tanaka, R","cited_arxiv_id":null,"evidence_quote":"It supplies the standard substitution-based quadratization of higher-order binary products that the paper positions as too expensive for dense nonlinear interactions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the piecewise-linear approximation background used by the discretization method and by the polyline fitting in the ReLU-expansion method."}],"review_version":1}