problemreductions/rules/
paintshop_qubo.rs

1//! Reduction from PaintShop to QUBO.
2//!
3//! One binary QUBO variable per car. Variable x_i = 0 means car i gets color A
4//! at its first occurrence and color B at its second; x_i = 1 reverses.
5//! Adjacent pairs in the sequence contribute to the Q matrix based on their
6//! parity (first/second occurrence).
7//!
8//! Reference: Streif et al., 2021, Physical Review A 104, 012403.
9
10use crate::models::algebraic::QUBO;
11use crate::models::misc::PaintShop;
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14
15/// Result of reducing PaintShop to QUBO.
16#[derive(Debug, Clone)]
17pub struct ReductionPaintShopToQUBO {
18    target: QUBO<i64>,
19}
20
21impl ReductionResult for ReductionPaintShopToQUBO {
22    type Source = PaintShop;
23    type Target = QUBO<i64>;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    /// The QUBO solution maps directly back: car i's first occurrence gets
30    /// color x_i, second gets 1 - x_i.
31    fn extract_solution(
32        &self,
33        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
34    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
35        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
36
37        Ok(target_solution.to_vec())
38    }
39}
40
41#[reduction(transform = {
42    exact {
43        num_vars = "num_cars",
44    },
45    upper_bound {
46        num_quadratic_terms = "num_cars * (num_cars - 1) / 2",
47    },
48})]
49impl ReduceTo<QUBO<i64>> for PaintShop {
50    type Result = ReductionPaintShopToQUBO;
51
52    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
53        let n = self.num_cars();
54        let seq = self.sequence_indices();
55        let is_first = self.is_first();
56        let seq_len = seq.len();
57
58        let mut matrix = vec![vec![0i64; n]; n];
59        let overflow = |operation| {
60            crate::rules::ReductionError::integer_overflow::<PaintShop, QUBO<i64>>(operation)
61        };
62
63        // For each adjacent pair in the sequence
64        for pos in 0..seq_len.saturating_sub(1) {
65            let a = seq[pos];
66            let b = seq[pos + 1];
67
68            // Skip if same car (always a color change, constant term)
69            if a == b {
70                continue;
71            }
72
73            let parity_a = is_first[pos];
74            let parity_b = is_first[pos + 1];
75
76            // Ensure we write to upper triangular: smaller index first
77            let (lo, hi) = if a < b { (a, b) } else { (b, a) };
78
79            if parity_a == parity_b {
80                // Same parity: color change when x_a != x_b
81                // Contribution: +1 to Q[a][a], +1 to Q[b][b], -2 to Q[lo][hi]
82                matrix[a][a] = matrix[a][a]
83                    .checked_add(1)
84                    .ok_or_else(|| overflow("adding a PaintShop diagonal coefficient"))?;
85                matrix[b][b] = matrix[b][b]
86                    .checked_add(1)
87                    .ok_or_else(|| overflow("adding a PaintShop diagonal coefficient"))?;
88                matrix[lo][hi] = matrix[lo][hi]
89                    .checked_sub(2)
90                    .ok_or_else(|| overflow("adding a PaintShop interaction coefficient"))?;
91            } else {
92                // Different parity: color change when x_a == x_b
93                // Contribution: -1 to Q[a][a], -1 to Q[b][b], +2 to Q[lo][hi]
94                matrix[a][a] = matrix[a][a]
95                    .checked_sub(1)
96                    .ok_or_else(|| overflow("adding a PaintShop diagonal coefficient"))?;
97                matrix[b][b] = matrix[b][b]
98                    .checked_sub(1)
99                    .ok_or_else(|| overflow("adding a PaintShop diagonal coefficient"))?;
100                matrix[lo][hi] = matrix[lo][hi]
101                    .checked_add(2)
102                    .ok_or_else(|| overflow("adding a PaintShop interaction coefficient"))?;
103            }
104        }
105
106        Ok(ReductionPaintShopToQUBO {
107            target: QUBO::from_matrix(matrix).map_err(|message| {
108                crate::rules::ReductionError::construction::<PaintShop, QUBO<i64>>(message)
109            })?,
110        })
111    }
112}
113
114#[cfg(feature = "example-db")]
115pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
116    use crate::export::SolutionPair;
117
118    vec![crate::example_db::specs::RuleExampleSpec {
119        id: "paintshop_to_qubo",
120        build: || {
121            // Issue example: Sequence [A, B, C, A, D, B, D, C], 4 cars
122            let source = PaintShop::new(vec!["A", "B", "C", "A", "D", "B", "D", "C"]);
123            crate::example_db::specs::rule_example_with_witness::<_, QUBO<i64>>(
124                source,
125                SolutionPair {
126                    source_config: serde_json::json!(vec![true, false, false, false]),
127                    target_config: serde_json::json!(vec![true, false, false, false]),
128                },
129            )
130        },
131    }]
132}
133
134#[cfg(test)]
135#[path = "../unit_tests/rules/paintshop_qubo.rs"]
136mod tests;
problemreductions/rules/paintshop_qubo.rs

problemreductions/rules/
paintshop_qubo.rs
