qecp 0.2.7

Quantum Error Correction Playground for Surface Code Research
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

use super::cfg_if;
use super::libc;
use libc::c_int;
use std::collections::BTreeSet;

cfg_if::cfg_if! {
    if #[cfg(feature="blossom_v")] {

        #[link(name = "blossomV")]
        extern {
            fn minimum_weight_perfect_matching(node_num: c_int, edge_num: c_int, edges: *const c_int, weights: *const c_int, matched: *mut c_int);
        }

    } else {

        fn minimum_weight_perfect_matching(_node_num: c_int, _edge_num: c_int, _edges: *const c_int, _weights: *const c_int, _matched: *mut c_int) {
            unimplemented!("need blossom V library, see README.md")
        }

    }
}

pub fn safe_minimum_weight_perfect_matching_integer_weights(
    node_num: usize,
    input_weighted_edges: Vec<(usize, usize, c_int)>,
) -> Vec<usize> {
    // reverse the nodes' indices
    let weighted_edges = if cfg!(feature = "MWPM_reverse_order") {
        input_weighted_edges
            .iter()
            .map(|(a, b, cost)| (node_num - 1 - a, node_num - 1 - b, *cost))
            .collect()
    } else {
        input_weighted_edges
    };
    // normal matching
    let edge_num = weighted_edges.len();
    let mut edges = Vec::with_capacity(2 * edge_num);
    let mut weights = Vec::with_capacity(edge_num);
    debug_assert!({
        let mut existing_edges = BTreeSet::new();
        let mut sanity_check_passed = true;
        for &(i, j, _weight) in weighted_edges.iter() {
            if i == j {
                eprintln!("invalid edge between the same vertex {}", i);
                sanity_check_passed = false;
            }
            let left: usize = if i < j { i } else { j };
            let right: usize = if i < j { j } else { i };
            if existing_edges.contains(&(left, right)) {
                eprintln!("duplicate edge between the vertices {} and {}", i, j);
                sanity_check_passed = false;
            }
            existing_edges.insert((left, right));
        }
        sanity_check_passed
    });
    for &(i, j, weight) in weighted_edges.iter() {
        edges.push(i as c_int);
        edges.push(j as c_int);
        assert!(i < node_num && j < node_num);
        weights.push(weight);
    }
    let mut output = Vec::with_capacity(node_num);
    unsafe {
        minimum_weight_perfect_matching(
            node_num as c_int,
            edge_num as c_int,
            edges.as_ptr(),
            weights.as_ptr(),
            output.as_mut_ptr(),
        );
        output.set_len(node_num);
    }
    let output: Vec<usize> = output.iter().map(|x| *x as usize).collect();
    // recover the nodes' indices
    if cfg!(feature = "MWPM_reverse_order") {
        let mut result = output.iter().map(|a| node_num - 1 - a).collect::<Vec<_>>();
        result.reverse();
        result
    } else {
        output
    }
}

pub fn safe_minimum_weight_perfect_matching(node_num: usize, input_weighted_edges: Vec<(usize, usize, f64)>) -> Vec<usize> {
    // scale all edges to integer values
    let mut maximum_weight = 0.;
    for (_, _, weight) in input_weighted_edges.iter() {
        if weight > &maximum_weight {
            maximum_weight = *weight;
        }
    }
    let scale: f64 = (c_int::MAX as f64) / 10. / ((node_num + 1) as f64) / maximum_weight;
    let mut integer_weighted_edges = Vec::<(usize, usize, c_int)>::with_capacity(input_weighted_edges.len());
    for (i, j, weight) in input_weighted_edges.into_iter() {
        integer_weighted_edges.push((i, j, (weight * scale).ceil() as c_int));
    }
    safe_minimum_weight_perfect_matching_integer_weights(node_num, integer_weighted_edges)
}

// important: only takes non-positive inputs
pub fn maximum_weight_perfect_matching_compatible(
    node_num: usize,
    weighted_edges: Vec<(usize, usize, f64)>,
) -> std::collections::HashSet<(usize, usize)> {
    // blossom V is minimum weight perfect matching, this function is maximum
    let weighted_edges: Vec<(usize, usize, f64)> = weighted_edges.iter().map(|(a, b, w)| (*a, *b, -*w)).collect();
    let output = safe_minimum_weight_perfect_matching(node_num, weighted_edges);
    let mut matched = std::collections::HashSet::new();
    for (i, &value) in output.iter().enumerate().take(node_num) {
        if value > i {
            matched.insert((i, value));
        }
    }
    matched
}