A quadratization represents a Boolean cost by minimizing a quadratic cost over auxiliary variables. For a four-variable family with one positive quartic coefficient and six sufficiently negative quadratic coefficients, this work determines the exact uniform error with at most six genuine pair interactions, allowing any finite auxiliary set. The optimum is the minimum of an explicit quadratic fallback and thirty-nine scalar capacities, explained by three response mechanisms. Interval endpoints and rational max flow construct attaining nonnegative rational networks with at most two auxiliary variables, without optimization linear programs. A structural lower bound covers all finite auxiliary sets. The paper also gives the separate one-auxiliary seven-, eight- and nine-interaction formulas, the one-auxiliary six-interaction procedure with 57 rational linear programs, and an exact interaction frontier. Absolute costs are retained. The results are proof-supported candidate theorems for this structured family; no claim about arbitrary quartic targets or hardware performance is made.
We study the error incurred when a nonnegative ternary Boolean cost, realizable by a network of treewidth at most two, is approximated by the sum of two independent hidden-variable stars. Costs are retained absolutely, including their constant part. We give an exact weighted maximum-norm distance formula and attained cost bounds. In the uniform norm the sharp bounds are one fifth of the largest entry and one thirty-first of the total; we describe their equality cases and the exact effect of a common lower floor. For eight independently positive tolerance scales, the least total and least peak needed for unit error have explicit finite min-max formulas. The peak formula admits an analytical construction using four aggregate parameters, replacing a previous thirty-vertex interpolation. We also give the total-cost law with eight tolerance scales and a lower floor. When the scales are constant on each cube parity, joint total and peak budgets have at most two Pareto-minimal cost pairs. The arguments use clipping at zero, an elementary weighted-box construction, and the root-capacity criterion from the companion compression paper. The results are presented as candidate theorems supported by written proofs and exact software checks. The accompanying support supplies the complete source, exact code, verification and reproduction records.
A direct coefficient proof establishes a sharp bound for real quadratic majorants of three-bit majority on three labelled terminals and any finite set of original hidden bits, with affine terms free. The bound includes hidden-hidden and terminal-terminal premiums and even-boundary excess. Every original total-mass-six representation is characterized by four corner-star types with positive weights totaling one half per type, plus nonnegative unary isolates after hidden complements. Sharp constructions, a scalar ternary cubic formulation and cut/cone dictionaries are included. The full bound and equality family also follow from earlier parity-gadget results through explicit supplied deductions. Results retain candidate assurance status; historical novelty is unresolved and no priority claim is made.
Strongly regular graphs, hereafter SRGs, are highly structured combinatorial objects of central interest in algebraic graph theory and quantum information, whose explicit construction becomes rapidly intractable as the number of vertices grows; Conway's still unresolved
99-graph problem is an emblematic example. The matrix equation defining SRGs is quadratic in the binary edge variables, so the natural penalty enforcing it, a sum of squared residuals, is quartic and lies outside quadratic unconstrained binary optimization, known as QUBO. We prove a considerably stronger obstruction, namely that no quadratic function of the edge variables has the labeled SRGs as its exact set of global minimizers, except for three degenerate families given by the perfect matchings, the cocktail-party graphs and the pentagon. In particular, we formally establish that the
99-vertex graph of Conway's problem cannot be obtained from any QUBO over the edge variables without auxiliary variables. Guided by this theorem we develop two complementary algorithms. The first operates within pure QUBO, solves the degenerate families exactly, and beyond them works as a generate--prune--verify pipeline whose output is a reduced set of candidates certified by a polynomial-time classical test. The second solves the full problem by quadratizing this quartic penalty through Rosenberg auxiliary variables, whose number grows as
Θ(N3) with the number of vertices
N. We test the pure-QUBO route under simulated annealing on all feasible families with at most
18 vertices and the auxiliary-variable route on representative targets up to
16 vertices, and tabulate the algebraically feasible parameter sets for graphs with at most
49 vertices.
The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications.A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques.Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials.A desirable property for a quadratization is to introduce small number of auxiliary variables.For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular.However, much less is known for positive monomials.The best lower bound on the number of variables required by a quadratization in the literature is n-1 2 .We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound.This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact kout-of-n functions, which is a more general class of symmetric functions.Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization.Finally, we provide quadratizations for general symmetric functions using O( √ n) auxiliary variables.This upper bound nicely matches a lower bound of Ω( √ n) variables that was recently introduced.
We give a direct analytic proof that every total Boolean function computable exactly with at most two quantum queries depends on at most six input variables. This bound is sharp. A previous derivation relied on a numerical classification of Boolean functions on at most four variables; to the best of our knowledge, ours is the first unconditional proof. The main difficulty beyond the one-query case is that query-path vectors need not be mutually orthogonal, so interference prevents the scalar weight-counting argument from applying. We overcome this difficulty by establishing a rigid support-and-branch decomposition: after the coordinates in the first-query support are fixed, the second query induces a family of exact one-query branches. This structural description may be of independent interest.
Ising solvers have a finite spin budget. Quadratization uses auxiliary spins to replace higher-order interactions by pairwise ones. We show that removing spins while allowing more complex interactions can fit larger problems within the same spin budget and improve optimization. Walsh elimination minimizes over one spin at a time, writes the resulting interaction as a sum of spin products in the Walsh basis, and stores a rule for recovering the removed spin. Explicit resource limits control which eliminations are accepted. In a held-out test with the protocol frozen before instance generation and one annealing schedule shared by both formulations, mean observed success rises from 10.4% to 97.5% on sparse quadratic spin glasses and from 16.9% to 87.5% on three-body problems. Observed success increases on every instance with a verified reference minimum, and pooled time-to-solution estimates decrease by factors of about 34 and 11, respectively, with preprocessing included. For zero-field pairwise models on connected simple cubic graphs with more than four vertices, we prove that a fixed spin budget accommodates 50% larger inputs while retaining pairwise interactions, zero fields, residual degree at most six, and no increase in coupling count. These results establish exact spin elimination as a controlled trade between active-spin capacity and interaction complexity.