Given a polynomial in $n$ variables of the form


is there a way to find a polynomial also in $n$ variables of degree at most 2


with the same roots and which is positive for all values in the domain? You may assume that all the variables only take on the values $0$ or $1$ and all coefficients are real.

If not is it possible to find a polynomial in $m$ variables with $m>n$


such that if $(z_1,z_2,\dots,z_n)$ is a root of $P$, then $R(z_1,z_2,\dots,z_n,z_{n+1},\dots,z_m)=0$ for some value of $z_{n+1},\dots,z_m$ and R is positive on the domain?

Motivation: I have a bunch of equations which will be fed to a quantum computer, but the it can only handle 2 qubit interactions so I need to reduce expressions to polynomials with degree no more than 2. At the moment I simply use Mathematica to find an instance of a polynomial that satisfies the above constraints, but it fails when $n$ is large. Is there a general procedure to find $R$? Under what conditions does $Q$ fail to exist?


2 Answers 2


The answer to the first part is NO:

  • An example of $P$ is $(\sum_i^Nx_iy_i)^2$, which has $2^N$ roots. But $Q$ has ${2N \choose 2}$ + $2N$ + 1 degrees of freedom ($d_{ij}, e_i, f$). For $N\ge7$ the former is bigger than the latter, so there are not enough degrees of freedom to satisfy the $2^N$ constraints.

The answer to the second part is YES:

  • In binary, there exist positive quadratic functions that have the same roots as the cubic function: $(AB - C)^2$. An example is [1]: $AB - 2AC - 2BC + 3C$.

  • So for every term with $a_{ij}\ne0$, introduce a new variable $C$ such that $P=(x_ix_j - C)^2$. This will be quadratic in $x_i,x_j,$ and $C$.

  • Repeat until all terms are quadratic.

    [1] This is Eq. 43 of Schaller & Schutzhold: http://arxiv.org/pdf/0708.1882v2.pdf with $C=-S$, after expanding, and remembering that binary variables are idempotent.


This is not possible...
let $u$ be a parameter so that $(x_1(u),x_2(u),\dots,x_n(u))$ describing a line in $\mathbb{R}^n$
then $P(x_1(u),x_2(u),\dots,x_n(u))= a_0u^2+a_1u+a_2$ is a parabula. Since $P$ has more than one root we can choose a line with two roots $X_0,X_1$ on it. In this case parabula have two roots $u_0,u_1$.

Suppose we have other quadratic function $R$ of a higher dimention, and $X_0,X_1$ are also its roots. so there is a line $(x_1(v),x_2(v),\dots,x_m(v))$ on witch $R(x_1(v),x_2(v),\dots,x_n(v))= b_0v^2+b_1v+b_2$ we have a parabula with two roots. but parabula with two different roots has negative values, Therefore R must have negative values...


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .