problemreductions/rules/
closestvectorproblem_qubo.rs

1//! Reduction from ClosestVectorProblem to QUBO.
2//!
3//! Encodes each bounded CVP coefficient with an exact in-range binary basis and
4//! expands the squared-distance objective into a QUBO over those bits.
5
6#[cfg(feature = "example-db")]
7use crate::export::SolutionPair;
8use crate::models::algebraic::{ClosestVectorProblem, QUBO};
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12#[derive(Debug, Clone)]
13struct EncodingSpan {
14    start: usize,
15    weights: Vec<usize>,
16}
17
18/// Result of reducing a bounded ClosestVectorProblem instance to QUBO.
19#[derive(Debug, Clone)]
20pub struct ReductionCVPToQUBO {
21    target: QUBO<f64>,
22    encodings: Vec<EncodingSpan>,
23}
24
25impl ReductionResult for ReductionCVPToQUBO {
26    type Source = ClosestVectorProblem<i32>;
27    type Target = QUBO<f64>;
28
29    fn target_problem(&self) -> &Self::Target {
30        &self.target
31    }
32
33    /// Reconstruct the source configuration offsets from the encoded QUBO bits.
34    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
35        self.encodings
36            .iter()
37            .map(|encoding| {
38                encoding
39                    .weights
40                    .iter()
41                    .enumerate()
42                    .map(|(offset, weight)| {
43                        target_solution
44                            .get(encoding.start + offset)
45                            .copied()
46                            .unwrap_or(0)
47                            * weight
48                    })
49                    .sum()
50            })
51            .collect()
52    }
53}
54
55#[cfg(feature = "example-db")]
56fn canonical_cvp_instance() -> ClosestVectorProblem<i32> {
57    ClosestVectorProblem::new(
58        vec![vec![2, 0], vec![1, 2]],
59        vec![2.8, 1.5],
60        vec![
61            crate::models::algebraic::VarBounds::bounded(-2, 4),
62            crate::models::algebraic::VarBounds::bounded(-2, 4),
63        ],
64    )
65}
66
67fn encoding_spans(problem: &ClosestVectorProblem<i32>) -> Vec<EncodingSpan> {
68    let mut start = 0usize;
69    let mut spans = Vec::with_capacity(problem.num_basis_vectors());
70    for bounds in problem.bounds() {
71        let weights = bounds
72            .exact_encoding_weights()
73            .into_iter()
74            .map(|weight| usize::try_from(weight).expect("encoding weights must be nonnegative"))
75            .collect::<Vec<_>>();
76        spans.push(EncodingSpan { start, weights });
77        start += spans.last().expect("just pushed").weights.len();
78    }
79    spans
80}
81
82fn gram_matrix(problem: &ClosestVectorProblem<i32>) -> Vec<Vec<f64>> {
83    let basis = problem.basis();
84    let n = basis.len();
85    let mut gram = vec![vec![0.0; n]; n];
86    for i in 0..n {
87        for j in i..n {
88            let dot = basis[i]
89                .iter()
90                .zip(&basis[j])
91                .map(|(&lhs, &rhs)| lhs as f64 * rhs as f64)
92                .sum::<f64>();
93            gram[i][j] = dot;
94            gram[j][i] = dot;
95        }
96    }
97    gram
98}
99
100fn at_times_target(problem: &ClosestVectorProblem<i32>) -> Vec<f64> {
101    problem
102        .basis()
103        .iter()
104        .map(|column| {
105            column
106                .iter()
107                .zip(problem.target())
108                .map(|(&entry, &target)| entry as f64 * target)
109                .sum()
110        })
111        .collect()
112}
113
114#[reduction(overhead = { num_vars = "num_encoding_bits" })]
115impl ReduceTo<QUBO<f64>> for ClosestVectorProblem<i32> {
116    type Result = ReductionCVPToQUBO;
117
118    fn reduce_to(&self) -> Self::Result {
119        let encodings = encoding_spans(self);
120        let total_bits = encodings
121            .last()
122            .map(|encoding| encoding.start + encoding.weights.len())
123            .unwrap_or(0);
124        let mut matrix = vec![vec![0.0; total_bits]; total_bits];
125
126        if total_bits == 0 {
127            return ReductionCVPToQUBO {
128                target: QUBO::from_matrix(matrix),
129                encodings,
130            };
131        }
132
133        let gram = gram_matrix(self);
134        let h = at_times_target(self);
135        let lowers = self
136            .bounds()
137            .iter()
138            .map(|bounds| {
139                bounds
140                    .lower
141                    .expect("CVP QUBO reduction requires finite lower bounds")
142            })
143            .map(|lower| lower as f64)
144            .collect::<Vec<_>>();
145        let g_lo_minus_h = (0..self.num_basis_vectors())
146            .map(|i| {
147                (0..self.num_basis_vectors())
148                    .map(|j| gram[i][j] * lowers[j])
149                    .sum::<f64>()
150                    - h[i]
151            })
152            .collect::<Vec<_>>();
153
154        let mut bit_terms = Vec::with_capacity(total_bits);
155        for (var_index, encoding) in encodings.iter().enumerate() {
156            for &weight in &encoding.weights {
157                bit_terms.push((var_index, weight as f64));
158            }
159        }
160
161        for u in 0..total_bits {
162            let (var_u, weight_u) = bit_terms[u];
163            matrix[u][u] =
164                gram[var_u][var_u] * weight_u * weight_u + 2.0 * weight_u * g_lo_minus_h[var_u];
165
166            for (v, &(var_v, weight_v)) in bit_terms.iter().enumerate().skip(u + 1) {
167                matrix[u][v] = 2.0 * gram[var_u][var_v] * weight_u * weight_v;
168            }
169        }
170
171        ReductionCVPToQUBO {
172            target: QUBO::from_matrix(matrix),
173            encodings,
174        }
175    }
176}
177
178#[cfg(feature = "example-db")]
179pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
180    vec![crate::example_db::specs::RuleExampleSpec {
181        id: "closestvectorproblem_to_qubo",
182        build: || {
183            crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
184                canonical_cvp_instance(),
185                SolutionPair {
186                    source_config: vec![3, 3],
187                    target_config: vec![0, 0, 1, 0, 0, 1],
188                },
189            )
190        },
191    }]
192}
193
194#[cfg(test)]
195#[path = "../unit_tests/rules/closestvectorproblem_qubo.rs"]
196mod tests;
problemreductions/rules/closestvectorproblem_qubo.rs

problemreductions/rules/
closestvectorproblem_qubo.rs
