pymatching 0.1.0

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

use ndarray::{Array1, Array2, ArrayView2};
use pymatching_cxx::EdgeRecord as RawEdgeRecord;

/// Attributes attached to an edge in a [`Matching`](crate::Matching) graph.
///
/// When a decoded correction contains this edge, every listed fault id is
/// toggled. The decoder minimizes `weight`; `error_probability` is optional
/// sampling metadata used by [`Matching::add_noise`](crate::Matching::add_noise).
///
/// ```
/// use pymatching::EdgeData;
///
/// let edge = EdgeData::new(vec![0, 2])
///     .with_weight(1.5)
///     .with_error_probability(0.1);
/// assert_eq!(edge.fault_ids, vec![0, 2]);
/// ```
#[derive(Debug, Clone, PartialEq)]
pub struct EdgeData {
    /// Output bits toggled when the correction uses this edge.
    pub fault_ids: Vec<usize>,
    /// Additive edge cost minimized by the decoder.
    pub weight: f64,
    /// Probability that this edge flips when sampling noise.
    pub error_probability: Option<f64>,
}

impl EdgeData {
    /// Creates edge data with weight `1.0` and no sampling probability.
    #[must_use]
    pub fn new(fault_ids: Vec<usize>) -> Self {
        Self {
            fault_ids,
            weight: 1.0,
            error_probability: None,
        }
    }

    /// Sets the additive matching weight.
    #[must_use]
    pub fn with_weight(mut self, weight: f64) -> Self {
        self.weight = weight;
        self
    }

    /// Sets the edge's sampling probability.
    ///
    /// Adding the edge fails if the probability is outside `0.0..=1.0`.
    #[must_use]
    pub fn with_error_probability(mut self, error_probability: f64) -> Self {
        self.error_probability = Some(error_probability);
        self
    }
}

/// An edge and its endpoints returned by [`Matching::edges`](crate::Matching::edges).
#[derive(Debug, Clone, PartialEq)]
pub struct EdgeRecord {
    /// First detector-node index.
    pub node1: usize,
    /// Second detector-node index, or `None` for a virtual-boundary edge.
    pub node2: Option<usize>,
    /// Weight, fault ids, and optional sampling probability.
    pub data: EdgeData,
}

impl EdgeRecord {
    /// Creates an edge record.
    #[must_use]
    pub fn new(node1: usize, node2: Option<usize>, data: EdgeData) -> Self {
        Self { node1, node2, data }
    }

    #[must_use]
    pub(crate) fn from_raw(record: RawEdgeRecord) -> Self {
        Self {
            node1: record.node1 as usize,
            node2: (!record.is_boundary).then_some(record.node2 as usize),
            data: EdgeData {
                fault_ids: record.fault_ids.into_iter().map(|id| id as usize).collect(),
                weight: record.weight,
                error_probability: normalize_error_probability(record.error_probability),
            },
        }
    }
}

fn normalize_error_probability(error_probability: f64) -> Option<f64> {
    (0.0..=1.0)
        .contains(&error_probability)
        .then_some(error_probability)
}

/// Policy used when an edge already exists between two endpoints.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum MergeStrategy {
    /// Reject the new parallel edge.
    Disallow,
    /// Merge independent error mechanisms and keep the original fault ids.
    ///
    /// Weights are treated as log-likelihood ratios and probabilities are
    /// combined as independent events.
    Independent,
    /// Keep whichever edge has the smaller weight.
    SmallestWeight,
    /// Ignore the new edge.
    KeepOriginal,
    /// Replace the existing edge with the new edge.
    Replace,
}

/// Detection-event matches keyed by detector index.
///
/// A value of `Some(j)` means the event was paired with detector `j`; `None`
/// means it was paired with a boundary.
pub type MatchedDetectors = HashMap<usize, Option<usize>>;

/// Options shared by single-shot and batch matching decoders.
///
/// All options default to `false`. Correlated decoding additionally requires a
/// matching built with correlations enabled; see
/// [`Matching::from_detector_error_model_with_options`](crate::Matching::from_detector_error_model_with_options).
///
/// ```
/// use pymatching::DecodeOptions;
///
/// let options = DecodeOptions::new()
///     .with_return_weight(true)
///     .with_enable_correlations(true);
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct DecodeOptions {
    pub(crate) return_weight: bool,
    pub(crate) bit_packed_shots: bool,
    pub(crate) bit_packed_predictions: bool,
    pub(crate) enable_correlations: bool,
}

/// GAP result for one syndrome.
///
/// GAP compares the two logical classes independently for each observable. It
/// returns the lower-weight class and the absolute difference between their
/// decoding weights. A larger gap means the decoder has a stronger preference
/// on its own weight scale; it is not a calibrated probability.
#[derive(Debug, Clone, PartialEq)]
pub struct GapPrediction {
    /// Lower-weight logical class for each observable.
    pub prediction: Array1<u8>,
    /// Absolute weight difference between the two classes for each observable.
    pub gaps: Array1<f64>,
}

/// GAP results for a batch of syndromes.
///
/// Both arrays have shape `(num_shots, num_fault_ids)`.
#[derive(Debug, Clone, PartialEq)]
pub struct GapBatchPrediction {
    /// Lower-weight logical class for each `(shot, observable)` pair.
    pub predictions: Array2<u8>,
    /// Absolute class-weight difference for each `(shot, observable)` pair.
    pub gaps: Array2<f64>,
}

impl Default for DecodeOptions {
    fn default() -> Self {
        Self::new()
    }
}

impl DecodeOptions {
    /// Creates options for raw, unpacked decoding without returned weights.
    #[must_use]
    pub fn new() -> Self {
        Self {
            return_weight: false,
            bit_packed_shots: false,
            bit_packed_predictions: false,
            enable_correlations: false,
        }
    }

    /// Controls whether matching weights are included in decode results.
    #[must_use]
    pub fn with_return_weight(mut self, return_weight: bool) -> Self {
        self.return_weight = return_weight;
        self
    }

    /// Controls whether each input shot is little-endian bit packed.
    ///
    /// Packed shot width is `ceil(num_detectors / 8)` bytes when the graph has
    /// no explicit boundary nodes. See [`crate::bit_packing`].
    #[must_use]
    pub fn with_bit_packed_shots(mut self, bit_packed_shots: bool) -> Self {
        self.bit_packed_shots = bit_packed_shots;
        self
    }

    /// Controls whether output fault-id predictions are little-endian bit packed.
    #[must_use]
    pub fn with_bit_packed_predictions(mut self, bit_packed_predictions: bool) -> Self {
        self.bit_packed_predictions = bit_packed_predictions;
        self
    }

    /// Enables native two-pass correlated matching.
    ///
    /// The graph must have been constructed with correlation data enabled.
    #[must_use]
    pub fn with_enable_correlations(mut self, enable_correlations: bool) -> Self {
        self.enable_correlations = enable_correlations;
        self
    }
}

/// Prediction and optional matching weight for one syndrome.
#[derive(Debug, Clone, PartialEq)]
pub struct DecodeResult {
    /// Parity prediction indexed by fault id.
    pub prediction: Array1<u8>,
    /// Sum of selected edge weights when requested in [`DecodeOptions`].
    pub weight: Option<f64>,
}

/// Predictions and optional matching weights for a batch of syndromes.
#[derive(Debug, Clone, PartialEq)]
pub struct BatchDecodeResult {
    /// Fault-id predictions with shape `(num_shots, num_fault_ids)` unless packed.
    pub predictions: Array2<u8>,
    /// One solution weight per shot when requested in [`DecodeOptions`].
    pub weights: Option<Array1<f64>>,
}

/// A sampled physical-fault vector and its resulting syndrome.
#[derive(Debug, Clone, PartialEq)]
pub struct NoiseSample {
    /// Sampled parity indexed by fault id.
    pub errors: Array1<u8>,
    /// Sampled detector syndrome indexed by graph node.
    pub syndrome: Array1<u8>,
}

/// Controls construction of a matching graph from a binary check matrix.
///
/// Columns must contain at most two ones. A column with two ones becomes an
/// ordinary edge; a column with one becomes a boundary edge. By default each
/// column has weight `1.0`, fault id equal to its column index, one repetition,
/// and an explicit boundary node.
#[derive(Debug, Clone, PartialEq)]
pub struct CheckMatrixOptions {
    pub(crate) weights: Option<Vec<f64>>,
    pub(crate) error_probabilities: Option<Vec<f64>>,
    pub(crate) faults_matrix: Option<StoredBinaryMatrix>,
    pub(crate) merge_strategy: MergeStrategy,
    pub(crate) repetitions: usize,
    pub(crate) timelike_weights: Option<Vec<f64>>,
    pub(crate) measurement_error_probabilities: Option<Vec<f64>>,
    pub(crate) use_virtual_boundary_node: bool,
}

impl Default for CheckMatrixOptions {
    fn default() -> Self {
        Self::new()
    }
}

impl CheckMatrixOptions {
    /// Creates the default check-matrix construction options.
    #[must_use]
    pub fn new() -> Self {
        Self {
            weights: None,
            error_probabilities: None,
            faults_matrix: None,
            merge_strategy: MergeStrategy::SmallestWeight,
            repetitions: 1,
            timelike_weights: None,
            measurement_error_probabilities: None,
            use_virtual_boundary_node: false,
        }
    }

    /// Sets one spacelike edge weight per check-matrix column.
    #[must_use]
    pub fn with_weights(mut self, weights: Vec<f64>) -> Self {
        self.weights = Some(weights);
        self
    }

    /// Sets one sampling probability per check-matrix column.
    ///
    /// Probabilities affect [`Matching::add_noise`](crate::Matching::add_noise),
    /// not decoding weights.
    #[must_use]
    pub fn with_error_probabilities(mut self, error_probabilities: Vec<f64>) -> Self {
        self.error_probabilities = Some(error_probabilities);
        self
    }

    /// Sets a binary `(num_fault_ids, num_columns)` fault-incidence matrix.
    ///
    /// Fault id `i` is attached to edge `j` exactly when element `(i, j)` is
    /// one. The view is copied into the options object.
    #[must_use]
    pub fn with_faults_matrix(mut self, faults_matrix: ArrayView2<'_, u8>) -> Self {
        self.faults_matrix = Some(StoredBinaryMatrix::from_array_view(faults_matrix));
        self
    }

    /// Sets the policy for duplicate graph edges.
    #[must_use]
    pub fn with_merge_strategy(mut self, merge_strategy: MergeStrategy) -> Self {
        self.merge_strategy = merge_strategy;
        self
    }

    /// Sets the number of syndrome-measurement rounds.
    ///
    /// Values above one add a time dimension and connect corresponding checks
    /// in consecutive rounds. The value must be at least one.
    #[must_use]
    pub fn with_repetitions(mut self, repetitions: usize) -> Self {
        self.repetitions = repetitions;
        self
    }

    /// Sets one timelike edge weight per check-matrix row.
    ///
    /// Used only when `repetitions > 1`; defaults to `1.0` per row.
    #[must_use]
    pub fn with_timelike_weights(mut self, timelike_weights: Vec<f64>) -> Self {
        self.timelike_weights = Some(timelike_weights);
        self
    }

    /// Sets one measurement-error sampling probability per check-matrix row.
    ///
    /// Used only when `repetitions > 1`.
    #[must_use]
    pub fn with_measurement_error_probabilities(
        mut self,
        measurement_error_probabilities: Vec<f64>,
    ) -> Self {
        self.measurement_error_probabilities = Some(measurement_error_probabilities);
        self
    }

    /// Controls whether columns with one nonzero entry use virtual boundaries.
    ///
    /// Virtual boundaries preserve a one-to-one mapping between check-matrix
    /// rows and graph nodes and are slightly more efficient. The default is
    /// `false` for parity with PyMatching's historical behavior.
    #[must_use]
    pub fn with_virtual_boundary_node(mut self, use_virtual_boundary_node: bool) -> Self {
        self.use_virtual_boundary_node = use_virtual_boundary_node;
        self
    }
}

#[derive(Debug, Clone, PartialEq)]
pub(crate) struct StoredBinaryMatrix {
    rows: usize,
    cols: usize,
    data: Vec<u8>,
}

impl StoredBinaryMatrix {
    fn from_array_view(matrix: ArrayView2<'_, u8>) -> Self {
        Self {
            rows: matrix.nrows(),
            cols: matrix.ncols(),
            data: matrix.iter().copied().collect(),
        }
    }

    pub(crate) fn nrows(&self) -> usize {
        self.rows
    }

    pub(crate) fn ncols(&self) -> usize {
        self.cols
    }

    pub(crate) fn get(&self, row: usize, col: usize) -> u8 {
        self.data[row * self.cols + col]
    }
}