Consider an undirected, unweighted graph $G=(V,E)$. We want to find the Maximum-Cut of the graph, which is defined to be $A \subseteq V$ maximizing the value $$\sum_{uv \in E, \; u \in A, \;v \in V \setminus A} 1.$$
The problem can be modeled as a binary quadratic optimization program as shown here: for each vertex define a variable $x_{i}$ interpreted as:
- $x_i=0 \to i\text{-th vertex} \in A$,
- $x_i=1\to i\text{-th vertex} \in V \setminus A$.
Then the formula is
$$\arg\max_{\mathbf{x} \in \{0,1\}^{|V|}} \sum_{ij \in E} (- 2 x_i x_j + x_i + x_j)$$
As a matter of fact, this is a polynomial reduction from Max-Cut to QUBO problem. However, I have few problems setting up the proof for this formulation.
Can you set up the proof for this reduction? Does it have to be done by induction on the input graph?
To verify that $-2 x_i x_j + x_i + x_j = 1$ if and only if $i$ and $j$ are in opposite sides of the bipartition, it suffices to check the four cases: \begin{matrix} x_i & x_j & -2 x_i x_j + x_i + x_j \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{matrix}
To derive $-2 x_i x_j + x_i + x_j$, note that $$[i\in A][j\in V\setminus A]+[j\in A][j\in V\setminus A] = (1-x_i)x_j+(1-x_j)x_i = -2 x_i x_j + x_i + x_j. $$