[Rule] GraphPartitioning to QUBO

[zazabap]

Source: GraphPartitioning
Target: QUBO
Motivation: Enables solving graph bisection on quantum annealers (D-Wave); natural quadratic formulation with balance penalty.
Reference: Lucas, 2014, Ising formulations of many NP problems, Section 5.2

Reduction Algorithm

Notation:

• Source: undirected graph $G = (V, E)$, $n = |V|$ (even), $m = |E|$
• Target: QUBO with $n$ binary variables

Variable mapping: $x_i \in {0, 1}$ for each vertex $i$ ($x_i = 0$ if $i \in A$, $x_i = 1$ if $i \in B$).

QUBO objective:

$$H = \sum_{(u,v) \in E} (x_u + x_v - 2x_u x_v) + P \left(\sum_{i \in V} x_i - \frac{n}{2}\right)^2$$

The first term counts cut edges: $x_u + x_v - 2x_u x_v = x_u(1 - x_v) + x_v(1 - x_u)$ equals 1 iff $x_u \neq x_v$.

The second term is the balance penalty: zero iff exactly $n/2$ vertices are in $B$. Set $P > m$ to ensure balance is enforced.

Solution extraction: $A = {i : x_i = 0}$, $B = {i : x_i = 1}$.

Size Overhead

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

Validation Method

Closed-loop testing: solve GraphPartitioning by brute-force, solve the reduced QUBO, and verify both give the same optimal cut. Verify penalty $P$ is large enough.

Example

Source: 6 vertices, 9 edges: $(0,1), (0,2), (1,2), (1,3), (2,3), (2,4), (3,4), (3,5), (4,5)$.

QUBO: 6 variables, penalty $P = 10 > m = 9$.

$$H = \sum_{(u,v) \in E} (x_u + x_v - 2x_u x_v) + 10\left(\sum_i x_i - 3\right)^2$$

Optimal: $x = (0,0,0,1,1,1)$, cut term $= 3$, balance term $= 10 \cdot 0 = 0$, $H = 3$.

Infeasible example: $x = (0,0,0,0,1,1)$ ($|B| = 2 \neq 3$), cut $= 2$ but penalty $= 10 \cdot 1 = 10$, $H = 12$.