problemreductions/rules/
spinglass_maxcut.rs

1//! Reductions between SpinGlass and MaxCut problems.
2//!
3//! MaxCut -> SpinGlass: Direct mapping, edge weights become J couplings.
4//! SpinGlass -> MaxCut: Requires ancilla vertex for onsite terms.
5
6use crate::models::graph::MaxCut;
7use crate::models::graph::SpinGlass;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::types::WeightElement;
12use num_traits::Zero;
13
14/// Result of reducing MaxCut to SpinGlass.
15#[derive(Debug, Clone)]
16pub struct ReductionMaxCutToSG<W> {
17    target: SpinGlass<SimpleGraph, W>,
18}
19
20impl<W> ReductionResult for ReductionMaxCutToSG<W>
21where
22    W: WeightElement
23        + crate::variant::VariantParam
24        + PartialOrd
25        + num_traits::Num
26        + num_traits::Zero
27        + num_traits::Bounded
28        + std::ops::AddAssign
29        + std::ops::Mul<Output = W>
30        + From<i32>,
31{
32    type Source = MaxCut<SimpleGraph, W>;
33    type Target = SpinGlass<SimpleGraph, W>;
34
35    fn target_problem(&self) -> &Self::Target {
36        &self.target
37    }
38
39    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
40        target_solution.to_vec()
41    }
42}
43
44#[reduction(
45    overhead = {
46        num_spins = "num_vertices",
47        num_interactions = "num_edges",
48    }
49)]
50impl ReduceTo<SpinGlass<SimpleGraph, i32>> for MaxCut<SimpleGraph, i32> {
51    type Result = ReductionMaxCutToSG<i32>;
52
53    fn reduce_to(&self) -> Self::Result {
54        let n = self.graph().num_vertices();
55        let edges_with_weights = self.edges();
56
57        // MaxCut: maximize sum of w_ij for edges (i,j) where s_i != s_j
58        // SpinGlass: minimize sum of J_ij * s_i * s_j
59        //
60        // For MaxCut, we want to maximize cut, which means:
61        // - When s_i != s_j (opposite spins), edge contributes to cut
62        // - s_i * s_j = -1 when opposite, +1 when same
63        //
64        // To convert: maximize sum(w_ij * [s_i != s_j])
65        //           = maximize sum(w_ij * (1 - s_i*s_j)/2)
66        //           = constant - minimize sum(w_ij * s_i*s_j / 2)
67        //
68        // So J_ij = -w_ij / 2 would work, but since we need to relate
69        // the problems directly, we use J_ij = w_ij and negate.
70        // Actually, for a proper reduction, we set J_ij = w_ij.
71        // MaxCut wants to maximize edges cut, SpinGlass minimizes energy.
72        // When J > 0 (antiferromagnetic), opposite spins lower energy.
73        // So maximizing cut = minimizing Ising energy with J = w.
74        let interactions: Vec<((usize, usize), i32)> = edges_with_weights
75            .into_iter()
76            .map(|(u, v, w)| ((u, v), w))
77            .collect();
78
79        // No onsite terms for pure MaxCut
80        let onsite = vec![0i32; n];
81
82        let target = SpinGlass::<SimpleGraph, i32>::new(n, interactions, onsite);
83
84        ReductionMaxCutToSG { target }
85    }
86}
87
88/// Result of reducing SpinGlass to MaxCut.
89#[derive(Debug, Clone)]
90pub struct ReductionSGToMaxCut<W> {
91    target: MaxCut<SimpleGraph, W>,
92    /// Ancilla vertex index (None if no ancilla needed).
93    ancilla: Option<usize>,
94}
95
96impl<W> ReductionResult for ReductionSGToMaxCut<W>
97where
98    W: WeightElement
99        + crate::variant::VariantParam
100        + PartialOrd
101        + num_traits::Num
102        + num_traits::Zero
103        + num_traits::Bounded
104        + std::ops::AddAssign
105        + std::ops::Mul<Output = W>
106        + From<i32>,
107{
108    type Source = SpinGlass<SimpleGraph, W>;
109    type Target = MaxCut<SimpleGraph, W>;
110
111    fn target_problem(&self) -> &Self::Target {
112        &self.target
113    }
114
115    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
116        match self.ancilla {
117            None => target_solution.to_vec(),
118            Some(anc) => {
119                // If ancilla is 1, flip all bits; then remove ancilla
120                let mut sol = target_solution.to_vec();
121                if sol[anc] == 1 {
122                    for x in sol.iter_mut() {
123                        *x = 1 - *x;
124                    }
125                }
126                sol.remove(anc);
127                sol
128            }
129        }
130    }
131}
132
133#[reduction(
134    overhead = {
135        num_vertices = "num_spins",
136        num_edges = "num_interactions",
137    }
138)]
139impl ReduceTo<MaxCut<SimpleGraph, i32>> for SpinGlass<SimpleGraph, i32> {
140    type Result = ReductionSGToMaxCut<i32>;
141
142    fn reduce_to(&self) -> Self::Result {
143        let n = self.num_spins();
144        let interactions = self.interactions();
145        let fields = self.fields();
146
147        // Check if we need an ancilla vertex for onsite terms
148        let need_ancilla = fields.iter().any(|h| !h.is_zero());
149        let total_vertices = if need_ancilla { n + 1 } else { n };
150        let ancilla_idx = if need_ancilla { Some(n) } else { None };
151
152        let mut edges = Vec::new();
153        let mut weights = Vec::new();
154
155        // Add interaction edges
156        for ((i, j), w) in interactions {
157            edges.push((i, j));
158            weights.push(w);
159        }
160
161        // Add onsite terms as edges to ancilla
162        // h_i * s_i can be modeled as an edge to ancilla with weight h_i
163        // When s_i and s_ancilla are opposite, the edge is cut
164        if need_ancilla {
165            for (i, h) in fields.iter().enumerate() {
166                if !h.is_zero() {
167                    edges.push((i, n));
168                    weights.push(*h);
169                }
170            }
171        }
172
173        let target = MaxCut::new(SimpleGraph::new(total_vertices, edges), weights);
174
175        ReductionSGToMaxCut {
176            target,
177            ancilla: ancilla_idx,
178        }
179    }
180}
181
182#[cfg(test)]
183#[path = "../unit_tests/rules/spinglass_maxcut.rs"]
184mod tests;
problemreductions/rules/spinglass_maxcut.rs

problemreductions/rules/
spinglass_maxcut.rs
