[Rule] MaxCut to QUBO

[zazabap]

Source: MaxCut
Target: QUBO
Motivation: Direct MaxCut-to-QUBO reduction is essential for quantum annealing pipelines; currently only indirect paths exist via SpinGlass.
Reference: Glover et al., "A Tutorial on Formulating and Using QUBO Models" (2019), arXiv:1811.11538

Reduction Algorithm

Notation:

• Source: graph $G = (V, E)$ with $n = |V|$ vertices, $m = |E|$ edges, and edge weights $w_{ij}$ for $(i,j) \in E$
• Target: QUBO matrix $Q$ of size $n \times n$

Variable mapping:

• One binary variable $x_i$ per vertex $i \in V$ ($1$ = in cut set $S$, $0$ = not in $S$)
• Identity mapping: QUBO variable $i$ corresponds to vertex $i$

Constraint/objective transformation:

MaxCut maximizes:

$$\sum_{(i,j)\in E} w_{ij} \cdot (x_i + x_j - 2 x_i x_j)$$

Since $x_i^2 = x_i$ for binary variables, this is equivalent to minimizing $\mathbf{x}^T Q \mathbf{x}$ where:

$$Q_{ii} = -\sum_{j:,(i,j)\in E} w_{ij}, \qquad Q_{ij} = 2 w_{ij} ;\text{for}; (i,j) \in E$$

The QUBO minimum equals the negated maximum cut value.

Solution extraction: The binary vector $\mathbf{x}$ from the QUBO solution directly gives the cut partition: $S = {i : x_i = 1}$.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vars	$n$

Validation Method

Closed-loop test: construct a small weighted graph (e.g., 4-vertex cycle with unit weights), reduce to QUBO, solve both with BruteForce, verify the QUBO optimum maps back to a valid maximum cut with the same weight.

Cross-check: compare with the existing SpinGlass→MaxCut and SpinGlass→QUBO chain — reducing MaxCut directly should yield an equivalent (or smaller) QUBO.

Example

Source: MaxCut on triangle graph with 3 vertices and edges ${(0,1), (1,2), (0,2)}$, all with unit weight $1$.

Reduction:

• $n = 3$, diagonal: each vertex has degree 2, so $Q_{ii} = -2$
• Off-diagonal: $Q_{01} = Q_{02} = Q_{12} = 2$

$Q$ matrix:

$$Q = \begin{pmatrix} -2 & 2 & 2 \ 0 & -2 & 2 \ 0 & 0 & -2 \end{pmatrix}$$

Target: QUBO with the above matrix.

Solution: QUBO optimum at $\mathbf{x} = (1, 0, 0)$ (or $(0, 1, 0)$, $(0, 0, 1)$, etc.) with value $-2$. Mapped back: partition $S = {0}$, cut edges ${(0,1), (0,2)}$, cut weight $= 2$, which is the maximum cut of the triangle.