[Rule] MinimumMultiwayCut to QUBO

[hmyuuu]

Source: MinimumMultiwayCut
Target: QUBO
Motivation: Enables solving minimum multiway cut on quantum annealers (D-Wave) and QUBO-based solvers via a direct Ising Hamiltonian with $kn$ binary variables.
Reference: Heidari, Dinneen & Delmas (2022), CDMTCS-565; Abbassi et al. (2026), arXiv:2601.00720

Reduction Algorithm

Notation:

• Source instance: graph $G=(V,E)$, $n=|V|$, edge weights $C({u,v})$, terminals $T={t_1,\ldots,t_k}$
• Target instance: QUBO matrix $Q \in \mathbb{R}^{kn \times kn}$
• $\alpha$ = penalty coefficient, $\alpha > \sum_{{u,v}\in E} C({u,v})$

Variable mapping:

Introduce $kn$ binary variables $x_{u,t}$ for each $u \in V$ and $t \in T$, where $x_{u,t} = 1$ means vertex $u$ is assigned to the component of terminal $t$. Variable index: $x_{u,t} \to u \cdot k + \mathrm{pos}(t)$.

Objective transformation (Heidari et al., eq. 2):

$$H_A = \alpha \left( \sum_{u \in V} \left(1 - \sum_{t \in T} x_{u,t}\right)^2 + \sum_{t \in T} \sum_{t' \neq t} x_{t,t'} \right)$$

$$H_B = \sum_{{u,v} \in E}\ \sum_{t \in T}\ \sum_{t' \neq t} C({u,v}), x_{u,t}, x_{v,t'}$$

$H_A$ enforces each vertex belongs to exactly one component (squared term) and each terminal $t$ is not misassigned to $t' \neq t$ (linear term), together forcing $x_{t,t}=1$. $H_B$ is the cut cost: for a feasible assignment each cut edge contributes $C({u,v})$ exactly once. Expanding $H = H_A + H_B$ in the binary variables yields the QUBO matrix $Q$.

Solution extraction: $E_m = {{u,v} \in E \mid x^_{u,t} = x^_{v,t'} = 1 \text{ for some } t \neq t'}$.

Size Overhead

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

Validation Method

• Solve small instances ($n \leq 6$, $k=3$) with BruteForce on both sides; verify $H(\mathbf{x}^*) = $ minimum cut cost with $H_A = 0$.
• Cross-check with the ILP reduction (issue [Rule] MinimumMultiwayCut to ILP #185) on the same instances.

Example

Source: $n=5$, $V={0,1,2,3,4}$, $T={0,2,4}$ ($k=3$), edges ${0,1}$:2, ${1,2}$:3, ${2,3}$:1, ${3,4}$:2, ${0,4}$:4, ${1,3}$:5. Set $\alpha=20$.

Variable index: $x_{u,t} \to u \cdot 3 + \mathrm{pos}(t)$ with $\mathrm{pos}(0)=0, \mathrm{pos}(2)=1, \mathrm{pos}(4)=2$. Total: $kn=15$ variables.

Optimal: $x_{0,0}=x_{1,2}=x_{2,2}=x_{3,2}=x_{4,4}=1$ (all others 0), giving components $\{0\}$, $\{1,2,3\}$, $\{4\}$.

• $H_A=0$ (valid partition, terminals correctly fixed)
• $H_B = C({0,1}) + C({0,4}) + C({3,4}) = 2+4+2 = \mathbf{8}$
• Ground-state energy $= 8 =$ minimum cut cost

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path; source problem (MinimumMultiwayCut) is new (see #184)
Non-trivial	✅ Pass	Genuine structural transformation: penalty Hamiltonian + cut-cost QUBO construction
Correctness	✅ Pass	Both references verified; claims match the cited papers
Well-written	⚠️ Warn	Algorithm omits explicit Q-matrix construction steps; overhead uses math symbols not code getters

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

The source problem MinimumMultiwayCut does not yet exist in the reduction graph (model issue #184 is the prerequisite). QUBO exists as a target. There is no existing path from MinimumMultiwayCut to QUBO since the source problem is entirely new. This reduction is novel and enables solving multiway cut on quantum annealers, which is a well-motivated use case.

The motivation field is adequate: it explains the quantum annealer / D-Wave use case and notes the kn binary variable count.

Non-trivial

The reduction constructs a QUBO matrix from scratch with:

• kn binary variables encoding vertex-to-terminal assignments
• Penalty Hamiltonian $H_A$ enforcing partition constraints (each vertex assigned to exactly one component, terminals pinned)
• Cut-cost Hamiltonian $H_B$ accumulating edge weights for cross-partition edges
• A penalty coefficient $\alpha$ that must exceed the total edge weight sum

This is a genuine gadget-based construction with auxiliary penalty terms, not a trivial relabeling or type coercion.

Correctness

Reference 1: Heidari, Dinneen & Delmas (2022), CDMTCS-565

• Verified: "An Equivalent QUBO Model to the Minimum Multi-Way Cut Problem", University of Auckland CDMTCS Research Report Series, report [Rule] PARTITION to COSINE PRODUCT INTEGRATION #565, September 2022.
• The paper presents exactly the QUBO formulation described in the issue with O(kn) binary variables and proves its correctness.
• Available at: https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/view-publication.php?selected-id=854

Reference 2: Abbassi et al. (2026), arXiv:2601.00720

• Verified: "Quantum Approaches to the Minimum Edge Multiway Cut Problem" by Ali Abbassi, Yann Dujardin, Eric Gourdin, Philippe Lacomme, and Caroline Prodhon. Submitted January 2, 2026; published at QUEST IS 2025.
• The paper cites Heidari et al. (2022) as reference [18] and uses the same QUBO formulation with kn binary variables.
• Confirms the Hamiltonian structure with penalty and cut-cost terms regulated by scalar parameter alpha.

Both references are real, properly attributed, and support the claims made in the issue.

Well-written

Strengths:

• All template sections are present and substantive
• Notation section clearly defines all symbols (G, V, E, n, k, T, alpha, variable indexing)
• The example is non-trivial (5 vertices, 3 terminals, 6 weighted edges) and fully worked through with explicit optimal assignment, H_A = 0 verification, and H_B = 8 = minimum cut cost
• Validation method is concrete (brute-force on both sides for small instances, cross-check with ILP reduction from [Rule] MinimumMultiwayCut to ILP #185)

Items to improve (warnings, not failures):

1. Algorithm detail gap: The reduction algorithm describes $H_A$ and $H_B$ symbolically but then says "Expanding $H = H_A + H_B$ in the binary variables yields the QUBO matrix $Q$" without showing how to compute individual Q-matrix entries $Q_{(u,t),(v,t')}$. A programmer implementing this would need the explicit expansion showing which diagonal entries get which coefficients and which off-diagonal entries arise from the cross-terms. Consider adding a step that enumerates: (a) diagonal entries from the linear terms in $H_A$, (b) off-diagonal entries from the squared penalty terms, and (c) off-diagonal entries from $H_B$.

2. Overhead expression format: The Size Overhead table uses kn (mathematical notation). When implemented, the overhead macro needs source-problem getter method names (e.g., num_terminals * num_vertices). This depends on the MinimumMultiwayCut model definition from [Model] MinimumMultiwayCut #184, so it cannot be fully validated yet. This is expected for a rule whose source model is not yet implemented.

3. Minor: The issue references "eq. 2" from Heidari et al. but the Abbassi et al. paper presents it as "Equation (1)". This is not an error (different papers number equations differently) but could be clarified.

Recommendations

• When implementing, the Q-matrix construction should be spelled out entry-by-entry in the reduce_to() method, following the expansion of $(1 - \sum_t x_{u,t})^2$ for the penalty terms.
• Depends on [Model] MinimumMultiwayCut #184 (MinimumMultiwayCut model) being implemented first.