problemreductions/rules/

spinglass_qubo.rs

//! Reductions between SpinGlass and QUBO problems.
//!
//! QUBO: minimize x^T Q x where x in {0, 1}^n
//! SpinGlass: minimize sum J_ij s_i s_j + sum h_i s_i where s in {-1, +1}^n
//!
//! Transformation: s = 2x - 1 (so x=0 -> s=-1, x=1 -> s=+1)

use crate::models::algebraic::QUBO;
use crate::models::graph::SpinGlass;
use crate::reduction;
use crate::rules::traits::{ReduceTo, ReductionResult};
use crate::topology::SimpleGraph;

/// Result of reducing QUBO to SpinGlass.
#[derive(Debug, Clone)]
pub struct ReductionQUBOToSG {
    target: SpinGlass<SimpleGraph, f64>,
}

impl ReductionResult for ReductionQUBOToSG {
    type Source = QUBO<f64>;
    type Target = SpinGlass<SimpleGraph, f64>;

    fn target_problem(&self) -> &Self::Target {
        &self.target
    }

    /// Solution maps directly (same binary encoding).
    fn extract_solution(
        &self,
        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;

        Ok(target_solution.iter().map(|&spin| spin == 1).collect())
    }
}

#[reduction(
    transform = exact {
        num_spins = "num_vars",
        num_interactions = "num_quadratic_terms",
    },
)]
impl ReduceTo<SpinGlass<SimpleGraph, f64>> for QUBO<f64> {
    type Result = ReductionQUBOToSG;

    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
        let n = self.num_vars();

        // Convert Q matrix to J interactions and h fields
        // Using substitution s = 2x - 1:
        // x = (s + 1) / 2
        // x_i * x_j = ((s_i + 1)/2) * ((s_j + 1)/2) = (s_i*s_j + s_i + s_j + 1) / 4
        //
        // For off-diagonal terms Q_ij x_i x_j:
        //   Q_ij * (s_i*s_j + s_i + s_j + 1) / 4
        //   = Q_ij/4 * s_i*s_j + Q_ij/4 * s_i + Q_ij/4 * s_j + Q_ij/4
        //
        // For diagonal terms Q_ii x_i:
        //   Q_ii * (s_i + 1) / 2 = Q_ii/2 * s_i + Q_ii/2
        let mut interactions = Vec::new();
        let mut onsite = vec![0.0; n];

        for &(i, j, q) in self.entries() {
            if i == j {
                // Diagonal: Q_ii * x_i = Q_ii/2 * s_i + Q_ii/2 (constant)
                onsite[i] += q / 2.0;
            } else {
                // Off-diagonal: Q_ij * x_i * x_j
                // J_ij contribution
                let j_ij = q / 4.0;
                interactions.push(((i, j), j_ij));
                // h_i and h_j contributions
                onsite[i] += q / 4.0;
                onsite[j] += q / 4.0;
            }
        }

        let target = SpinGlass::<SimpleGraph, f64>::new(n, interactions, onsite).map_err(
            |cause| {
                crate::rules::ReductionError::construction::<
                    QUBO<f64>,
                    SpinGlass<SimpleGraph, f64>,
                >(cause)
            },
        )?;

        Ok(ReductionQUBOToSG { target })
    }
}

/// Result of reducing SpinGlass to QUBO.
#[derive(Debug, Clone)]
pub struct ReductionSGToQUBO<W = f64> {
    target: QUBO<W>,
}

impl<W> ReductionResult for ReductionSGToQUBO<W>
where
    W: crate::types::WeightElement + crate::types::NumericSize + crate::variant::VariantParam,
{
    type Source = SpinGlass<SimpleGraph, W>;
    type Target = QUBO<W>;

    fn target_problem(&self) -> &Self::Target {
        &self.target
    }

    fn extract_solution(
        &self,
        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;

        Ok(target_solution
            .iter()
            .map(|&bit| if bit { 1 } else { -1 })
            .collect())
    }
}

// Each source interaction contributes to at most one quadratic coefficient.
#[reduction(transform = {
    exact {
        num_vars = "num_spins",
    },
    upper_bound {
        num_quadratic_terms = "num_interactions",
    },
})]
impl ReduceTo<QUBO<f64>> for SpinGlass<SimpleGraph, f64> {
    type Result = ReductionSGToQUBO<f64>;

    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
        let n = self.num_spins();
        let mut matrix = vec![vec![0.0; n]; n];

        // Convert using s = 2x - 1:
        // s_i * s_j = (2x_i - 1)(2x_j - 1) = 4x_i*x_j - 2x_i - 2x_j + 1
        // s_i = 2x_i - 1
        //
        // J_ij * s_i * s_j = J_ij * (4x_i*x_j - 2x_i - 2x_j + 1)
        //                  = 4*J_ij*x_i*x_j - 2*J_ij*x_i - 2*J_ij*x_j + J_ij
        //
        // h_i * s_i = h_i * (2x_i - 1) = 2*h_i*x_i - h_i
        for ((i, j), j_val) in self.interactions() {
            // Off-diagonal: 4 * J_ij
            matrix[i][j] += 4.0 * j_val;
            // Diagonal contributions: -2 * J_ij
            matrix[i][i] -= 2.0 * j_val;
            matrix[j][j] -= 2.0 * j_val;
        }

        // Convert h fields to diagonal
        for (i, &h) in self.fields().iter().enumerate() {
            // h_i * s_i -> 2*h_i*x_i
            matrix[i][i] += 2.0 * h;
        }

        let target = QUBO::from_matrix(matrix).map_err(|message| {
            crate::rules::ReductionError::construction::<SpinGlass<SimpleGraph, f64>, QUBO<f64>>(
                message,
            )
        })?;

        Ok(ReductionSGToQUBO { target })
    }
}

#[reduction(transform = {
    exact {
        num_vars = "num_spins",
    },
    upper_bound {
        num_quadratic_terms = "num_interactions",
    },
})]
impl ReduceTo<QUBO<i64>> for SpinGlass<SimpleGraph, i64> {
    type Result = ReductionSGToQUBO<i64>;

    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
        let n = self.num_spins();
        let mut matrix = vec![vec![0_i64; n]; n];
        let overflow = |operation| {
            crate::rules::ReductionError::integer_overflow::<SpinGlass<SimpleGraph, i64>, QUBO<i64>>(
                operation,
            )
        };

        for ((i, j), coupling) in self.interactions() {
            let interaction = coupling
                .checked_mul(4)
                .ok_or_else(|| overflow("scaling a spin-glass interaction"))?;
            matrix[i][j] = matrix[i][j]
                .checked_add(interaction)
                .ok_or_else(|| overflow("summing QUBO interaction coefficients"))?;
            let diagonal = coupling
                .checked_mul(2)
                .ok_or_else(|| overflow("scaling a spin-glass diagonal contribution"))?;
            matrix[i][i] = matrix[i][i]
                .checked_sub(diagonal)
                .ok_or_else(|| overflow("summing QUBO diagonal coefficients"))?;
            matrix[j][j] = matrix[j][j]
                .checked_sub(diagonal)
                .ok_or_else(|| overflow("summing QUBO diagonal coefficients"))?;
        }

        for (i, &field) in self.fields().iter().enumerate() {
            let diagonal = field
                .checked_mul(2)
                .ok_or_else(|| overflow("scaling a spin-glass field"))?;
            matrix[i][i] = matrix[i][i]
                .checked_add(diagonal)
                .ok_or_else(|| overflow("summing QUBO diagonal coefficients"))?;
        }

        Ok(ReductionSGToQUBO {
            target:
                QUBO::from_matrix(matrix).map_err(
                    crate::rules::ReductionError::construction::<
                        SpinGlass<SimpleGraph, i64>,
                        QUBO<i64>,
                    >,
                )?,
        })
    }
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
    use crate::export::SolutionPair;

    vec![
        crate::example_db::specs::RuleExampleSpec {
            id: "qubo_to_spinglass",
            build: || {
                let (n, edges) = crate::topology::small_graphs::petersen();
                let mut matrix = vec![vec![0.0; n]; n];
                for (i, row) in matrix.iter_mut().enumerate() {
                    row[i] = -1.0 + 0.2 * i as f64;
                }
                for (idx, &(u, v)) in edges.iter().enumerate() {
                    let (i, j) = if u < v { (u, v) } else { (v, u) };
                    matrix[i][j] = if idx % 2 == 0 { 2.0 } else { -1.5 };
                }
                let source = QUBO::from_matrix(matrix).unwrap();
                crate::example_db::specs::rule_example_with_witness::<_, SpinGlass<SimpleGraph, f64>>(
                    source,
                    SolutionPair {
                        source_config: serde_json::json!(vec![
                            true, false, true, true, true, false, true, false, false, true
                        ]),
                        target_config: serde_json::json!(vec![1, -1, 1, 1, 1, -1, 1, -1, -1, 1]),
                    },
                )
            },
        },
        crate::example_db::specs::RuleExampleSpec {
            id: "spinglass_to_qubo",
            build: || {
                let (n, edges) = crate::topology::small_graphs::petersen();
                let couplings: Vec<((usize, usize), f64)> = edges
                    .iter()
                    .enumerate()
                    .map(|(i, &(u, v))| ((u, v), if i % 2 == 0 { 1.0 } else { -1.0 }))
                    .collect();
                let source = SpinGlass::new(n, couplings, vec![0.0; n]).unwrap();
                crate::example_db::specs::rule_example_with_witness::<_, QUBO<f64>>(
                    source,
                    SolutionPair {
                        source_config: serde_json::json!(vec![1, -1, 1, 1, 1, -1, 1, -1, -1, 1]),
                        target_config: serde_json::json!(vec![
                            true, false, true, true, true, false, true, false, false, true
                        ]),
                    },
                )
            },
        },
        crate::example_db::specs::RuleExampleSpec {
            id: "integer_spinglass_to_qubo",
            build: || {
                let source =
                    SpinGlass::<SimpleGraph, i64>::new(2, vec![((0, 1), 1)], vec![0, 0]).unwrap();
                crate::example_db::specs::rule_example_with_witness::<_, QUBO<i64>>(
                    source,
                    SolutionPair {
                        source_config: serde_json::json!([1, -1]),
                        target_config: serde_json::json!([true, false]),
                    },
                )
            },
        },
    ]
}

#[cfg(test)]
#[path = "../unit_tests/rules/spinglass_qubo.rs"]
mod tests;