problemreductions/rules/

spinglass_maxcut.rs

//! Reductions between SpinGlass and MaxCut problems.
//!
//! MaxCut -> SpinGlass: Direct mapping, edge weights become J couplings.
//! SpinGlass -> MaxCut: Requires ancilla vertex for onsite terms.

use crate::models::graph::MaxCut;
use crate::models::graph::SpinGlass;
use crate::reduction;
use crate::rules::traits::{ReduceTo, ReductionResult};
use crate::topology::{Graph, SimpleGraph};
use crate::types::WeightElement;
use num_traits::Zero;

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

impl<W> ReductionResult for ReductionMaxCutToSG<W>
where
    W: WeightElement
        + crate::variant::VariantParam
        + PartialOrd
        + num_traits::Num
        + num_traits::Zero
        + num_traits::Bounded
        + std::ops::AddAssign
        + std::ops::Mul<Output = W>,
{
    type Source = MaxCut<SimpleGraph, W>;
    type Target = SpinGlass<SimpleGraph, 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(|&spin| spin == 1).collect())
    }
}

#[reduction(
    transform = exact {
        num_spins = "num_vertices",
        num_interactions = "num_edges",
    }
)]
impl ReduceTo<SpinGlass<SimpleGraph, i64>> for MaxCut<SimpleGraph, i64> {
    type Result = ReductionMaxCutToSG<i64>;

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

        // MaxCut: maximize sum of w_ij for edges (i,j) where s_i != s_j
        // SpinGlass: minimize sum of J_ij * s_i * s_j
        //
        // For MaxCut, we want to maximize cut, which means:
        // - When s_i != s_j (opposite spins), edge contributes to cut
        // - s_i * s_j = -1 when opposite, +1 when same
        //
        // To convert: maximize sum(w_ij * [s_i != s_j])
        //           = maximize sum(w_ij * (1 - s_i*s_j)/2)
        //           = constant - minimize sum(w_ij * s_i*s_j / 2)
        //
        // So J_ij = -w_ij / 2 would work, but since we need to relate
        // the problems directly, we use J_ij = w_ij and negate.
        // Actually, for a proper reduction, we set J_ij = w_ij.
        // MaxCut wants to maximize edges cut, SpinGlass minimizes energy.
        // When J > 0 (antiferromagnetic), opposite spins lower energy.
        // So maximizing cut = minimizing Ising energy with J = w.
        let interactions: Vec<((usize, usize), i64)> = edges_with_weights
            .into_iter()
            .map(|(u, v, w)| ((u, v), w))
            .collect();

        // No onsite terms for pure MaxCut
        let onsite = vec![0i64; n];

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

        Ok(ReductionMaxCutToSG { target })
    }
}

/// Result of reducing SpinGlass to MaxCut.
#[derive(Debug, Clone)]
pub struct ReductionSGToMaxCut<W> {
    target: MaxCut<SimpleGraph, W>,
    /// Ancilla vertex index (None if no ancilla needed).
    ancilla: Option<usize>,
}

impl<W> ReductionResult for ReductionSGToMaxCut<W>
where
    W: WeightElement
        + crate::variant::VariantParam
        + PartialOrd
        + num_traits::Num
        + num_traits::Zero
        + num_traits::Bounded
        + std::ops::AddAssign
        + std::ops::Mul<Output = W>,
{
    type Source = SpinGlass<SimpleGraph, W>;
    type Target = MaxCut<SimpleGraph, 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({
            match self.ancilla {
                None => target_solution
                    .iter()
                    .map(|&side| if side { 1 } else { -1 })
                    .collect(),
                Some(anc) => {
                    // Normalize the ancilla to spin +1 so its edge contributes h_i * s_i.
                    let mut sol = target_solution.to_vec();
                    if !sol[anc] {
                        for x in sol.iter_mut() {
                            *x = !*x;
                        }
                    }
                    sol.remove(anc);
                    sol.into_iter()
                        .map(|side| if side { 1 } else { -1 })
                        .collect()
                }
            }
        })
    }
}

#[reduction(
    transform = upper_bound {
        num_vertices = "num_spins + 1",
        num_edges = "num_interactions + num_spins",
    }
)]
impl ReduceTo<MaxCut<SimpleGraph, i64>> for SpinGlass<SimpleGraph, i64> {
    type Result = ReductionSGToMaxCut<i64>;

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

        // Check if we need an ancilla vertex for onsite terms
        let need_ancilla = fields.iter().any(|h| !h.is_zero());
        let total_vertices = if need_ancilla { n + 1 } else { n };
        let ancilla_idx = if need_ancilla { Some(n) } else { None };

        let mut edges = Vec::new();
        let mut weights = Vec::new();

        // Add interaction edges
        for ((i, j), w) in interactions {
            edges.push((i, j));
            weights.push(w);
        }

        // Add onsite terms as edges to ancilla
        // h_i * s_i can be modeled as an edge to ancilla with weight h_i
        // When s_i and s_ancilla are opposite, the edge is cut
        if need_ancilla {
            for (i, h) in fields.iter().enumerate() {
                if !h.is_zero() {
                    edges.push((i, n));
                    weights.push(*h);
                }
            }
        }

        let target = MaxCut::new(SimpleGraph::new(total_vertices, edges), weights);

        Ok(ReductionSGToMaxCut {
            target,
            ancilla: ancilla_idx,
        })
    }
}

#[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: "maxcut_to_spinglass",
            build: || {
                let (n, edges) = crate::topology::small_graphs::petersen();
                let source = MaxCut::unweighted(SimpleGraph::new(n, edges));
                crate::example_db::specs::rule_example_with_witness::<_, SpinGlass<SimpleGraph, i64>>(
                    source,
                    SolutionPair {
                        source_config: serde_json::json!(vec![
                            false, true, false, true, false, true, false, 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_maxcut",
            build: || {
                let (n, edges) = crate::topology::small_graphs::petersen();
                let couplings: Vec<((usize, usize), i64)> = edges
                    .iter()
                    .enumerate()
                    .map(|(i, &(u, v))| ((u, v), if i % 2 == 0 { 1 } else { -1 }))
                    .collect();
                let source = SpinGlass::new(n, couplings, vec![0; n]).unwrap();
                crate::example_db::specs::rule_example_with_witness::<_, MaxCut<SimpleGraph, i64>>(
                    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
                        ]),
                    },
                )
            },
        },
    ]
}

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