# Converting a Quartic Term into Quadratic Form in QUBO for Prime Factorization

This is a continuation of this question and I encourage you to read that as well.

I'm trying to embed the prime factorization problem into the form of a QUBO. To do so, let $$p$$ and $$q$$ be two real positive numbers. We can represent these two numbers as binary numbers, which itself can be represented as vectors, $$\pmb{p}$$ and $$\pmb{q}$$, where $$\pmb{p}$$ and $$\pmb{q}$$ both have $$k$$ elements. I define a new vector $$\pmb{x}$$ by concatenating $$\pmb{p}$$ and $$\pmb{q}$$ as follows:

$$p_i \in \{ 0,1\}$$ $$q_i \in \{ 0,1\}$$

$$\pmb{x} = (p_1, \ldots, p_k, q_1, \ldots, q_{k})^T$$

Now I define the following matrix $$Q$$:

$$Q = \sigma_x \otimes \alpha$$

where $$\alpha$$ is a $$k \times k$$ matrix that its elements are defined like this:

$$\alpha_{ij} = 2^{2k - (i+j)}$$ and $$\sigma_x = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$

This formulation, allows us to make $$Q$$ in a way that the product of numbers $$p$$ and $$q$$ is equal to the expression $$\frac{1}{2}\pmb{x}^T Q \pmb{x}$$:

$$\frac{1}{2}\pmb{x}^T Q \pmb{x} = pq$$

Now, I can also do this for $$(pq)^2$$:

$$\frac{1}{4}\pmb{x}^T Q \pmb{x}\pmb{x}^T Q \pmb{x} = (pq)^2$$

Now coming back to our original problem, we want to find the $$p$$ and $$q$$ so that:

$$pq = N$$

To do so, we can convert it into this optimization problem:

$$\min_{p,q} f(p,q) = \min_{p,q} (N-pq)^2$$

and I using the QUBO form, we can convert $$f$$ to:

$$f(p,q) = N^2+ (pq)^2 - 2 N pq$$ $$f(p,q) = N^2+ \frac{1}{4}\pmb{x}^T Q \pmb{x}\pmb{x}^T Q \pmb{x} - N \pmb{x}^T Q \pmb{x}$$

This is not yet in QUBO form, as the $$\pmb{x}^T Q \pmb{x}\pmb{x}^T Q \pmb{x}$$ actually has 4 local terms. Now my question starts here: I want to use the following formula to "reduce" this minimization into a quadratic form. For 4 binary numbers, this can be done by introducing new variables like this:

$${a}_{1}{a}_{2}{b}_{1}{b}_{2}={a}_{1}\left({x}_{1}{a}_{2}+{x}_{1}{b}_{1}+{x}_{1}{b}_{2}+{a}_{2}{b}_{1}+{a}_{2}{b}_{2}+{b}_{1}{b}_{2}-{a}_{2}-{b}_{1}-{b}_{2}-{x}_{1}+1\right)$$

\begin{aligned} & = x_{2} x_{1} + x_{2} a_{1} + x_{2} a_{2} + x_{1} a_{1} + x_{1} a_{2} + a_{1} a_{2} - x_{1} - a_{1} - a_{2} - x_{2} + 1 \hfill \\ & \quad + x_{3} x_{1} + x_{3} a_{1} + x_{3} b_{1} + x_{1} a_{1} + x_{1} b_{1} + a_{1} b_{1} - x_{1} - a_{1} - b_{1} - x_{3} + 1 \hfill \\ & \quad + x_{4} x_{1} + x_{4} a_{1} + x_{4} b_{2} + x_{1} a_{1} + x_{1} b_{2} + a_{1} b_{2} - x_{1} - a_{1} - b_{2} - x_{4} + 1 \hfill \\ & \quad + x_{5} a_{1} + x_{5} a_{2} + x_{5} b_{1} + a_{1} a_{2} + a_{1} b_{1} + a_{2} b_{1} - a_{1} - a_{2} - b_{1} - x_{5} + 1 \hfill \\ & \quad + x_{6} a_{1} + x_{6} a_{2} + x_{6} b_{2} + a_{1} a_{2} + a_{1} b_{2} + a_{2} b_{2} - a_{1} - a_{2} - b_{2} - x_{6} + 1 \hfill \\ & \quad + x_{7} a_{1} + x_{7} b_{1} + x_{7} b_{2} + a_{1} b_{1} + a_{1} b_{2} + b_{1} b_{2} - a_{1} - b_{1} - b_{2} - x_{7} + 1 \hfill \\ & \quad - a_{1} a_{2} - a_{1} b_{1} - a_{1} b_{2} - a_{1} x_{1} + a_{1} \hfill \\ \end{aligned}

For all $${a}_{1},{a}_{2},{b}_{1},{b}_{2},\in \{\mathrm{0,1}\}$$, $${a}_{1}{a}_{2}{b}_{1}{b}_{2}$$ can be transformed into a combination of linear and quadratic terms by adding seven new variables, $${x}_{1}, {x}_{2},\cdots ,{x}_{7}$$, for each quartic term.

Now I'd like to take this idea and directly apply it to the $$\pmb{x}^T Q \pmb{x}\pmb{x}^T Q \pmb{x}$$ term. Can anyone point me in the right direction? Any guidance would be greatly appreciated.