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.
