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

problemreductions/rules/
coloring_qubo.rs
