跳转至

TemplateMatching

QuICT.qcda.optimization.template_optimization.template_matching.TemplateMatching

References

[1] Exact and practical pattern matching for quantum circuit optimization. https://arxiv.org/abs/1909.05270

execute classmethod 

execute(circuit: MatchingDAGCircuit, template: MatchingDAGCircuit, qubit_fixing_param: List[int] = None, prune_param: List[int] = None) -> List[Match]

Execute the template matching algorithm. It match circuit with template and return all maximal matches start from every qubit as a list.

Heuristic qubit parameters qubit_fixing_param is in the form [cnt] where cnt is the number of additional qubits explored when enumerating the qubit mapping (recommended value is 1).

Heuristic backward match parameter prune_param is in the form [D, W]. Backward match will prune the search tree when depth=k*D (k = 1, 2, ...) and at most W maximal matching scenarios will survive (recommended value is [3, 1]).

Above two heuristic algorithms will be executed only when the corresponding parameter is specified.

Parameters:

  • circuit (MatchingDAGCircuit) –

    the circuit to match

  • template (MatchingDAGCircuit) –

    the template to be matched

  • qubit_fixing_param (List[int], default: None ) –

    Heuristic qubit parameters

  • prune_param (List[int], default: None ) –

    Heuristic backward match parameter

Returns:

  • List[Match] –

    List[Match]: List of matches

Source code in QuICT/qcda/optimization/template_optimization/template_matching/template_matching.py 
 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
@classmethod
def execute(cls,
            circuit: MatchingDAGCircuit,
            template: MatchingDAGCircuit,
            qubit_fixing_param: List[int] = None,
            prune_param: List[int] = None
            ) -> List[Match]:
    """
    Execute the template matching algorithm. It match `circuit` with `template` and return
    all maximal matches start from every qubit as a list.

    Heuristic qubit parameters `qubit_fixing_param` is in the form [cnt] where `cnt` is
    the number of additional qubits explored when enumerating the qubit mapping (recommended
    value is 1).

    Heuristic backward match parameter `prune_param` is in the form [D, W]. Backward match
    will prune the search tree when depth=k*D (k = 1, 2, ...) and at most W maximal matching
    scenarios will survive (recommended value is [3, 1]).

    Above two heuristic algorithms will be executed only when the corresponding parameter is
    specified.

    Args:
        circuit (MatchingDAGCircuit): the circuit to match
        template (MatchingDAGCircuit): the template to be matched
        qubit_fixing_param (List[int]): Heuristic qubit parameters
        prune_param (List[int]): Heuristic backward match parameter

    Returns:
        List[Match]: List of matches
    """

    match_set = set()

    # enumerate the starting node of template
    for t_node_id in range(template.size):
        # enumerate the starting node of circuit
        for c_node_id in range(circuit.size):
            t_node = template.get_node(t_node_id)
            c_node = circuit.get_node(c_node_id)
            if not t_node.compare_with(c_node):
                continue

            # heuristically fixed qubits
            fixed_q = cls._qubit_fixing(circuit, template, c_node_id, t_node_id, *qubit_fixing_param) \
                if qubit_fixing_param else []

            # enumerate free qubits
            all_free_q = set(range(circuit.width)) - set(fixed_q)
            for free_q in itertools.combinations(all_free_q, template.width - len(fixed_q)):
                q_set = list(free_q) + fixed_q
                # enumerate permutation
                for mapping in itertools.permutations(q_set, template.width):
                    if not t_node.compare_with(c_node, mapping):
                        continue

                    forward_match = ForwardMatch.execute(
                        circuit, template, c_node_id, t_node_id, list(mapping))

                    match_list = BackwardMatch.execute(
                        circuit, template, forward_match, c_node_id, t_node_id, list(mapping), prune_param)
                    match_set.update(match_list)

    return list(match_set)