pymatching 0.1.0

Safe Rust bindings for the PyMatching quantum error-correction decoder
Documentation
use ndarray::{Array1, Array2, ArrayView1, ArrayView2};

use crate::bit_packing::required_packed_bytes;
use crate::types::{
    BatchDecodeResult, DecodeOptions, DecodeResult, GapBatchPrediction, GapPrediction,
    MatchedDetectors, NoiseSample,
};
use crate::{Matching, MatchingError, Result};

impl Matching {
    /// Decodes one binary syndrome with raw minimum-weight perfect matching.
    ///
    /// `syndrome[i]` is the detection-event bit for detector node `i`. The
    /// returned vector is indexed by fault id: bit `j` is one exactly when the
    /// selected correction toggles fault id `j` an odd number of times.
    ///
    /// # Errors
    ///
    /// Returns an error for an invalid syndrome shape or when no correction is
    /// consistent with the syndrome.
    pub fn decode(&self, syndrome: ArrayView1<'_, u8>) -> Result<Array1<u8>> {
        Ok(self
            .decode_with_options(syndrome, DecodeOptions::new())?
            .prediction)
    }

    /// Decodes one syndrome with explicit weight and correlation options.
    ///
    /// Set [`DecodeOptions::with_return_weight`] to include the sum of selected
    /// edge weights. Set [`DecodeOptions::with_enable_correlations`] for native
    /// two-pass correlated matching; this requires a graph constructed with
    /// correlations enabled. Bit-packing options apply only to batch decoding.
    ///
    /// ```
    /// use ndarray::array;
    /// use pymatching::{DecodeOptions, EdgeData, Matching};
    ///
    /// let mut matching = Matching::default();
    /// matching.add_boundary_edge(0, EdgeData::new(vec![0]).with_weight(2.0))?;
    /// let result = matching.decode_with_options(
    ///     array![1_u8].view(),
    ///     DecodeOptions::new().with_return_weight(true),
    /// )?;
    /// assert_eq!(result.prediction.to_vec(), vec![1]);
    /// assert_eq!(result.weight, Some(2.0));
    /// # Ok::<(), pymatching::MatchingError>(())
    /// ```
    pub fn decode_with_options(
        &self,
        syndrome: ArrayView1<'_, u8>,
        options: DecodeOptions,
    ) -> Result<DecodeResult> {
        let raw = with_contiguous_1d(syndrome, |syndrome| {
            self.decode_syndrome_with_options_raw(syndrome, options)
        })?;
        Ok(DecodeResult {
            prediction: Array1::from_vec(raw.prediction),
            weight: raw.has_weight.then_some(raw.weight),
        })
    }

    /// Decodes both logical classes and returns a hard prediction plus GAP.
    ///
    /// The prediction is exactly the underlying hard decoder's prediction. For
    /// each logical observable, the decoder also solves the complementary class,
    /// and `gaps` contains the absolute difference between the two weights.
    ///
    /// Logical cuts are inferred from edge fault ids. Detector coordinates and
    /// Pauli-basis annotations are not used, so the same method handles X- and
    /// Z-basis memory experiments. Every observable must define one connected
    /// graph cut, and the matching must come from an unmodified detector error
    /// model. Correlations are used automatically when the matching was built
    /// with them enabled.
    ///
    /// ```
    /// use ndarray::array;
    /// use pymatching::Matching;
    ///
    /// let dem: stim::DetectorErrorModel = "\
    ///     error(0.1) D0 L0\n\
    ///     error(0.1) D0 D1\n\
    ///     error(0.2) D1\n".parse()?;
    /// let matching = Matching::from_detector_error_model_with_options(&dem, false)?;
    /// let result = matching.decode_gap(array![1_u8, 0].view())?;
    /// assert_eq!(result.prediction.len(), 1);
    /// assert!(result.gaps[0] >= 0.0);
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn decode_gap(&self, syndrome: ArrayView1<'_, u8>) -> Result<GapPrediction> {
        let raw = with_contiguous_1d(syndrome, |syndrome| self.decode_gap_raw(syndrome))?;
        Ok(GapPrediction {
            prediction: Array1::from_vec(raw.prediction),
            gaps: Array1::from_vec(raw.gaps),
        })
    }

    /// Decodes both logical classes for every shot and returns predictions and gaps.
    ///
    /// `shots` must be an unpacked binary array with shape
    /// `(num_shots, self.num_detectors())`; GAP batch decoding does not use the
    /// bit-packing options from [`DecodeOptions`].
    ///
    /// Both returned arrays have shape `(shots.nrows(), self.num_fault_ids())`.
    /// See [`Matching::decode_gap`] for graph requirements and GAP semantics.
    ///
    /// ```
    /// use ndarray::array;
    /// use pymatching::Matching;
    ///
    /// let dem: stim::DetectorErrorModel = "\
    ///     error(0.1) D0 L0\n\
    ///     error(0.1) D0 D1\n\
    ///     error(0.2) D1\n".parse()?;
    /// let matching = Matching::from_detector_error_model_with_options(&dem, false)?;
    /// let result = matching.decode_gap_batch(array![[0_u8, 0], [1, 0]].view())?;
    /// assert_eq!(result.predictions.dim(), (2, 1));
    /// assert_eq!(result.gaps.dim(), (2, 1));
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn decode_gap_batch(&self, shots: ArrayView2<'_, u8>) -> Result<GapBatchPrediction> {
        let num_rows = shots.nrows();
        let raw = with_contiguous_2d(shots, |shots, rows, cols| {
            self.decode_gap_batch_raw(shots, rows, cols)
        })?;
        if raw.rows as usize != num_rows || raw.cols as usize != self.num_fault_ids() {
            return Err(MatchingError::Upstream(
                "bridge returned an invalid GAP batch shape".to_string(),
            ));
        }
        Ok(GapBatchPrediction {
            predictions: array2_from_u8(raw.predictions, raw.rows, raw.cols)?,
            gaps: array2_from_f64(raw.gaps, raw.rows, raw.cols)?,
        })
    }

    /// Decodes a batch of unpacked binary syndromes with raw matching.
    ///
    /// `shots` has shape `(num_shots, syndrome_length)`. The returned array has
    /// shape `(num_shots, self.num_fault_ids())`.
    ///
    /// ```
    /// use ndarray::array;
    /// use pymatching::{EdgeData, Matching};
    ///
    /// let mut matching = Matching::default();
    /// matching.add_boundary_edge(0, EdgeData::new(vec![0]))?;
    /// let predictions = matching.decode_batch(array![[0_u8], [1]].view())?;
    /// assert_eq!(predictions, array![[0_u8], [1]]);
    /// # Ok::<(), pymatching::MatchingError>(())
    /// ```
    pub fn decode_batch(&self, shots: ArrayView2<'_, u8>) -> Result<Array2<u8>> {
        Ok(self
            .decode_batch_with_options(shots, DecodeOptions::new())?
            .predictions)
    }

    /// Decodes a batch with optional packing, weights, and correlations.
    ///
    /// Unpacked shots are shaped `(num_shots, syndrome_length)`. Packed shots
    /// use little-endian bits within each byte and normally have width
    /// `ceil(self.num_detectors() / 8)`. Unpacked predictions are shaped
    /// `(num_shots, self.num_fault_ids())`; packed predictions have width
    /// `ceil(self.num_fault_ids() / 8)`.
    ///
    /// Native correlated matching is selected by
    /// [`DecodeOptions::with_enable_correlations`]. The matching must also have
    /// been built with correlations enabled.
    ///
    /// ```
    /// use ndarray::array;
    /// use pymatching::{DecodeOptions, Matching};
    ///
    /// let dem: stim::DetectorErrorModel = "\
    ///     error(0.1) D0 L0\n\
    ///     error(0.1) D0 D1\n\
    ///     error(0.2) D1\n".parse()?;
    /// let matching = Matching::from_detector_error_model_with_options(&dem, true)?;
    /// let result = matching.decode_batch_with_options(
    ///     array![[0_u8, 0], [1, 0]].view(),
    ///     DecodeOptions::new().with_enable_correlations(true),
    /// )?;
    /// assert_eq!(result.predictions.dim(), (2, 1));
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn decode_batch_with_options(
        &self,
        shots: ArrayView2<'_, u8>,
        options: DecodeOptions,
    ) -> Result<BatchDecodeResult> {
        let num_rows = shots.nrows();
        let raw = with_contiguous_2d(shots, |shots, rows, cols| {
            self.decode_batch_with_options_raw(shots, rows, cols, options)
        })?;
        if raw.prediction_rows as usize != num_rows {
            return Err(MatchingError::Upstream(
                "bridge returned an invalid batch prediction row count".to_string(),
            ));
        }
        let predictions =
            array2_from_u8(raw.predictions, raw.prediction_rows, raw.prediction_cols)?;
        let expected_cols = if options.bit_packed_predictions {
            required_packed_bytes(self.num_fault_ids())
        } else {
            self.num_fault_ids()
        };
        if predictions.ncols() != expected_cols {
            return Err(MatchingError::Upstream(
                "bridge returned an invalid batch prediction width".to_string(),
            ));
        }
        if raw.has_weights && raw.weights.len() != num_rows {
            return Err(MatchingError::Upstream(
                "bridge returned an invalid batch weight count".to_string(),
            ));
        }

        let weights = raw.has_weights.then(|| Array1::from_vec(raw.weights));
        Ok(BatchDecodeResult {
            predictions,
            weights,
        })
    }

    /// Decodes a batch and always returns one matching weight per shot.
    ///
    /// This is a convenience wrapper over [`Matching::decode_batch_with_options`]
    /// that enables `return_weight` while preserving the other options.
    pub fn decode_batch_with_weights(
        &self,
        shots: ArrayView2<'_, u8>,
        options: DecodeOptions,
    ) -> Result<(Array2<u8>, Array1<f64>)> {
        let result = self.decode_batch_with_options(shots, options.with_return_weight(true))?;
        let weights = result.weights.ok_or(MatchingError::Upstream(
            "bridge did not return batch weights".to_string(),
        ))?;
        Ok((result.predictions, weights))
    }

    /// Returns every graph edge in a raw matching correction.
    ///
    /// The result has shape `(num_selected_edges, 2)`. Each row contains two
    /// detector indices; the second value is `-1` for an edge to any boundary.
    pub fn decode_to_edges_array(&self, syndrome: ArrayView1<'_, u8>) -> Result<Array2<i64>> {
        self.decode_to_edges_array_with_options(syndrome, DecodeOptions::new())
    }

    /// Returns every correction edge with optional native correlations.
    ///
    /// Only [`DecodeOptions::with_enable_correlations`] affects this method.
    /// See [`Matching::decode_to_edges_array`] for the output format.
    pub fn decode_to_edges_array_with_options(
        &self,
        syndrome: ArrayView1<'_, u8>,
        options: DecodeOptions,
    ) -> Result<Array2<i64>> {
        let raw = with_contiguous_1d(syndrome, |syndrome| {
            self.decode_to_edges_array_raw(syndrome, options.enable_correlations)
        })?;
        array2_from_i64(raw.data, raw.rows, raw.cols)
    }

    /// Returns the detection-event pairs selected by raw matching.
    ///
    /// Each row is a pair of active detectors, or `(detector, -1)` when an
    /// event is matched to a boundary. Unlike edge-array decoding, this reports
    /// matched event endpoints rather than every edge along their shortest
    /// paths. Negative graph weights are not supported by this method.
    pub fn decode_to_matched_dets_array(
        &self,
        syndrome: ArrayView1<'_, u8>,
    ) -> Result<Array2<i64>> {
        let raw = with_contiguous_1d(syndrome, |syndrome| {
            self.decode_to_matched_dets_array_raw(syndrome)
        })?;
        array2_from_i64(raw.data, raw.rows, raw.cols)
    }

    /// Returns detection-event matches as a map.
    ///
    /// Both members of a detector pair are keys mapped to each other. A
    /// detector matched to a boundary maps to `None`.
    pub fn decode_to_matched_dets_dict(
        &self,
        syndrome: ArrayView1<'_, u8>,
    ) -> Result<MatchedDetectors> {
        let pairs = self.decode_to_matched_dets_array(syndrome)?;
        let mut matched = MatchedDetectors::with_capacity(pairs.nrows() * 2);
        for pair in pairs.outer_iter() {
            let detector = pair[0] as usize;
            let mate = pair[1];
            if mate == -1 {
                matched.insert(detector, None);
            } else if mate >= 0 {
                let mate = mate as usize;
                matched.insert(detector, Some(mate));
                matched.insert(mate, Some(detector));
            } else {
                return Err(MatchingError::Upstream(
                    "bridge returned an invalid matched-detector index".to_string(),
                ));
            }
        }
        Ok(matched)
    }

    /// Samples independent edge noise using each edge's error probability.
    ///
    /// Returns `None` unless every edge has an `error_probability`. A supplied
    /// seed makes the sample reproducible. Explicit boundary-node syndrome bits
    /// are always zero.
    pub fn add_noise(&self, seed: Option<u64>) -> Result<Option<NoiseSample>> {
        let raw = self.add_noise_raw(seed)?;
        if !raw.has_noise {
            return Ok(None);
        }

        Ok(Some(NoiseSample {
            errors: Array1::from_vec(raw.errors),
            syndrome: Array1::from_vec(raw.syndrome),
        }))
    }
}

fn with_contiguous_1d<T>(
    array: ArrayView1<'_, u8>,
    operation: impl FnOnce(&[u8]) -> Result<T>,
) -> Result<T> {
    if let Some(slice) = array.as_slice() {
        operation(slice)
    } else {
        operation(&array.iter().copied().collect::<Vec<_>>())
    }
}

fn with_contiguous_2d<T>(
    array: ArrayView2<'_, u8>,
    operation: impl FnOnce(&[u8], usize, usize) -> Result<T>,
) -> Result<T> {
    let rows = array.nrows();
    let cols = array.ncols();
    if let Some(slice) = array.as_slice() {
        operation(slice, rows, cols)
    } else {
        operation(&array.iter().copied().collect::<Vec<_>>(), rows, cols)
    }
}

fn array2_from_u8(data: Vec<u8>, rows: u64, cols: u64) -> Result<Array2<u8>> {
    Array2::from_shape_vec((rows as usize, cols as usize), data).map_err(|_| {
        MatchingError::Upstream("bridge returned an invalid u8 matrix shape".to_string())
    })
}

fn array2_from_i64(data: Vec<i64>, rows: u64, cols: u64) -> Result<Array2<i64>> {
    Array2::from_shape_vec((rows as usize, cols as usize), data).map_err(|_| {
        MatchingError::Upstream("bridge returned an invalid i64 matrix shape".to_string())
    })
}

fn array2_from_f64(data: Vec<f64>, rows: u64, cols: u64) -> Result<Array2<f64>> {
    Array2::from_shape_vec((rows as usize, cols as usize), data).map_err(|_| {
        MatchingError::Upstream("bridge returned an invalid f64 matrix shape".to_string())
    })
}