跳转至

ForwardMatch

QuICT.qcda.optimization.template_optimization.template_matching.ForwardMatch

Class for forward matching.

execute classmethod 

execute(circuit: MatchingDAGCircuit, template: MatchingDAGCircuit, c_node_id: int, t_node_id: int, qubit_mapping: List[int]) -> List[Tuple[int, int]]

Execute Forward matching.

Parameters:

  • circuit (MatchingDAGCircuit) –

    the circuit to match

  • template (MatchingDAGCircuit) –

    the template to be matched

  • c_node_id (int) –

    the starting node of circuit

  • t_node_id (int) –

    the starting node of template

  • qubit_mapping (List[int]) –

    qubit mapping (qubit i in temlate is mapped to qubit_mapping[i] is circuit)

Returns:

  • List[Tuple[int, int]] –

    List[Tuple[int, int]]: the maximal match (template node id, circuit node id)'s

Source code in QuICT/qcda/optimization/template_optimization/template_matching/forward_match.py 
 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
@classmethod
def execute(cls,
            circuit: MatchingDAGCircuit,
            template: MatchingDAGCircuit,
            c_node_id: int,
            t_node_id: int,
            qubit_mapping: List[int]) -> List[Tuple[int, int]]:
    """
    Execute Forward matching.

    Args:
        circuit (MatchingDAGCircuit): the circuit to match
        template (MatchingDAGCircuit): the template to be matched
        c_node_id (int): the starting node of `circuit`
        t_node_id (int): the starting node of `template`
        qubit_mapping (List[int]): qubit mapping
            (qubit i in `temlate` is mapped to qubit_mapping[i] is circuit)

    Returns:
        List[Tuple[int, int]]: the maximal match (template node id, circuit node id)'s
    """

    # initialize properties
    circuit.init_forward_matching(c_node_id, t_node_id, s2v_enabled=True)
    template.init_forward_matching(t_node_id, c_node_id)

    match = [(t_node_id, c_node_id)]
    match_nodes = [circuit.get_node(c_node_id)]
    while len(match_nodes) > 0:
        # every time match the first element of successors_to_visit of one node
        cur_node: MatchingDAGNode = match_nodes[0]
        match_nodes.pop(0)

        nxt_node_id = cur_node.pop_successors_to_visit()
        if nxt_node_id is None:
            continue
        nxt_node = circuit.get_node(nxt_node_id)

        if cur_node.successors_to_visit:
            cls._insert_match_nodes(match_nodes, cur_node)

        if not nxt_node.matchable():
            continue

        cands: List[MatchingDAGNode] = cls._find_candidates(match, template, cur_node.matched_with)
        success = False
        for t_nxt_node in cands:
            if t_nxt_node.compare_with(nxt_node, qubit_mapping):
                t_nxt_node.matched_with = nxt_node.id
                nxt_node.matched_with = t_nxt_node.id
                match.append((t_nxt_node.id, nxt_node.id))

                # calc nxt_node.successors_to_visit
                nxt_node.successors_to_visit = sorted(list(filter(
                    lambda x: circuit.get_node(x).matchable,
                    nxt_node.successors
                )))
                # match_nodes.append(nxt_node)
                cls._insert_match_nodes(match_nodes, nxt_node)

                success = True
                break

        if not success:
            # if not succeeded, block the node and all its successors
            nxt_node.is_blocked = True
            for node_id in circuit.all_successors(nxt_node.id):
                succ_node = circuit.get_node(node_id)

                succ_node.is_blocked = True
                # remove matched info
                if succ_node.matched_with:
                    t = succ_node.matched_with
                    template.get_node(t).matched_with = None
                    succ_node.matched_with = None
                    match.remove((t, succ_node.id))

    return match