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<f64>,
19}
20
21impl ReductionResult for ReductionPaintShopToQUBO {
22    type Source = PaintShop;
23    type Target = QUBO<f64>;
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(&self, target_solution: &[usize]) -> Vec<usize> {
32        target_solution.to_vec()
33    }
34}
35
36#[reduction(overhead = { num_vars = "num_cars" })]
37impl ReduceTo<QUBO<f64>> for PaintShop {
38    type Result = ReductionPaintShopToQUBO;
39
40    fn reduce_to(&self) -> Self::Result {
41        let n = self.num_cars();
42        let seq = self.sequence_indices();
43        let is_first = self.is_first();
44        let seq_len = seq.len();
45
46        let mut matrix = vec![vec![0.0f64; n]; n];
47
48        // For each adjacent pair in the sequence
49        for pos in 0..seq_len.saturating_sub(1) {
50            let a = seq[pos];
51            let b = seq[pos + 1];
52
53            // Skip if same car (always a color change, constant term)
54            if a == b {
55                continue;
56            }
57
58            let parity_a = is_first[pos];
59            let parity_b = is_first[pos + 1];
60
61            // Ensure we write to upper triangular: smaller index first
62            let (lo, hi) = if a < b { (a, b) } else { (b, a) };
63
64            if parity_a == parity_b {
65                // Same parity: color change when x_a != x_b
66                // Contribution: +1 to Q[a][a], +1 to Q[b][b], -2 to Q[lo][hi]
67                matrix[a][a] += 1.0;
68                matrix[b][b] += 1.0;
69                matrix[lo][hi] -= 2.0;
70            } else {
71                // Different parity: color change when x_a == x_b
72                // Contribution: -1 to Q[a][a], -1 to Q[b][b], +2 to Q[lo][hi]
73                matrix[a][a] -= 1.0;
74                matrix[b][b] -= 1.0;
75                matrix[lo][hi] += 2.0;
76            }
77        }
78
79        ReductionPaintShopToQUBO {
80            target: QUBO::from_matrix(matrix),
81        }
82    }
83}
84
85#[cfg(feature = "example-db")]
86pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
87    use crate::export::SolutionPair;
88
89    vec![crate::example_db::specs::RuleExampleSpec {
90        id: "paintshop_to_qubo",
91        build: || {
92            // Issue example: Sequence [A, B, C, A, D, B, D, C], 4 cars
93            let source = PaintShop::new(vec!["A", "B", "C", "A", "D", "B", "D", "C"]);
94            crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
95                source,
96                SolutionPair {
97                    source_config: vec![1, 0, 0, 0],
98                    target_config: vec![1, 0, 0, 0],
99                },
100            )
101        },
102    }]
103}
104
105#[cfg(test)]
106#[path = "../unit_tests/rules/paintshop_qubo.rs"]
107mod tests;
problemreductions/rules/paintshop_qubo.rs

problemreductions/rules/
paintshop_qubo.rs
