pymatching 0.1.0

Safe Rust bindings for the PyMatching quantum error-correction decoder
Documentation
use std::collections::HashMap;

use pymatching_cxx::{
    BatchDecodeResult as RawBatchDecodeResult, DecodeConfig as RawDecodeConfig,
    DecodeResult as RawDecodeResult, EdgeInput, EdgeRecord as RawEdgeRecord,
    GapBatchDecodeResult as RawGapBatchDecodeResult, GapDecodeResult as RawGapDecodeResult,
    Int64Matrix as RawInt64Matrix, MergeStrategy as RawMergeStrategy,
    NoiseResult as RawNoiseResult, RawMatchingHandle,
};

use crate::types::{DecodeOptions, EdgeData, EdgeRecord, MergeStrategy};
use crate::{MatchingError, Result};

/// A minimum-weight perfect matching decoder and its decoding graph.
///
/// Graph nodes represent detectors. Edges represent graphlike error
/// mechanisms and carry weights plus the output fault ids they toggle. Build a
/// graph directly with [`Matching::add_edge`], from a binary check matrix with
/// [`Matching::from_check_matrix`], or from Stim with
/// [`Matching::from_detector_error_model_with_options`].
#[derive(Default)]
pub struct Matching {
    inner: RawMatchingHandle,
    edge_cache: EdgeCache,
}

#[derive(Default)]
struct EdgeCache {
    edges: Vec<EdgeRecord>,
    edge_lookup: HashMap<(usize, usize), usize>,
    boundary_lookup: HashMap<usize, usize>,
}

impl Matching {
    pub(crate) fn from_raw_handle(inner: RawMatchingHandle) -> Self {
        let mut matching = Self {
            inner,
            edge_cache: EdgeCache::default(),
        };
        matching.refresh_edge_cache();
        matching
    }

    /// Adds an edge between detector nodes `node1` and `node2`.
    ///
    /// The default merge strategy is [`MergeStrategy::Disallow`], so adding a
    /// second edge between the same nodes returns an error. Node indices beyond
    /// the current graph size extend the graph.
    pub fn add_edge(&mut self, node1: usize, node2: usize, edge: EdgeData) -> Result<()> {
        self.add_edge_with_strategy(node1, node2, edge, MergeStrategy::Disallow)
    }

    /// Adds an edge between `node` and the virtual boundary.
    ///
    /// Virtual-boundary edges do not add a graph node. The default merge
    /// strategy is [`MergeStrategy::Disallow`].
    pub fn add_boundary_edge(&mut self, node: usize, edge: EdgeData) -> Result<()> {
        self.add_boundary_edge_with_strategy(node, edge, MergeStrategy::Disallow)
    }

    /// Returns whether an edge connects `node1` and `node2`.
    #[must_use]
    pub fn has_edge(&self, node1: usize, node2: usize) -> bool {
        self.inner.has_edge(node1, node2)
    }

    /// Returns whether `node` has an edge to the virtual boundary.
    #[must_use]
    pub fn has_boundary_edge(&self, node: usize) -> bool {
        self.inner.has_boundary_edge(node)
    }

    /// Returns the number of graph nodes, including explicit boundary nodes.
    #[must_use]
    pub fn num_nodes(&self) -> usize {
        self.inner.num_nodes()
    }

    /// Returns the number of ordinary and virtual-boundary edges.
    #[must_use]
    pub fn num_edges(&self) -> usize {
        self.inner.num_edges()
    }

    /// Returns the length of an unpacked decode prediction.
    ///
    /// This is one greater than the largest edge fault id, or a larger minimum
    /// set by [`Matching::ensure_num_fault_ids`].
    #[must_use]
    pub fn num_fault_ids(&self) -> usize {
        self.inner.num_fault_ids()
    }

    /// Returns the number of detector nodes, excluding explicit boundaries.
    #[must_use]
    pub fn num_detectors(&self) -> usize {
        self.inner.num_detectors()
    }

    /// Iterates over a snapshot of the explicit boundary-node indices.
    ///
    /// Virtual boundaries created by [`Matching::add_boundary_edge`] are not
    /// included.
    pub fn boundary(&self) -> impl Iterator<Item = usize> {
        self.inner.boundary_nodes().into_iter()
    }

    /// Alias for [`Matching::boundary`].
    pub fn boundary_nodes(&self) -> impl Iterator<Item = usize> {
        self.boundary()
    }

    /// Replaces the set of explicit boundary nodes.
    ///
    /// Boundary nodes may absorb an unmatched detection event and are excluded
    /// from [`Matching::num_detectors`].
    ///
    /// ```
    /// use pymatching::{EdgeData, Matching};
    ///
    /// let mut matching = Matching::default();
    /// matching.add_edge(0, 1, EdgeData::new(vec![]))?;
    /// matching.add_edge(1, 2, EdgeData::new(vec![]))?;
    /// matching.set_boundary_nodes([0, 2]);
    /// assert_eq!(matching.boundary().collect::<Vec<_>>(), vec![0, 2]);
    /// # Ok::<(), pymatching::MatchingError>(())
    /// ```
    pub fn set_boundary_nodes<I>(&mut self, nodes: I)
    where
        I: IntoIterator<Item = usize>,
    {
        let nodes: Vec<usize> = nodes.into_iter().collect();
        self.inner.set_boundary_nodes(&nodes);
    }

    /// Ensures predictions contain at least `min_num_fault_ids` bits.
    ///
    /// Existing edge fault ids can require a larger output and are never
    /// removed by this method.
    pub fn ensure_num_fault_ids(&mut self, min_num_fault_ids: usize) {
        self.inner.ensure_num_fault_ids(min_num_fault_ids);
    }

    /// Returns the attributes for the edge between two detector nodes.
    ///
    /// Endpoint order does not matter.
    pub fn edge_data(&self, node1: usize, node2: usize) -> Result<&EdgeData> {
        self.edge_cache
            .edge_lookup
            .get(&edge_key(node1, node2))
            .map(|&index| &self.edge_cache.edges[index].data)
            .ok_or(MatchingError::MissingEdge { node1, node2 })
    }

    /// Returns the attributes for `node`'s edge to the virtual boundary.
    pub fn boundary_edge_data(&self, node: usize) -> Result<&EdgeData> {
        self.edge_cache
            .boundary_lookup
            .get(&node)
            .map(|&index| &self.edge_cache.edges[index].data)
            .ok_or(MatchingError::MissingBoundaryEdge { node })
    }

    /// Returns a snapshot of every edge in the graph.
    ///
    /// Virtual-boundary edges have [`EdgeRecord::node2`] set to `None`.
    #[must_use]
    pub fn edges(&self) -> Vec<EdgeRecord> {
        self.edge_cache.edges.clone()
    }

    pub(crate) fn add_edge_with_strategy(
        &mut self,
        node1: usize,
        node2: usize,
        edge: EdgeData,
        merge_strategy: MergeStrategy,
    ) -> Result<()> {
        self.insert_edge_with_strategy(node1, node2, edge, merge_strategy)?;
        self.refresh_edge_cache();
        Ok(())
    }

    pub(crate) fn add_boundary_edge_with_strategy(
        &mut self,
        node: usize,
        edge: EdgeData,
        merge_strategy: MergeStrategy,
    ) -> Result<()> {
        self.insert_boundary_edge_with_strategy(node, edge, merge_strategy)?;
        self.refresh_edge_cache();
        Ok(())
    }

    pub(crate) fn refresh_edge_cache(&mut self) {
        self.edge_cache = EdgeCache::from_raw_records(self.inner.edges());
    }

    pub(crate) fn decode_syndrome_with_options_raw(
        &self,
        syndrome: &[u8],
        options: DecodeOptions,
    ) -> Result<RawDecodeResult> {
        self.inner
            .decode_with_config(syndrome, options.into_raw())
            .map_err(map_upstream_error)
    }

    pub(crate) fn decode_batch_with_options_raw(
        &self,
        shots: &[u8],
        num_rows: usize,
        num_cols: usize,
        options: DecodeOptions,
    ) -> Result<RawBatchDecodeResult> {
        self.inner
            .decode_batch(shots, num_rows, num_cols, options.into_raw())
            .map_err(map_upstream_error)
    }

    pub(crate) fn decode_to_edges_array_raw(
        &self,
        syndrome: &[u8],
        enable_correlations: bool,
    ) -> Result<RawInt64Matrix> {
        self.inner
            .decode_to_edges_array(syndrome, enable_correlations)
            .map_err(map_upstream_error)
    }

    pub(crate) fn decode_gap_raw(&self, syndrome: &[u8]) -> Result<RawGapDecodeResult> {
        self.inner.decode_gap(syndrome).map_err(map_upstream_error)
    }

    pub(crate) fn decode_gap_batch_raw(
        &self,
        shots: &[u8],
        num_rows: usize,
        num_cols: usize,
    ) -> Result<RawGapBatchDecodeResult> {
        self.inner
            .decode_gap_batch(shots, num_rows, num_cols)
            .map_err(map_upstream_error)
    }

    pub(crate) fn decode_to_matched_dets_array_raw(
        &self,
        syndrome: &[u8],
    ) -> Result<RawInt64Matrix> {
        self.inner
            .decode_to_matched_dets_array(syndrome)
            .map_err(map_upstream_error)
    }

    pub(crate) fn add_noise_raw(&self, seed: Option<u64>) -> Result<RawNoiseResult> {
        self.inner.add_noise(seed).map_err(map_upstream_error)
    }

    pub(crate) fn insert_edge_with_strategy(
        &mut self,
        node1: usize,
        node2: usize,
        edge: EdgeData,
        merge_strategy: MergeStrategy,
    ) -> Result<()> {
        validate_probability(&edge)?;
        self.inner
            .add_edge_with_merge_strategy(node1, node2, &edge.to_raw(), merge_strategy.into_raw())
            .map_err(map_upstream_error)
    }

    pub(crate) fn insert_boundary_edge_with_strategy(
        &mut self,
        node: usize,
        edge: EdgeData,
        merge_strategy: MergeStrategy,
    ) -> Result<()> {
        validate_probability(&edge)?;
        self.inner
            .add_boundary_edge_with_merge_strategy(node, &edge.to_raw(), merge_strategy.into_raw())
            .map_err(map_upstream_error)
    }
}

impl EdgeCache {
    fn from_raw_records(records: Vec<RawEdgeRecord>) -> Self {
        let mut edges = Vec::with_capacity(records.len());
        let mut edge_lookup = HashMap::with_capacity(records.len());
        let mut boundary_lookup = HashMap::with_capacity(records.len());

        for record in records {
            let edge = EdgeRecord::from_raw(record);
            let index = edges.len();
            match edge.node2 {
                Some(node2) => {
                    edge_lookup.insert(edge_key(edge.node1, node2), index);
                }
                None => {
                    boundary_lookup.insert(edge.node1, index);
                }
            }
            edges.push(edge);
        }

        Self {
            edges,
            edge_lookup,
            boundary_lookup,
        }
    }
}

fn validate_probability(edge: &EdgeData) -> Result<()> {
    if let Some(probability) = edge.error_probability {
        if !(0.0..=1.0).contains(&probability) {
            return Err(MatchingError::InvalidProbability { probability });
        }
    }

    Ok(())
}

fn map_upstream_error(error: cxx::Exception) -> MatchingError {
    MatchingError::Upstream(error.to_string())
}

fn edge_key(node1: usize, node2: usize) -> (usize, usize) {
    if node1 <= node2 {
        (node1, node2)
    } else {
        (node2, node1)
    }
}

impl EdgeData {
    fn to_raw(&self) -> EdgeInput {
        EdgeInput {
            fault_ids: self.fault_ids.iter().map(|&id| id as u64).collect(),
            weight: self.weight,
            error_probability: self.error_probability.unwrap_or(-1.0),
        }
    }
}

impl MergeStrategy {
    fn into_raw(self) -> RawMergeStrategy {
        match self {
            Self::Disallow => RawMergeStrategy::Disallow,
            Self::Independent => RawMergeStrategy::Independent,
            Self::SmallestWeight => RawMergeStrategy::SmallestWeight,
            Self::KeepOriginal => RawMergeStrategy::KeepOriginal,
            Self::Replace => RawMergeStrategy::Replace,
        }
    }
}

impl DecodeOptions {
    fn into_raw(self) -> RawDecodeConfig {
        RawDecodeConfig {
            return_weight: self.return_weight,
            bit_packed_shots: self.bit_packed_shots,
            bit_packed_predictions: self.bit_packed_predictions,
            enable_correlations: self.enable_correlations,
        }
    }
}