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

arXiv1910.13583MaRDI QIDQ6328134FDOQ6328134

Publication date: 29 October 2019

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.

Mathematics Subject Classification ID

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

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)