  We prove that any function with real-valued coefficients, whose input is 4
binary variables and whose output is a real number, is perfectly equivalent to
a quadratic function whose input is 5 binary variables and is minimized over
the new variable. Our proof is constructive: we provide quadratizations for all
possible 4-variable functions. There exists 4 different classes of 4-variable
functions that each have their own 5-variable quadratization formula. Since we
provide 'perfect' quadratizations, we can apply these formulas to any
4-variable subset of an n-variable function even if n >> 4. We provide 5
examples of functions that can be quadratized using the result of this work.
For each of the 5 examples we compare the best possible quadratization we could
construct using previously known methods, to a quadratization that we construct
using our new result. In the most extreme example, the quadratization using our
new result needs only N auxiliary variables for a 4N-variable degree-4
function, whereas the previous state-of-the-art quadratization requires 2N
(double as many) auxiliary variables and therefore we can reduce by the cost of
optimizing such a function by a factor of 2^1000 if it were to have 4000
variables before quadratization. In all 5 of our examples, the range of
coefficient sizes in our quadratic function is smaller than in the previous
state-of-the-art one, and our coefficient range is a factor of 7 times smaller
in our 15-term, 5-variable example of a degree-4 function.
