problemreductions/rules/
coloring_qubo.rs

1//! Reduction from KColoring to QUBO.
2//!
3//! One-hot encoding: x_{v,c} = 1 iff vertex v gets color c.
4//! QUBO variable index: v * K + c.
5//!
6//! Integer-scaled one-hot penalty: 2P*sum_v (1 - sum_c x_{v,c})^2
7//! Edge penalty: P*sum_{(u,v) in E} sum_c x_{u,c}*x_{v,c}
8//!
9//! QUBO has n*K variables.
10
11use crate::models::algebraic::QUBO;
12use crate::models::graph::KColoring;
13use crate::reduction;
14use crate::rules::traits::{ReduceTo, ReductionResult};
15use crate::topology::{Graph, SimpleGraph};
16use crate::variant::{KValue, K2, K3, KN};
17
18/// Result of reducing KColoring to QUBO.
19#[derive(Debug, Clone)]
20pub struct ReductionKColoringToQUBO<K: KValue> {
21    target: QUBO<i64>,
22    num_vertices: usize,
23    num_colors: usize,
24    feasible_energy: i64,
25    _phantom: std::marker::PhantomData<K>,
26}
27
28impl<K: KValue> ReductionResult for ReductionKColoringToQUBO<K> {
29    type Source = KColoring<K, SimpleGraph>;
30    type Target = QUBO<i64>;
31
32    fn target_problem(&self) -> &Self::Target {
33        &self.target
34    }
35
36    /// Decode one-hot: for each vertex, find which color bit is 1.
37    fn extract_solution(
38        &self,
39        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
40    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
41        let value =
42            crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
43        if !crate::rules::AggregateReductionResult::extract_value(self, value).0 {
44            return Err(crate::rules::ExtractionError::invalid(
45                "target QUBO configuration does not certify a proper coloring",
46            ));
47        }
48
49        (0..self.num_vertices)
50            .map(|vertex| {
51                let mut selected = (0..self.num_colors)
52                    .filter(|&color| target_solution[vertex * self.num_colors + color]);
53                match (selected.next(), selected.next()) {
54                    (Some(color), None) => Ok(color),
55                    (None, _) => Err(crate::rules::ExtractionError::invalid(format!(
56                        "assignment row {vertex} has no selected color"
57                    ))),
58                    (Some(_), Some(_)) => Err(crate::rules::ExtractionError::invalid(format!(
59                        "assignment row {vertex} has multiple selected colors"
60                    ))),
61                }
62            })
63            .collect()
64    }
65}
66
67impl<K: KValue> crate::rules::AggregateReductionResult for ReductionKColoringToQUBO<K> {
68    type Source = KColoring<K, SimpleGraph>;
69    type Target = QUBO<i64>;
70
71    fn target_problem(&self) -> &Self::Target {
72        &self.target
73    }
74
75    fn extract_value(&self, value: crate::types::Min<i64>) -> crate::types::Or {
76        crate::types::Or(value.0 == Some(self.feasible_energy))
77    }
78}
79
80/// Check dimensions and the omitted constant before allocating the matrix.
81fn coloring_qubo_parameters<K: KValue>(
82    n: usize,
83    k: usize,
84) -> Result<(usize, i64, i64), crate::rules::ReductionError> {
85    let overflow = |operation| {
86        crate::rules::ReductionError::integer_overflow::<KColoring<K, SimpleGraph>, QUBO<i64>>(
87            operation,
88        )
89    };
90    let nq = n
91        .checked_mul(k)
92        .ok_or_else(|| overflow("computing the number of QUBO variables"))?;
93    nq.checked_mul(nq)
94        .ok_or_else(|| overflow("computing the QUBO matrix size"))?;
95    let n_i64 = i64::try_from(n)
96        .map_err(|_| overflow("converting the vertex count to a QUBO coefficient"))?;
97    let penalty = n_i64
98        .checked_add(1)
99        .ok_or_else(|| overflow("computing the coloring penalty"))?;
100    let feasible_energy = n_i64
101        .checked_mul(penalty)
102        .and_then(|value| value.checked_mul(-2))
103        .ok_or_else(|| overflow("computing the zero-penalty coloring energy"))?;
104    Ok((nq, penalty, feasible_energy))
105}
106
107/// Helper function implementing the KColoring to QUBO reduction logic.
108fn reduce_kcoloring_to_qubo<K: KValue>(
109    problem: &KColoring<K, SimpleGraph>,
110) -> Result<ReductionKColoringToQUBO<K>, crate::rules::ReductionError> {
111    let k = problem.num_colors();
112    let n = problem.graph().num_vertices();
113    let edges = problem.graph().edges();
114    let overflow = |operation| {
115        crate::rules::ReductionError::integer_overflow::<KColoring<K, SimpleGraph>, QUBO<i64>>(
116            operation,
117        )
118    };
119    let (nq, penalty, feasible_energy) = coloring_qubo_parameters::<K>(n, k)?;
120
121    let diagonal_penalty = penalty
122        .checked_mul(-2)
123        .ok_or_else(|| overflow("computing a coloring diagonal coefficient"))?;
124    let one_hot_interaction = penalty
125        .checked_mul(4)
126        .ok_or_else(|| overflow("computing a one-hot interaction coefficient"))?;
127
128    let mut matrix = vec![vec![0i64; nq]; nq];
129
130    // Twice the former half-integral objective keeps every coefficient integral.
131    // One-hot penalty: 2P*sum_v (1 - sum_c x_{v,c})^2
132    // Expanding: (1 - sum_c x_{v,c})^2 = 1 - 2*sum_c x_{v,c} + (sum_c x_{v,c})^2
133    // = 1 - 2*sum_c x_{v,c} + sum_c x_{v,c}^2 + 2*sum_{c<c'} x_{v,c}*x_{v,c'}
134    // Since x^2 = x for binary: = 1 - sum_c x_{v,c} + 2*sum_{c<c'} x_{v,c}*x_{v,c'}
135    for v in 0..n {
136        for c in 0..k {
137            let idx = v * k + c;
138            // Diagonal: -2P
139            matrix[idx][idx] = matrix[idx][idx]
140                .checked_add(diagonal_penalty)
141                .ok_or_else(|| overflow("adding a coloring diagonal coefficient"))?;
142        }
143        // Off-diagonal within same vertex: 4P for each pair of colors
144        for c1 in 0..k {
145            for c2 in (c1 + 1)..k {
146                let idx1 = v * k + c1;
147                let idx2 = v * k + c2;
148                matrix[idx1][idx2] = matrix[idx1][idx2]
149                    .checked_add(one_hot_interaction)
150                    .ok_or_else(|| overflow("adding a one-hot interaction coefficient"))?;
151            }
152        }
153    }
154
155    // Edge penalty: P*sum_{(u,v) in E} sum_c x_{u,c}*x_{v,c}
156    for (u, v) in &edges {
157        for c in 0..k {
158            let idx_u = u * k + c;
159            let idx_v = v * k + c;
160            let (i, j) = if idx_u < idx_v {
161                (idx_u, idx_v)
162            } else {
163                (idx_v, idx_u)
164            };
165            matrix[i][j] = matrix[i][j]
166                .checked_add(penalty)
167                .ok_or_else(|| overflow("adding an edge-conflict coefficient"))?;
168        }
169    }
170
171    Ok(ReductionKColoringToQUBO {
172        target: QUBO::from_matrix(matrix).map_err(|message| {
173            crate::rules::ReductionError::construction::<KColoring<K, SimpleGraph>, QUBO<i64>>(
174                message,
175            )
176        })?,
177        num_vertices: n,
178        num_colors: k,
179        feasible_energy,
180        _phantom: std::marker::PhantomData,
181    })
182}
183
184// Register only the KN variant in the reduction graph
185#[reduction(
186    aggregate = custom,
187    transform = exact {
188        num_vars = "num_vertices * num_colors",
189    }
190)]
191impl ReduceTo<QUBO<i64>> for KColoring<KN, SimpleGraph> {
192    type Result = ReductionKColoringToQUBO<KN>;
193
194    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
195        reduce_kcoloring_to_qubo(self)
196    }
197}
198
199// Additional concrete impls for tests (not registered in reduction graph)
200macro_rules! impl_kcoloring_to_qubo {
201    ($($ktype:ty),+) => {$(
202        impl ReduceTo<QUBO<i64>> for KColoring<$ktype, SimpleGraph> {
203            type Result = ReductionKColoringToQUBO<$ktype>;
204            fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
205                reduce_kcoloring_to_qubo(self)
206            }
207        }
208    )+};
209}
210
211impl_kcoloring_to_qubo!(K2, K3);
212
213#[cfg(feature = "example-db")]
214pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
215    use crate::export::SolutionPair;
216    use crate::models::algebraic::QUBO;
217
218    vec![crate::example_db::specs::RuleExampleSpec {
219        id: "kcoloring_to_qubo",
220        build: || {
221            let (n, edges) = crate::topology::small_graphs::house();
222            let source = KColoring::<KN, _>::with_k(SimpleGraph::new(n, edges), 3);
223            crate::example_db::specs::rule_example_with_witness::<_, QUBO<i64>>(
224                source,
225                SolutionPair {
226                    source_config: serde_json::json!(vec![1, 2, 2, 1, 0]),
227                    target_config: serde_json::json!(vec![
228                        false, true, false, false, false, true, false, false, true, false, true,
229                        false, true, false, false
230                    ]),
231                },
232            )
233        },
234    }]
235}
236
237#[cfg(test)]
238#[path = "../unit_tests/rules/coloring_qubo.rs"]
239mod tests;
problemreductions/rules/coloring_qubo.rs

problemreductions/rules/
coloring_qubo.rs
