pymatching 0.1.0

Safe Rust bindings for the PyMatching quantum error-correction decoder
Documentation
use ndarray::array;
use pymatching::{CheckMatrixOptions, DecodeOptions, Matching, MatchingError};
use std::str::FromStr;
use std::sync::mpsc;
use std::thread;
use std::time::{Duration, Instant};

#[test]
fn decodes_a_single_syndrome_to_fault_predictions() {
    let check_matrix = array![
        [1_u8, 1, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 1, 1]
    ];
    let matching = Matching::from_check_matrix(
        check_matrix.view(),
        CheckMatrixOptions::new().with_weights(vec![4.0, 3.0, 2.0, 3.0, 4.0]),
    )
    .unwrap();

    let prediction = matching.decode(array![0_u8, 1, 0, 1].view()).unwrap();
    assert_eq!(prediction.to_vec(), vec![0, 0, 1, 1, 0]);
}

#[test]
fn rejects_invalid_syndrome_values() {
    let check_matrix = array![[1_u8, 1, 0], [0, 1, 1]];
    let matching =
        Matching::from_check_matrix(check_matrix.view(), CheckMatrixOptions::new()).unwrap();

    let error = matching.decode(array![0_u8, 2].view()).unwrap_err();

    assert_eq!(
        error,
        MatchingError::Upstream("syndrome values must be binary".to_string())
    );
}

#[test]
fn decode_batch_returns_predictions_for_all_shots() {
    let check_matrix = array![
        [1_u8, 1, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 1, 1]
    ];
    let matching =
        Matching::from_check_matrix(check_matrix.view(), CheckMatrixOptions::new()).unwrap();
    let shots = array![[0_u8, 1, 0, 1], [1, 0, 1, 0]];

    let predictions = matching.decode_batch(shots.view()).unwrap();
    assert_eq!(predictions.dim().0, 2);
    assert_eq!(predictions.dim().1, matching.num_fault_ids());
}

#[test]
fn decode_batch_preserves_rows_from_nonstandard_layouts() {
    let check_matrix = array![
        [1_u8, 1, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 1, 1]
    ];
    let matching =
        Matching::from_check_matrix(check_matrix.view(), CheckMatrixOptions::new()).unwrap();
    let storage = array![[0_u8, 1], [1, 0], [0, 1], [1, 0]];
    let transposed_shots = storage.t();
    assert!(!transposed_shots.is_standard_layout());

    let actual = matching.decode_batch(transposed_shots).unwrap();
    let expected = matching
        .decode_batch(array![[0_u8, 1, 0, 1], [1, 0, 1, 0]].view())
        .unwrap();

    assert_eq!(actual, expected);
}

#[test]
fn correlated_decode_batch_matches_correlated_single_shots() {
    let dem = stim::DetectorErrorModel::from_str(
        "error(0.05) D0 L0 ^ D2 L1\n\
         error(0.1) D0 D1\n\
         error(0.2) D1\n\
         error(0.1) D2 D3\n\
         error(0.2) D3\n",
    )
    .unwrap();
    let matching = Matching::from_detector_error_model_with_options(&dem, true).unwrap();
    let shots = array![[0_u8, 0, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1]];
    let options = DecodeOptions::new().with_enable_correlations(true);

    let batch = matching
        .decode_batch_with_options(shots.view(), options)
        .unwrap();
    for (row_index, syndrome) in shots.outer_iter().enumerate() {
        let single = matching
            .decode_with_options(syndrome, options)
            .unwrap()
            .prediction;
        assert_eq!(batch.predictions.row(row_index), single.view());
    }
}

#[test]
fn decode_batch_with_weights_returns_weight_for_each_shot() {
    let check_matrix = array![
        [1_u8, 1, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 1, 1]
    ];
    let matching = Matching::from_check_matrix(
        check_matrix.view(),
        CheckMatrixOptions::new().with_weights(vec![4.0, 3.0, 2.0, 3.0, 4.0]),
    )
    .unwrap();
    let shots = array![[0_u8, 1, 0, 1], [1, 0, 1, 0]];

    let (predictions, weights) = matching
        .decode_batch_with_weights(shots.view(), DecodeOptions::new().with_return_weight(true))
        .unwrap();

    assert_eq!(predictions.dim(), (2, matching.num_fault_ids()));
    assert_eq!(weights.len(), 2);
    assert_eq!(weights[0], 5.0);
    assert_eq!(weights[1], 5.0);
}

#[test]
fn decode_batch_with_return_weight_options_returns_predictions_and_weights() {
    let check_matrix = array![
        [1_u8, 1, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 1, 1]
    ];
    let matching = Matching::from_check_matrix(
        check_matrix.view(),
        CheckMatrixOptions::new().with_weights(vec![4.0, 3.0, 2.0, 3.0, 4.0]),
    )
    .unwrap();
    let shots = array![[0_u8, 1, 0, 1], [1, 0, 1, 0]];

    let result = matching
        .decode_batch_with_options(shots.view(), DecodeOptions::new().with_return_weight(true))
        .unwrap();

    assert_eq!(
        result.predictions,
        array![[0_u8, 0, 1, 1, 0], [0, 1, 1, 0, 0]]
    );
    assert_eq!(result.weights.unwrap().to_vec(), vec![5.0, 5.0]);
}

#[test]
fn decode_to_edges_and_matched_detector_arrays_use_upstream_matching_state() {
    let mut matching = Matching::default();
    matching
        .add_boundary_edge(0, pymatching::EdgeData::new(vec![]))
        .unwrap();
    matching
        .add_edge(0, 1, pymatching::EdgeData::new(vec![]))
        .unwrap();
    matching
        .add_edge(1, 2, pymatching::EdgeData::new(vec![]))
        .unwrap();
    matching
        .add_edge(2, 3, pymatching::EdgeData::new(vec![]))
        .unwrap();
    matching
        .add_edge(3, 4, pymatching::EdgeData::new(vec![]))
        .unwrap();

    let edges = matching
        .decode_to_edges_array(array![1_u8, 0, 0, 1, 1].view())
        .unwrap();
    let matched = matching
        .decode_to_matched_dets_array(array![1_u8, 0, 0, 1, 1].view())
        .unwrap();

    assert_eq!(edges, array![[0_i64, -1], [3, 4]]);
    assert_eq!(matched, array![[0_i64, -1], [3, 4]]);
}

#[test]
fn decode_to_matched_dets_dict_returns_boundary_as_none() {
    let mut matching = Matching::default();
    matching
        .add_boundary_edge(0, pymatching::EdgeData::new(vec![]))
        .unwrap();
    matching
        .add_edge(0, 1, pymatching::EdgeData::new(vec![]))
        .unwrap();
    matching
        .add_edge(1, 2, pymatching::EdgeData::new(vec![]))
        .unwrap();
    matching
        .add_edge(2, 3, pymatching::EdgeData::new(vec![]))
        .unwrap();
    matching
        .add_edge(3, 4, pymatching::EdgeData::new(vec![]))
        .unwrap();

    let matched = matching
        .decode_to_matched_dets_dict(array![1_u8, 0, 0, 1, 1].view())
        .unwrap();
    assert_eq!(matched.get(&0), Some(&None));
    assert_eq!(matched.get(&3), Some(&Some(4)));
    assert_eq!(matched.get(&4), Some(&Some(3)));
}

#[test]
fn decode_with_options_returns_weighted_prediction() {
    let check_matrix = array![
        [1_u8, 1, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 1, 1]
    ];
    let matching = Matching::from_check_matrix(
        check_matrix.view(),
        CheckMatrixOptions::new().with_weights(vec![4.0, 3.0, 2.0, 3.0, 4.0]),
    )
    .unwrap();

    let result = matching
        .decode_with_options(
            array![0_u8, 1, 0, 1].view(),
            DecodeOptions::new().with_return_weight(true),
        )
        .unwrap();

    assert_eq!(result.prediction.to_vec(), vec![0, 0, 1, 1, 0]);
    assert_eq!(result.weight, Some(5.0));
}

#[test]
fn decode_batch_supports_bit_packed_shots_and_predictions() {
    let check_matrix = array![
        [1_u8, 1, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 1, 1]
    ];
    let matching =
        Matching::from_check_matrix(check_matrix.view(), CheckMatrixOptions::new()).unwrap();
    let packed_shots = array![[0b0000_1010_u8], [0b0000_0101_u8]];

    let result = matching
        .decode_batch_with_options(
            packed_shots.view(),
            DecodeOptions::new()
                .with_bit_packed_shots(true)
                .with_bit_packed_predictions(true),
        )
        .unwrap();

    assert_eq!(result.predictions.dim(), (2, 1));
    assert_eq!(result.predictions[[0, 0]] & 0b0001_1111, 0b0000_1100);
    assert_eq!(result.predictions[[1, 0]] & 0b0001_1111, 0b0000_0110);
}

#[test]
fn decode_batch_rejects_bit_packed_input_with_too_few_columns() {
    let check_matrix = array![
        [1_u8, 1, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 1, 1]
    ];
    let matching =
        Matching::from_check_matrix(check_matrix.view(), CheckMatrixOptions::new()).unwrap();
    let empty_packed_shots = ndarray::Array2::<u8>::zeros((2, 0));

    let error = matching
        .decode_batch_with_options(
            empty_packed_shots.view(),
            DecodeOptions::new().with_bit_packed_shots(true),
        )
        .unwrap_err();

    assert_eq!(
        error,
        MatchingError::Upstream(
            "bit_packed `shots` array should have at least 1 columns (ceil(num_detectors/8)) and at most 1 columns, (ceil(num_nodes/8)). Instead it has 0 columns.".to_string()
        )
    );
}

#[test]
fn decode_batch_rejects_non_binary_non_bit_packed_values() {
    let check_matrix = array![
        [1_u8, 1, 0, 0, 0],
        [0, 1, 1, 0, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 1, 1]
    ];
    let matching =
        Matching::from_check_matrix(check_matrix.view(), CheckMatrixOptions::new()).unwrap();
    let malformed_shots = array![[0_u8, 2, 0, 1], [1, 0, 1, 0]];

    let error = matching
        .decode_batch_with_options(malformed_shots.view(), DecodeOptions::new())
        .unwrap_err();

    assert_eq!(
        error,
        MatchingError::Upstream("syndrome values must be binary".to_string())
    );
}

#[test]
fn add_noise_with_seed_is_deterministic() {
    let check_matrix = array![[1_u8, 1, 0], [0, 1, 1]];
    let matching = Matching::from_check_matrix(
        check_matrix.view(),
        CheckMatrixOptions::new().with_error_probabilities(vec![0.25, 0.1, 0.2]),
    )
    .unwrap();

    let first = matching.add_noise(Some(7)).unwrap().unwrap();
    let second = matching.add_noise(Some(7)).unwrap().unwrap();

    assert_eq!(first.errors, second.errors);
    assert_eq!(first.syndrome, second.syndrome);
}

#[test]
fn seeded_noise_does_not_perturb_repeated_unseeded_sequence() {
    let check_matrix = array![[1_u8, 1, 0], [0, 1, 1]];
    let options = CheckMatrixOptions::new().with_error_probabilities(vec![0.25, 0.1, 0.2]);
    let matching = Matching::from_check_matrix(check_matrix.view(), options).unwrap();

    pymatching_cxx::set_global_rng_seed_for_tests(123);
    let baseline_unseeded = matching.add_noise(None).unwrap().unwrap();

    pymatching_cxx::set_global_rng_seed_for_tests(123);
    let seeded_first = matching.add_noise(Some(101)).unwrap().unwrap();
    let seeded_second = matching.add_noise(Some(101)).unwrap().unwrap();
    let unseeded_after_seeded = matching.add_noise(None).unwrap().unwrap();

    assert_eq!(seeded_first.errors, seeded_second.errors);
    assert_eq!(seeded_first.syndrome, seeded_second.syndrome);
    assert_eq!(baseline_unseeded.errors, unseeded_after_seeded.errors);
    assert_eq!(baseline_unseeded.syndrome, unseeded_after_seeded.syndrome);
}

#[test]
fn unseeded_noise_uses_the_shared_rng_lock() {
    let check_matrix = array![[1_u8, 1, 0], [0, 1, 1]];

    let holder = thread::spawn(|| {
        pymatching_cxx::hold_noise_rng_lock_for_tests(250);
    });

    let deadline = Instant::now() + Duration::from_secs(1);
    while !pymatching_cxx::is_noise_rng_lock_held_for_tests() && Instant::now() < deadline {
        thread::sleep(Duration::from_millis(5));
    }
    assert!(pymatching_cxx::is_noise_rng_lock_held_for_tests());

    let (tx, rx) = mpsc::channel();
    let worker_check_matrix = check_matrix;
    let worker = thread::spawn(move || {
        let matching = Matching::from_check_matrix(
            worker_check_matrix.view(),
            CheckMatrixOptions::new().with_error_probabilities(vec![0.25, 0.1, 0.2]),
        )
        .unwrap();
        let result = matching.add_noise(None);
        tx.send(result.is_ok()).unwrap();
    });

    thread::sleep(Duration::from_millis(50));
    assert!(
        rx.try_recv().is_err(),
        "unseeded add_noise unexpectedly completed while the RNG lock was held"
    );

    holder.join().unwrap();
    assert!(rx.recv().unwrap());
    worker.join().unwrap();
}