All 4-variable functions can be perfectly quadratized with only 1 auxiliary variable

Publication date 29 October 2019

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Primes (11A41) Factorization; primality (11A51) Sieves (11N35) Applications of sieve methods (11N36) Generalized primes and integers (11N80) Factorization (11Y05) Numerical optimization and variational techniques (65K10) Numerical methods for Hamiltonian systems including symplectic integrators (65P10) Complexity and performance of numerical algorithms (65Y20) Quantum algorithms and complexity in the theory of computing (68Q12) Computational methods for problems pertaining to quantum theory (81-08) Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Abstract: 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.

This page was built for publication: All 4-variable functions can be perfectly quadratized with only 1 auxiliary variable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328134)