How to reduce a quartic form to a quadratic form with equal roots

Question

Given a polynomial in $n$ variables of the form

$$P(x_1,x_2,\dots,x_n)=\left(\sum_{i,j}a_{ij}x_ix_j+\sum_{i}b_{i}x_i+c\right)^2$$

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

$$Q(y_1,y_2,\dots,y_n)=\sum_{i,j}d_{ij}y_iy_j+\sum_{i}e_{i}y_i+f$$

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$

$$R(y_1,y_2,\dots,y_m)=\sum_{i,j}g_{ij}y_iy_j+\sum_{i}h_{i}y_i+k$$

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?

Answer 1

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.

Answer 2

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