pymatching 0.1.0

Safe Rust bindings for the PyMatching quantum error-correction decoder
Documentation
use ndarray::ArrayView2;

use crate::types::{CheckMatrixOptions, EdgeData, MergeStrategy, StoredBinaryMatrix};
use crate::{Matching, MatchingError, Result};

impl Matching {
    /// Constructs a matching graph from a binary check matrix.
    ///
    /// Each column must contain at most two ones. Two ones at rows `i` and `j`
    /// create an edge `(i, j)`; one creates a boundary edge; an empty column
    /// creates no edge. Unless a faults matrix is supplied, column `j` carries
    /// fault id `j`.
    ///
    /// ```
    /// use ndarray::array;
    /// use pymatching::{CheckMatrixOptions, Matching};
    ///
    /// let check_matrix = array![[1_u8, 1, 0], [0, 1, 1]];
    /// let matching = Matching::from_check_matrix(
    ///     check_matrix.view(),
    ///     CheckMatrixOptions::new().with_virtual_boundary_node(true),
    /// )?;
    /// assert_eq!(matching.num_detectors(), 2);
    /// assert_eq!(matching.num_edges(), 3);
    /// # Ok::<(), pymatching::MatchingError>(())
    /// ```
    ///
    /// # Errors
    ///
    /// Returns an error if either matrix is nonbinary, a column has more than
    /// two ones, option-vector dimensions do not match, a probability is
    /// invalid, or `repetitions` is zero.
    pub fn from_check_matrix(
        check_matrix: ArrayView2<'_, u8>,
        options: CheckMatrixOptions,
    ) -> Result<Self> {
        let mut matching = Self::default();
        matching.load_check_matrix(check_matrix, options)?;
        Ok(matching)
    }

    /// Replaces this decoder with a graph built from a binary check matrix.
    ///
    /// Construction is transactional: if validation or graph construction
    /// fails, the existing matching is unchanged. See
    /// [`Matching::from_check_matrix`] for matrix semantics and errors.
    pub fn load_check_matrix(
        &mut self,
        check_matrix: ArrayView2<'_, u8>,
        options: CheckMatrixOptions,
    ) -> Result<()> {
        validate_binary_matrix("check_matrix", check_matrix)?;
        let mut column_supports = Vec::with_capacity(check_matrix.ncols());
        for col in 0..check_matrix.ncols() {
            column_supports.push(nonzero_rows(check_matrix, col)?);
        }

        self.load_check_matrix_from_column_supports(
            check_matrix.nrows(),
            check_matrix.ncols(),
            column_supports,
            options,
        )
    }

    pub(crate) fn load_check_matrix_from_column_supports(
        &mut self,
        num_rows: usize,
        num_cols: usize,
        column_supports: Vec<Vec<usize>>,
        options: CheckMatrixOptions,
    ) -> Result<()> {
        if column_supports.len() != num_cols {
            return Err(MatchingError::InvalidInput(
                "column_supports length must match the number of check-matrix columns",
            ));
        }

        let resolved = ResolvedCheckMatrixOptions::new(num_rows, num_cols, options)?;
        build_matching_from_column_supports(self, num_rows, &column_supports, &resolved)
    }
}

#[derive(Debug, Clone)]
struct ResolvedCheckMatrixOptions {
    weights: Vec<f64>,
    error_probabilities: Vec<f64>,
    fault_id_source: FaultIdSource,
    merge_strategy: MergeStrategy,
    repetitions: usize,
    timelike_weights: Option<Vec<f64>>,
    measurement_error_probabilities: Option<Vec<f64>>,
    use_virtual_boundary_node: bool,
    num_fault_ids: usize,
}

impl ResolvedCheckMatrixOptions {
    fn new(num_rows: usize, num_cols: usize, options: CheckMatrixOptions) -> Result<Self> {
        let CheckMatrixOptions {
            weights,
            error_probabilities,
            faults_matrix,
            merge_strategy,
            repetitions,
            timelike_weights,
            measurement_error_probabilities,
            use_virtual_boundary_node,
        } = options;

        if repetitions == 0 {
            return Err(MatchingError::Upstream(
                "repetitions must be at least 1".to_string(),
            ));
        }

        let explicit_error_probabilities = error_probabilities.is_some();
        let weights = resolve_values(
            weights,
            num_cols,
            1.0,
            "weights length must match the number of check-matrix columns",
        )?;
        let error_probabilities = resolve_values(
            error_probabilities,
            num_cols,
            -1.0,
            "error_probabilities length must match the number of check-matrix columns",
        )?;
        if explicit_error_probabilities {
            validate_explicit_probabilities(&error_probabilities)?;
        }

        let (fault_id_source, num_fault_ids) = match faults_matrix {
            Some(matrix) => {
                validate_stored_binary_matrix("faults_matrix", &matrix)?;
                if matrix.ncols() != num_cols {
                    return Err(MatchingError::Upstream(
                        "faults_matrix column count must match the check matrix".to_string(),
                    ));
                }
                let rows = matrix.nrows();
                (FaultIdSource::Explicit(matrix), rows)
            }
            None => (FaultIdSource::Identity, num_cols),
        };

        let timelike_weights = if repetitions > 1 {
            Some(resolve_values(
                timelike_weights,
                num_rows,
                1.0,
                "timelike_weights length must match the number of check-matrix rows",
            )?)
        } else {
            None
        };
        let explicit_measurement_error_probabilities = measurement_error_probabilities.is_some();
        let measurement_error_probabilities = if repetitions > 1 {
            let resolved = resolve_values(
                measurement_error_probabilities,
                num_rows,
                -1.0,
                "measurement_error_probabilities length must match the number of check-matrix rows",
            )?;
            if explicit_measurement_error_probabilities {
                validate_explicit_probabilities(&resolved)?;
            }
            Some(resolved)
        } else {
            None
        };

        Ok(Self {
            weights,
            error_probabilities,
            fault_id_source,
            merge_strategy,
            repetitions,
            timelike_weights,
            measurement_error_probabilities,
            use_virtual_boundary_node,
            num_fault_ids,
        })
    }

    fn fault_ids_for_column(&self, col: usize) -> Vec<usize> {
        match &self.fault_id_source {
            FaultIdSource::Identity => vec![col],
            FaultIdSource::Explicit(matrix) => {
                let mut fault_ids = Vec::new();
                for row in 0..matrix.nrows() {
                    if matrix.get(row, col) == 1 {
                        fault_ids.push(row);
                    }
                }
                fault_ids
            }
        }
    }
}

#[derive(Debug, Clone)]
enum FaultIdSource {
    Identity,
    Explicit(StoredBinaryMatrix),
}

fn build_matching_from_column_supports(
    matching: &mut Matching,
    num_rows: usize,
    column_supports: &[Vec<usize>],
    resolved: &ResolvedCheckMatrixOptions,
) -> Result<()> {
    let mut staged = Matching::default();
    staged.ensure_num_fault_ids(resolved.num_fault_ids);

    let num_detectors = num_rows * resolved.repetitions;
    let mut has_boundary_node = false;

    for rep in 0..resolved.repetitions {
        for (col, detectors) in column_supports.iter().enumerate() {
            let edge = EdgeData {
                fault_ids: resolved.fault_ids_for_column(col),
                weight: resolved.weights[col],
                error_probability: edge_error_probability(resolved.error_probabilities[col]),
            };

            match detectors.as_slice() {
                [node1, node2] => {
                    staged.insert_edge_with_strategy(
                        node1 + num_rows * rep,
                        node2 + num_rows * rep,
                        edge,
                        resolved.merge_strategy,
                    )?;
                }
                [node] => {
                    if resolved.use_virtual_boundary_node {
                        staged.insert_boundary_edge_with_strategy(
                            node + num_rows * rep,
                            edge,
                            resolved.merge_strategy,
                        )?;
                    } else {
                        has_boundary_node = true;
                        staged.insert_edge_with_strategy(
                            node + num_rows * rep,
                            num_detectors,
                            edge,
                            resolved.merge_strategy,
                        )?;
                    }
                }
                [] => {}
                _ => unreachable!("column supports validate the maximum count"),
            }
        }
    }

    if resolved.repetitions > 1 {
        let timelike_weights = resolved
            .timelike_weights
            .as_ref()
            .expect("timelike weights are always resolved for repetitions > 1");
        let measurement_error_probabilities = resolved
            .measurement_error_probabilities
            .as_ref()
            .expect("measurement error probabilities are always resolved for repetitions > 1");

        for rep in 0..(resolved.repetitions - 1) {
            for row in 0..num_rows {
                staged.insert_edge_with_strategy(
                    row + rep * num_rows,
                    row + (rep + 1) * num_rows,
                    EdgeData {
                        fault_ids: Vec::new(),
                        weight: timelike_weights[row],
                        error_probability: edge_error_probability(
                            measurement_error_probabilities[row],
                        ),
                    },
                    resolved.merge_strategy,
                )?;
            }
        }
    }

    if has_boundary_node {
        staged.set_boundary_nodes([num_detectors]);
    }

    staged.ensure_num_fault_ids(resolved.num_fault_ids);
    staged.refresh_edge_cache();
    *matching = staged;
    Ok(())
}

fn validate_binary_matrix(name: &str, matrix: ArrayView2<'_, u8>) -> Result<()> {
    if matrix.iter().all(|&value| value <= 1) {
        Ok(())
    } else {
        Err(MatchingError::Upstream(format!(
            "{name} must contain only binary values"
        )))
    }
}

fn validate_stored_binary_matrix(name: &str, matrix: &StoredBinaryMatrix) -> Result<()> {
    for row in 0..matrix.nrows() {
        for col in 0..matrix.ncols() {
            if matrix.get(row, col) > 1 {
                return Err(MatchingError::Upstream(format!(
                    "{name} must contain only binary values"
                )));
            }
        }
    }
    Ok(())
}

fn resolve_values(
    values: Option<Vec<f64>>,
    expected_len: usize,
    default_value: f64,
    length_error: &'static str,
) -> Result<Vec<f64>> {
    let resolved = values.unwrap_or_else(|| vec![default_value; expected_len]);
    if resolved.len() == expected_len {
        Ok(resolved)
    } else {
        Err(MatchingError::Upstream(length_error.to_string()))
    }
}

fn validate_explicit_probabilities(probabilities: &[f64]) -> Result<()> {
    for &probability in probabilities {
        if !(0.0..=1.0).contains(&probability) {
            return Err(MatchingError::InvalidProbability { probability });
        }
    }

    Ok(())
}

fn nonzero_rows(check_matrix: ArrayView2<'_, u8>, col: usize) -> Result<Vec<usize>> {
    let mut rows = Vec::with_capacity(2);
    for row in 0..check_matrix.nrows() {
        match check_matrix[(row, col)] {
            0 => {}
            1 => rows.push(row),
            _ => unreachable!("check_matrix is validated before reading"),
        }
    }

    if rows.len() > 2 {
        Err(MatchingError::Upstream(format!(
            "check_matrix column {col} contains more than two ones"
        )))
    } else {
        Ok(rows)
    }
}

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