I'm trying to reproduce a paper on Prime Factorization. This paper converts the prime factorization problem into a QUBO form, which then we can map it to the Ising model.
As an example, let $p$ and $q$ be binary values like this:
$$p = (x_1 1)_2$$ $$q = (x_3 x_2 1)_2$$ $$ N = pq = 15$$
We want to compute and minimize this expression:
$$f(x_1, x_2, x_3) = (N-p q)^2$$
$$f(x)=128{x}_{1}{x}_{2}{x}_{3}-56{x}_{1}{x}_{2}-48{x}_{1}{x}_{3}+16{x}_{2}{x}_{3}-52{x}_{1}-52{x}_{2}-96{x}_{3}+196$$
But this has 3-local terms. To convert it into a QUBO, we need to reduce it to 2-local terms. This can be done by introducing a new variable for each 3-local term. As we have only one 3-local term, using the following:
$${\rm{\min }}({x}_{1}{x}_{2}{x}_{3})=\,{\rm{\min }}({x}_{4}{x}_{3}+\mathrm{2(}{x}_{1}{x}_{2}-2{x}_{1}{x}_{4}-2{x}_{2}{x}_{4}+3{x}_{4})$$
we get:
$$\begin{array}{rcl}f^{\prime} (x) & = & 200{x}_{1}{x}_{2}-48{x}_{1}{x}_{3}-512{x}_{1}{x}_{4}+16{x}_{2}{x}_{3}-512{x}_{2}{x}_{4}+128{x}_{3}{x}_{4}\\ & & -52{x}_{1}-52{x}_{2}-96{x}_{3}+768{x}_{4}+\mathrm{196,}\end{array}$$
Which ofcourse, satisfies:
$$\mathop{{\rm{\min }}}\limits_{{x}_{1}{x}_{2}={x}_{4}}f({x}_{1},\,{x}_{2},\,{x}_{3},\,{x}_{4})=\,{\rm{\min }}\,f^{\prime} ({x}_{1},\,{x}_{2},\,{x}_{3},\,{x}_{4})$$
Now the bottleneck about this encoding method, lies in its reduction step. For larger numbers, most of the time 3 or 4-local terms appear that the standard procedure is to repeat the reduction until it gets to 2. When done symbolically on a computer, it gets really slow very fast. I've shown it here.
Now my question (suggestion?) is that can we do this using matrix multiplication? As an example, for calculating the term $pq$, let the two binary numbers be represented as vectors, $\pmb{p}$ and $\pmb{q}$, where $\pmb{p}$ has $k$ elements and $\pmb{q}$ has $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$$
I want to construct a matrix $Q$ such that the product of the decimal values of $\pmb{p}$ and $\pmb{q}$ is equal to the expression $\pmb{x}^T Q \pmb{x}$:
$$ \text{decimal}(v) = \sum_{i=1}^{n} v_i 2^{n-i} $$ $$\pmb{x}^T Q \pmb{x} = decimal(p) \times decimal(q)$$
As an example, if $\pmb{p}$ and $\pmb{q}$ are both binary values of length 2, then $Q$ should be:
$$ \begin{bmatrix} p_1 & p_2 & q_1 & q_2 \end{bmatrix} \begin{bmatrix} Q{11} & Q{12} & Q{13} & Q{14} \\ Q{21} & Q{22} & Q{23} & Q{24} \\ Q{31} & Q{32} & Q{33} & Q{34} \\ Q{41} & Q{42} & Q{43} & Q{44} \\ \end{bmatrix} \begin{bmatrix} p_1 \\ p_2 \\ q_1 \\ q_2 \end{bmatrix} $$
The elements of $Q$ corresponding to the interactions within $p$ and within $q$ should be zero, as they do not contribute to the product of $p$ and $q$. Therefore, elements like $Q{11}, Q{12}, Q{21}, Q{22}$ and $Q{33}, Q{34}, Q{43}, Q{44}$ will be zero. The other elements are just the powers of two ($2^k$) in a way that converts the binaries into decimal:
$$Q = \begin{bmatrix} 0 & 0 & 2^2 & 2^1 \\ 0 & 0 & 2^1 & 2^0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} $$
This can be generalized pretty easily. Now, I want to do this for $(N-pq)^2$ but there has to be a procedure for reduction in the language of matrices. Meaning that in the end, using reduction, a matrix $Q'$ and a vector $h$ should exist, where $Q$'s elements are the coefficients of the form $x_i x_j$ and $h$'s elements are coefficients of the $x_i$ terms:
$$\pmb{x}^T Q \pmb{x} + h \cdot \pmb{x} + C= (N - p q)^2$$ where $C$ is just a constant. Is my guess correct or I'm in the wrong here? If I'm correct, can anyone suggest a method for this procedure?
