problemreductions/rules/
spinglass_qubo.rs

1//! Reductions between SpinGlass and QUBO problems.
2//!
3//! QUBO: minimize x^T Q x where x in {0, 1}^n
4//! SpinGlass: minimize sum J_ij s_i s_j + sum h_i s_i where s in {-1, +1}^n
5//!
6//! Transformation: s = 2x - 1 (so x=0 -> s=-1, x=1 -> s=+1)
7
8use crate::models::algebraic::QUBO;
9use crate::models::graph::SpinGlass;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use crate::topology::SimpleGraph;
13
14/// Result of reducing QUBO to SpinGlass.
15#[derive(Debug, Clone)]
16pub struct ReductionQUBOToSG {
17    target: SpinGlass<SimpleGraph, f64>,
18}
19
20impl ReductionResult for ReductionQUBOToSG {
21    type Source = QUBO<f64>;
22    type Target = SpinGlass<SimpleGraph, f64>;
23
24    fn target_problem(&self) -> &Self::Target {
25        &self.target
26    }
27
28    /// Solution maps directly (same binary encoding).
29    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
30        target_solution.to_vec()
31    }
32}
33
34#[reduction(
35    overhead = {
36        num_spins = "num_vars",
37    }
38)]
39impl ReduceTo<SpinGlass<SimpleGraph, f64>> for QUBO<f64> {
40    type Result = ReductionQUBOToSG;
41
42    fn reduce_to(&self) -> Self::Result {
43        let n = self.num_vars();
44        let matrix = self.matrix();
45
46        // Convert Q matrix to J interactions and h fields
47        // Using substitution s = 2x - 1:
48        // x = (s + 1) / 2
49        // x_i * x_j = ((s_i + 1)/2) * ((s_j + 1)/2) = (s_i*s_j + s_i + s_j + 1) / 4
50        //
51        // For off-diagonal terms Q_ij x_i x_j:
52        //   Q_ij * (s_i*s_j + s_i + s_j + 1) / 4
53        //   = Q_ij/4 * s_i*s_j + Q_ij/4 * s_i + Q_ij/4 * s_j + Q_ij/4
54        //
55        // For diagonal terms Q_ii x_i:
56        //   Q_ii * (s_i + 1) / 2 = Q_ii/2 * s_i + Q_ii/2
57        let mut interactions = Vec::new();
58        let mut onsite = vec![0.0; n];
59
60        for i in 0..n {
61            for j in i..n {
62                let q = matrix[i][j];
63                if q.abs() < 1e-10 {
64                    continue;
65                }
66
67                if i == j {
68                    // Diagonal: Q_ii * x_i = Q_ii/2 * s_i + Q_ii/2 (constant)
69                    onsite[i] += q / 2.0;
70                } else {
71                    // Off-diagonal: Q_ij * x_i * x_j
72                    // J_ij contribution
73                    let j_ij = q / 4.0;
74                    if j_ij.abs() > 1e-10 {
75                        interactions.push(((i, j), j_ij));
76                    }
77                    // h_i and h_j contributions
78                    onsite[i] += q / 4.0;
79                    onsite[j] += q / 4.0;
80                }
81            }
82        }
83
84        let target = SpinGlass::<SimpleGraph, f64>::new(n, interactions, onsite);
85
86        ReductionQUBOToSG { target }
87    }
88}
89
90/// Result of reducing SpinGlass to QUBO.
91#[derive(Debug, Clone)]
92pub struct ReductionSGToQUBO {
93    target: QUBO<f64>,
94}
95
96impl ReductionResult for ReductionSGToQUBO {
97    type Source = SpinGlass<SimpleGraph, f64>;
98    type Target = QUBO<f64>;
99
100    fn target_problem(&self) -> &Self::Target {
101        &self.target
102    }
103
104    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
105        target_solution.to_vec()
106    }
107}
108
109#[reduction(
110    overhead = {
111        num_vars = "num_spins",
112    }
113)]
114impl ReduceTo<QUBO<f64>> for SpinGlass<SimpleGraph, f64> {
115    type Result = ReductionSGToQUBO;
116
117    fn reduce_to(&self) -> Self::Result {
118        let n = self.num_spins();
119        let mut matrix = vec![vec![0.0; n]; n];
120
121        // Convert using s = 2x - 1:
122        // s_i * s_j = (2x_i - 1)(2x_j - 1) = 4x_i*x_j - 2x_i - 2x_j + 1
123        // s_i = 2x_i - 1
124        //
125        // J_ij * s_i * s_j = J_ij * (4x_i*x_j - 2x_i - 2x_j + 1)
126        //                  = 4*J_ij*x_i*x_j - 2*J_ij*x_i - 2*J_ij*x_j + J_ij
127        //
128        // h_i * s_i = h_i * (2x_i - 1) = 2*h_i*x_i - h_i
129        for ((i, j), j_val) in self.interactions() {
130            // Off-diagonal: 4 * J_ij
131            matrix[i][j] += 4.0 * j_val;
132            // Diagonal contributions: -2 * J_ij
133            matrix[i][i] -= 2.0 * j_val;
134            matrix[j][j] -= 2.0 * j_val;
135        }
136
137        // Convert h fields to diagonal
138        for (i, &h) in self.fields().iter().enumerate() {
139            // h_i * s_i -> 2*h_i*x_i
140            matrix[i][i] += 2.0 * h;
141        }
142
143        let target = QUBO::from_matrix(matrix);
144
145        ReductionSGToQUBO { target }
146    }
147}
148
149#[cfg(feature = "example-db")]
150pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
151    use crate::export::SolutionPair;
152
153    vec![
154        crate::example_db::specs::RuleExampleSpec {
155            id: "qubo_to_spinglass",
156            build: || {
157                let (n, edges) = crate::topology::small_graphs::petersen();
158                let mut matrix = vec![vec![0.0; n]; n];
159                for (i, row) in matrix.iter_mut().enumerate() {
160                    row[i] = -1.0 + 0.2 * i as f64;
161                }
162                for (idx, &(u, v)) in edges.iter().enumerate() {
163                    let (i, j) = if u < v { (u, v) } else { (v, u) };
164                    matrix[i][j] = if idx % 2 == 0 { 2.0 } else { -1.5 };
165                }
166                let source = QUBO::from_matrix(matrix);
167                crate::example_db::specs::rule_example_with_witness::<_, SpinGlass<SimpleGraph, f64>>(
168                    source,
169                    SolutionPair {
170                        source_config: vec![1, 0, 1, 1, 1, 0, 1, 0, 0, 1],
171                        target_config: vec![1, 0, 1, 1, 1, 0, 1, 0, 0, 1],
172                    },
173                )
174            },
175        },
176        crate::example_db::specs::RuleExampleSpec {
177            id: "spinglass_to_qubo",
178            build: || {
179                let (n, edges) = crate::topology::small_graphs::petersen();
180                let couplings: Vec<((usize, usize), f64)> = edges
181                    .iter()
182                    .enumerate()
183                    .map(|(i, &(u, v))| ((u, v), if i % 2 == 0 { 1.0 } else { -1.0 }))
184                    .collect();
185                let source = SpinGlass::new(n, couplings, vec![0.0; n]);
186                crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
187                    source,
188                    SolutionPair {
189                        source_config: vec![1, 0, 1, 1, 1, 0, 1, 0, 0, 1],
190                        target_config: vec![1, 0, 1, 1, 1, 0, 1, 0, 0, 1],
191                    },
192                )
193            },
194        },
195    ]
196}
197
198#[cfg(test)]
199#[path = "../unit_tests/rules/spinglass_qubo.rs"]
200mod tests;
problemreductions/rules/spinglass_qubo.rs

problemreductions/rules/
spinglass_qubo.rs
