mwpm.py 文件源码

def MinWeightMatching(code, Syndrome, type, charge_type):
    dim = code.dimension

    # Fully connect check operators
    for check1 in Syndrome.nodes():
        for check2 in Syndrome.nodes():
            if check1 != check2:
                # weight = - code.distance(type, check1, check2)
                weight = - common.euclidean_dist(check1, check2)
                Syndrome.add_edge(*(check1, check2), weight=weight)

    # Generate Boundary Graph
    External_Graph = nx.Graph()

    for node in Syndrome.nodes():
        charge = Syndrome.node[node]['charge']
        external_node = AssociatedExternal(node, code.Dual[type], code.External[type])
        External_Graph.add_node(external_node, charge=(-charge) % dim)
        # weight = -code.distance(type, node, external_node)
        weight = - common.euclidean_dist(node, external_node)
        Syndrome.add_edge(*(node, external_node), weight=weight)

    # Ensure even number of elements in Syndrome
    # so min weight matching can proceed successfully
    if len(Syndrome.nodes()) % 2 != 0:
        removed_external = External_Graph.nodes()[0]
        edge = Syndrome.edges(removed_external)[0]
        min_weight = Syndrome.get_edge_data(*edge)['weight']
        for external_node in External_Graph.nodes():
            edge = Syndrome.edges(external_node)[0]
            weight = Syndrome.get_edge_data(*edge)['weight']
            if weight < min_weight:
                removed_external = external_node
                min_weight = weight

        External_Graph.remove_node(removed_external)
        Syndrome.remove_node(removed_external)

    # Connect External Nodes
    for ext1 in External_Graph:
        for ext2 in External_Graph:
            if ext1 != ext2:
                Syndrome.add_edge(*(ext1, ext2), weight=0)

    TempMatching = nx.max_weight_matching(Syndrome, maxcardinality=True)

    Matching = {}
    # each edge appears twice in TempMatching
    # Should only appear once in Matching
    for node, neighbor in TempMatching.items():
        if neighbor not in Matching:
            if node in code.Dual[type].nodes() or neighbor in code.Dual[type].nodes():
                Matching[node] = neighbor

    return Matching


# Recovery Operations
# Generate recovery chains to correct for errors during code cycle.