Reduce 3-SAT to QUBO (Under Development)

I. Quadratic Unconstrained Binary Optimizati (QUBO)

The QUBO problem is to minimize or maximize a quadratic form $y=x^T Q x$, where $x$ is a Boolean vector and $Q$ is a real square matrix.

Ref. 1 gives a new transformation from 3-SAT to QUBO:

Energy of an assignment $\vec{x}$ of a 3-SAT CNF in $Q$: We can introduce some dummy variables $\vec{a}$ and define a new Boolean vector $\tilde{x}=\vec{x} \otimes \vec{a}$. The energy of an assignment $\vec{x}$ is defined as: $\min_{\vec{a}} \tilde{x}^T Q \tilde{x}$.
Clause QUBO: Given a clause $C$ of a 3-SAT instance. A QUBO is a clause QUBO (in terms of $C$) if: 1) The assignments satisfying $C$ has the minimal degenerate energy; 2) Assignments not satisfying $C$ have higher energy.
The remaing proof is lengthy. One may check Ref. 1 for more details.

For a given graph $G=(V,E)$, we can define a classical spin model:

$$ H=\sum{(i, j) \in E} J{i j} \sigma_i \sigmaj+\sum{i \in V} h_i \sigma_i $$

I didn't find good references for this reduction, but it seems that this reduction is trivial:

$J{ij} \rightarrow Q{ij}$
$h_i \rightarrow 0$
Therefore, QUBO can be trivially transformed to solving the ground state of a spin glass model.

GiggleLiu commented 1 month ago