[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.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Direct 1-step reduction replaces existing 3-step path via SpinGlass
Non-trivial	✅ Pass	Constructs a QUBO Q matrix with non-trivial diagonal/off-diagonal structure
Correctness	✅ Pass	Reference verified; formulation is mathematically correct
Well-written	⚠️ Warn	Minor notation gap in overhead table; otherwise complete and clear

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

An existing 3-step path already connects MaxCut to QUBO: MaxCut → SpinGlass (i32) → SpinGlass (f64) → QUBO (f64). The overall overhead of that path is num_vars = num_vertices, which is the same as the proposed direct reduction (num_vars = n). However, the proposed reduction is strictly better in path length (1 step vs 3 steps), eliminating two intermediate conversions. This reduces implementation complexity and avoids potential floating-point precision issues from the SpinGlass(f64) intermediate. Pass — the reduction improves the existing path.

The motivation field clearly explains why a direct path matters: quantum annealing pipelines benefit from avoiding the SpinGlass detour.

Non-trivial

The reduction constructs a QUBO Q matrix from the graph structure by:

1. Computing diagonal entries as the negated sum of incident edge weights for each vertex
2. Setting off-diagonal entries to twice the edge weight for each edge
3. Converting from maximization to minimization via negation

This involves genuine structural transformation — mapping graph topology into a matrix representation with specific algebraic relationships. It is not a trivial relabeling or type coercion. Pass.

Correctness

Reference: Glover, Kochenberger, Du, "A Tutorial on Formulating and Using QUBO Models" (2019), arXiv:1811.11538.

• The paper exists on arXiv with matching title, authors, and year. It is already in the project bibliography as glover2019.
• The paper is a well-known tutorial covering QUBO formulations of various combinatorial problems including MaxCut. The MaxCut-to-QUBO transformation described in the issue is a standard result.

Mathematical verification: The MaxCut objective maximizes $\sum_{(i,j) \in E} w_{ij}(x_i + x_j - 2x_ix_j)$. Since $x_i^2 = x_i$ for binary variables, this rewrites as $\mathbf{x}^T Q \mathbf{x}$ (negated for minimization) with $Q_{ii} = -\sum_{j:(i,j)\in E} w_{ij}$ and $Q_{ij} = 2w_{ij}$. This matches the issue exactly.

Example verification: Triangle graph (3 vertices, unit weights):

• Diagonal: each vertex has degree 2, so $Q_{ii} = -2$ ✓
• Off-diagonal: $Q_{01} = Q_{02} = Q_{12} = 2$ ✓
• QUBO optimum at $\mathbf{x} = (1,0,0)$: $x^T Q x = -2$, corresponding to cut weight 2 ✓
• MaxCut of triangle = 2 (any single vertex vs the other two) ✓

Pass.

Well-written

Information completeness: All required sections are present and substantive — Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, and Example.

Algorithm completeness: The reduction algorithm is step-by-step and implementable. Variable mapping is explicit (identity), Q matrix construction is precisely defined, and solution extraction is clear.

Symbol consistency: Symbols are mostly consistent across sections. The algorithm defines $n = |V|$, $m = |E|$, $w_{ij}$, and the Q matrix entries. The overhead table uses num_vars = n which correctly references the defined symbol.

Minor issue (warning): The overhead table uses the code metric name num_vars which correctly matches QUBO's size_fields. However, the issue does not explicitly note that QUBO only has num_vars as a size field — the number of nonzero entries in Q (which scales with $m$) is not tracked as a separate metric. This is acceptable since num_vars is the only available size field for QUBO.

Example quality: The triangle example is small enough to verify by hand, fully worked through with intermediate values, and demonstrates the reduction correctly. It could be slightly more interesting (e.g., a non-uniform weight graph) but is adequate.

Recommendations

• Consider using a weighted example (e.g., edges with weights 1, 2, 3) to better showcase how different edge weights affect the Q matrix construction. This would make the example more illustrative for the paper.
• The issue could note that this reduction naturally produces an upper-triangular Q matrix (as QUBO expects), since each undirected edge $(i,j)$ with $i < j$ contributes to $Q_{ij}$ only once.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Existing 3-step path has identical num_vars = num_vertices overhead; direct path saves intermediate steps only
Non-trivial	⚠️ Warn	Construction is mathematically equivalent to composing MaxCut->SpinGlass->QUBO, but does build the Q matrix directly
Correctness	✅ Pass	Reference (Glover et al. 2019) is valid and already in project bibliography; reduction math is correct
Well-written	⚠️ Warn	Minor issues: weight type mismatch (MaxCut uses i32 weights, QUBO uses f64), and QUBO matrix shown as upper-triangular but described with only upper entries

Overall: 1 passed, 3 warnings, 0 failed

---

Usefulness

An existing path already exists: MaxCut {graph: "SimpleGraph", weight: "i32"} -> SpinGlass {graph: "SimpleGraph", weight: "i32"} -> SpinGlass {graph: "SimpleGraph", weight: "f64"} -> QUBO {weight: "f64"} (3 steps).

The overall overhead of the existing path is num_vars = num_vertices — identical to the proposed direct reduction's num_vars = n (where n = num_vertices). Since the overhead is not strictly lower on any dimension, this does not meet the "improves existing reduction" criterion for a clear Pass.

However, the direct path has practical value: it eliminates 2 intermediate conversions (and the i32->f64 variant coercion step), simplifying solution extraction. The motivation ("essential for quantum annealing pipelines") is reasonable — a 1-step reduction is preferable to a 3-step chain when the overhead is the same.

Non-trivial

The reduction constructs a QUBO matrix directly from the graph: Q_ii = -sum of incident edge weights, Q_ij = 2 * w_ij. This is a genuine construction (not a variable relabeling or subtype cast), but it is mathematically equivalent to composing the existing MaxCut->SpinGlass (negate weights as J couplings) and SpinGlass->QUBO (apply s=2x-1 substitution) reductions. The direct formula is essentially the closed-form result of those two transformations.

This is borderline — it is a valid structural construction, but not a novel reduction technique. It shortens the path without introducing new algorithmic insight.

Correctness

Reference verification:

• Glover, Kochenberger & Du, "Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models" (2019) — confirmed in project bibliography as glover2019 (4OR, vol. 17, pp. 335-371, DOI: 10.1007/s10288-019-00424-y). The arxiv ID 1811.11538 matches.
• The MaxCut-to-QUBO formulation is a well-known standard result also covered in Lucas (2014), "Ising formulations of many NP problems" (already in bibliography as lucas2014).

Math verification:
The reduction is correct. MaxCut maximizes sum w_ij (x_i + x_j - 2 x_i x_j) over binary variables. Expanding:

• Linear terms: sum w_ij x_i + sum w_ij x_j = sum_i x_i * (sum_{j: (i,j) in E} w_ij)
• Quadratic terms: -2 sum w_ij x_i x_j
• Since x_i^2 = x_i, the diagonal of Q is -sum_{j: (i,j) in E} w_ij and off-diagonal is 2 * w_ij
• Negation converts maximization to QUBO minimization. Correct.

Example verification:
Triangle with unit weights: each vertex has degree 2, so Q_ii = -2. Off-diagonal Q_ij = 2 for each edge. The QUBO value at x = (1,0,0) is: (-2)(1) + 2(0) + 2(0) = -2. Max cut of triangle is 2 (any single vertex vs the other two). QUBO minimum = -2 = -(max cut). Correct.

Well-written

Information completeness: All template sections are present and substantive. Good.

Minor issues:

1. Weight type mismatch: The existing MaxCut implementation uses i32 weights (variant: {graph: "SimpleGraph", weight: "i32"}), but QUBO uses f64 weights. The issue does not mention this type conversion. The implementation will need to handle i32-to-f64 conversion, or a new MaxCut variant with f64 weights would need to exist. This should be clarified.

2. QUBO matrix representation: The example shows Q as an upper-triangular matrix (zeros below diagonal), which matches the QUBO convention in this codebase. However, the formula section describes Q_ij = 2 w_ij for edges without explicitly noting the upper-triangular convention. This is minor but could cause confusion if someone implements symmetric Q.

3. Symbol consistency: The issue defines n = |V|, m = |E|, and w_ij consistently across sections. The overhead table uses num_vars = n which correctly maps to the QUBO num_vars size field. Good.

4. Example quality: The triangle example is minimal but adequate — it exercises the reduction correctly. A slightly larger example (e.g., 4-vertex cycle as mentioned in Validation) would be more illustrative.

Recommendations

• Consider noting that this reduction requires MaxCut with f64-compatible weights (or an explicit i32->f64 cast), since the current MaxCut variant uses i32.
• The Lucas (2014) paper (lucas2014, already in bibliography) is an additional reference that covers this same formulation and could strengthen the citation.
• If the primary motivation is quantum annealing pipelines, the weight type alignment with QUBO is especially important to document.