Source code for pennylane.transforms.optimization.pattern_matching
# Copyright 2021-2022 Xanadu Quantum Technologies Inc.# Licensed under the Apache License, Version 2.0 (the "License");# you may not use this file except in compliance with the License.# You may obtain a copy of the License at# http://www.apache.org/licenses/LICENSE-2.0# Unless required by applicable law or agreed to in writing, software# distributed under the License is distributed on an "AS IS" BASIS,# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.# See the License for the specific language governing permissions and# limitations under the License."""Transform finding all maximal matches of a pattern in a quantum circuit and optimizing the circuit bysubstitution."""importcopyimportitertoolsfromcollectionsimportOrderedDictimportnumpyasnpimportpennylaneasqmlfrompennylaneimportadjointfrompennylane.ops.qubit.attributesimportsymmetric_over_all_wiresfrompennylane.tapeimportQuantumScript,QuantumScriptBatchfrompennylane.transformsimporttransformfrompennylane.transforms.commutation_dagimportcommutation_dagfrompennylane.typingimportPostprocessingFnfrompennylane.wiresimportWires# pylint: disable=too-many-statements
[docs]@transformdefpattern_matching_optimization(tape:QuantumScript,pattern_tapes,custom_quantum_cost=None)->tuple[QuantumScriptBatch,PostprocessingFn]:r"""Quantum function transform to optimize a circuit given a list of patterns (templates). Args: tape (QNode or QuantumTape or Callable): A quantum circuit to be optimized. pattern_tapes(list(.QuantumTape)): List of quantum tapes that implement the identity. custom_quantum_cost (dict): Optional, quantum cost that overrides the default cost dictionary. Returns: qnode (QNode) or quantum function (Callable) or tuple[List[QuantumTape], function]: The transformed circuit as described in :func:`qml.transform <pennylane.transform>`. Raises: QuantumFunctionError: The pattern provided is not a valid QuantumTape or the pattern contains measurements or the pattern does not implement identity or the circuit has less qubits than the pattern. **Example** >>> dev = qml.device('default.qubit', wires=5) You can apply the transform directly on a :class:`QNode`. For that, you need first to define a pattern that is to be found in the circuit. We use the following pattern that implements the identity: .. code-block:: python ops = [qml.S(0), qml.S(0), qml.Z(0)] pattern = qml.tape.QuantumTape(ops) Let's consider the following circuit where we want to replace a sequence of two ``pennylane.S`` gates with a ``pennylane.PauliZ`` gate. .. code-block:: python @partial(pattern_matching_optimization, pattern_tapes = [pattern]) @qml.qnode(device=dev) def circuit(): qml.S(wires=0) qml.Z(0) qml.S(wires=1) qml.CZ(wires=[0, 1]) qml.S(wires=1) qml.S(wires=2) qml.CZ(wires=[1, 2]) qml.S(wires=2) return qml.expval(qml.X(0)) During the call of the circuit, it is first optimized (if possible) and then executed. >>> circuit() .. details:: :title: Usage Details .. code-block:: python def circuit(): qml.S(wires=0) qml.Z(0) qml.S(wires=1) qml.CZ(wires=[0, 1]) qml.S(wires=1) qml.S(wires=2) qml.CZ(wires=[1, 2]) qml.S(wires=2) return qml.expval(qml.X(0)) For optimizing the circuit given the following template of CNOTs we apply the ``pattern_matching`` transform. >>> qnode = qml.QNode(circuit, dev) >>> optimized_qfunc = pattern_matching_optimization(pattern_tapes=[pattern])(circuit) >>> optimized_qnode = qml.QNode(optimized_qfunc, dev) >>> print(qml.draw(qnode)()) 0: ──S──Z─╭●──────────┤ <X> 1: ──S────╰Z──S─╭●────┤ 2: ──S──────────╰Z──S─┤ >>> print(qml.draw(optimized_qnode)()) 0: ──S†─╭●────┤ <X> 1: ──Z──╰Z─╭●─┤ 2: ──Z─────╰Z─┤ Note that with this pattern we also replace a ``pennylane.S``, ``pennylane.PauliZ`` sequence by ``Adjoint(S)``. If one would like avoiding this, it possible to give a custom quantum cost dictionary with a negative cost for ``pennylane.PauliZ``. >>> my_cost = {"PauliZ": -1 , "S": 1, "Adjoint(S)": 1} >>> optimized_qfunc = pattern_matching_optimization(circuit, pattern_tapes=[pattern], custom_quantum_cost=my_cost) >>> optimized_qnode = qml.QNode(optimized_qfunc, dev) >>> print(qml.draw(optimized_qnode)()) 0: ──S──Z─╭●────┤ <X> 1: ──Z────╰Z─╭●─┤ 2: ──Z───────╰Z─┤ Now we can consider a more complicated example with the following quantum circuit to be optimized .. code-block:: python def circuit(): qml.Toffoli(wires=[3, 4, 0]) qml.CNOT(wires=[1, 4]) qml.CNOT(wires=[2, 1]) qml.Hadamard(wires=3) qml.Z(1) qml.CNOT(wires=[2, 3]) qml.Toffoli(wires=[2, 3, 0]) qml.CNOT(wires=[1, 4]) return qml.expval(qml.X(0)) We define a pattern that implement the identity: .. code-block:: python ops = [ qml.CNOT(wires=[1, 2]), qml.CNOT(wires=[0, 1]), qml.CNOT(wires=[1, 2]), qml.CNOT(wires=[0, 1]), qml.CNOT(wires=[0, 2]), ] tape = qml.tape.QuantumTape(ops) For optimizing the circuit given the following pattern of CNOTs we apply the ``pattern_matching`` transform. >>> dev = qml.device('default.qubit', wires=5) >>> qnode = qml.QNode(circuit, dev) >>> optimized_qfunc = pattern_matching_optimization(circuit, pattern_tapes=[pattern]) >>> optimized_qnode = qml.QNode(optimized_qfunc, dev) In our case, it is possible to find three CNOTs and replace this pattern with only two CNOTs and therefore optimizing the circuit. The number of CNOTs in the circuit is reduced by one. >>> qml.specs(qnode)()["resources"].gate_types["CNOT"] 4 >>> qml.specs(optimized_qnode)()["resources"].gate_types["CNOT"] 3 >>> print(qml.draw(qnode)()) 0: ─╭X──────────╭X────┤ <X> 1: ─│──╭●─╭X──Z─│──╭●─┤ 2: ─│──│──╰●─╭●─├●─│──┤ 3: ─├●─│───H─╰X─╰●─│──┤ 4: ─╰●─╰X──────────╰X─┤ >>> print(qml.draw(optimized_qnode)()) 0: ─╭X──────────╭X─┤ <X> 1: ─│─────╭X──Z─│──┤ 2: ─│──╭●─╰●─╭●─├●─┤ 3: ─├●─│───H─╰X─╰●─┤ 4: ─╰●─╰X──────────┤ .. seealso:: :func:`~.pattern_matching` **References** [1] Iten, R., Moyard, R., Metger, T., Sutter, D. and Woerner, S., 2022. Exact and practical pattern matching for quantum circuit optimization. `doi.org/10.1145/3498325 <https://dl.acm.org/doi/abs/10.1145/3498325>`_ """# pylint: disable=too-many-branchesconsecutive_wires=Wires(range(len(tape.wires)))inverse_wires_map=OrderedDict(zip(consecutive_wires,tape.wires))original_tape_meas=tape.measurementsforpatterninpattern_tapes:# Check the validity of the patternifnotisinstance(pattern,QuantumScript):raiseqml.QuantumFunctionError("The pattern is not a valid quantum tape.")# Check that it does not contain a measurement.ifpattern.measurements:raiseqml.QuantumFunctionError("The pattern contains measurements.")# Verify that the pattern is implementing the identityifnotnp.allclose(qml.matrix(pattern,wire_order=pattern.wires),np.eye(2**pattern.num_wires)):raiseqml.QuantumFunctionError("Pattern is not valid, it does not implement identity.")# Verify that the pattern has less qubits or same number of qubitsiftape.num_wires<pattern.num_wires:raiseqml.QuantumFunctionError("Circuit has less qubits than the pattern.")# Construct Dag representation of the circuit and the pattern.circuit_dag=commutation_dag(tape)pattern_dag=commutation_dag(pattern)max_matches=pattern_matching(circuit_dag,pattern_dag)# Optimizes the circuit for compatible maximal matchesifmax_matches:# Initialize the optimization by substitution of the different matchessubstitution=TemplateSubstitution(max_matches,circuit_dag,pattern_dag,custom_quantum_cost)substitution.substitution()already_sub=[]# If some substitutions are possible, we create an optimized circuit.ifsubstitution.substitution_list:# Create a tape that does not affect the outside context.withqml.queuing.AnnotatedQueue()asq_inside:# Loop over all possible substitutionsforgroupinsubstitution.substitution_list:circuit_sub=group.circuit_configtemplate_inverse=group.template_configpred=group.pred_block# Choose the first configurationqubit=group.qubit_config[0]# First add all the predecessors of the given match.foreleminpred:node=circuit_dag.get_node(elem)# pylint: disable=no-memberinst=copy.deepcopy(node.op)qml.apply(inst)already_sub.append(elem)already_sub=already_sub+circuit_sub# Then add the inverse of the template.forindexintemplate_inverse:all_qubits=tape.wires.tolist()all_qubits.sort()wires_t=group.template_dag.get_node(index).wireswires_c=[qubit[x]forxinwires_t]wires=[all_qubits[x]forxinwires_c]node=group.template_dag.get_node(index)inst=copy.deepcopy(node.op)inst=qml.map_wires(inst,wire_map=dict(zip(inst.wires,wires)))adjoint(qml.apply,lazy=False)(inst)# Add the unmatched gates.fornode_idinsubstitution.unmatched_list:node=circuit_dag.get_node(node_id)# pylint: disable=no-memberinst=copy.deepcopy(node.op)qml.apply(inst)qscript=QuantumScript.from_queue(q_inside)[tape],_=qml.map_wires(input=qscript,wire_map=inverse_wires_map)new_tape=tape.copy(measurements=original_tape_meas)defnull_postprocessing(results):"""A postprocesing function returned by a transform that only converts the batch of results into a result for a single ``QuantumTape``. """returnresults[0]return[new_tape],null_postprocessing
[docs]defpattern_matching(circuit_dag,pattern_dag):r"""Function that applies the pattern matching algorithm and returns the list of maximal matches. Args: circuit_dag (.CommutationDAG): A commutation DAG representing the circuit to be optimized. pattern_dag(.CommutationDAG): A commutation DAG representing the pattern. Returns: list(Match): the list of maximal matches. **Example** First let's consider the following circuit .. code-block:: python def circuit(): qml.S(wires=0) qml.Z(0) qml.S(wires=1) qml.CZ(wires=[0, 1]) qml.S(wires=1) qml.S(wires=2) qml.CZ(wires=[1, 2]) qml.S(wires=2) return qml.expval(qml.X(0)) Assume that we want to find all maximal matches of a pattern containing a sequence of two :class:`~.S` gates and a :class:`~.PauliZ` gate: .. code-block:: python def pattern(): qml.S(wires=0) qml.S(wires=0) qml.Z(0) >>> circuit_dag = qml.commutation_dag(circuit)() >>> pattern_dag = qml.commutation_dag(pattern)() >>> all_max_matches = qml.pattern_matching(circuit_dag, pattern_dag) The matches are accessible by looping through the list outputted by ``qml.pattern_matching``. This output is a list of lists containing indices. Each list represents a match between a gate in the pattern with a gate in the circuit. The first indices represent the gates in the pattern and the second indices provide indices for the gates in the circuit (by order of appearance). >>> for match_conf in all_max_matches: ... print(match_conf.match) [[0, 0], [2, 1]] [[0, 2], [1, 4]] [[0, 4], [1, 2]] [[0, 5], [1, 7]] [[0, 7], [1, 5]] The first match of this list corresponds to match the first gate (:class:`~.S`) in the pattern with the first gate in the circuit and also the third gate in the pattern (:class:`~.PauliZ`) with the second circuit gate. .. seealso:: :func:`~.pattern_matching_optimization` **Reference:** [1] Iten, R., Moyard, R., Metger, T., Sutter, D. and Woerner, S., 2022. Exact and practical pattern matching for quantum circuit optimization. `doi.org/10.1145/3498325 <https://dl.acm.org/doi/abs/10.1145/3498325>`_ """# Match listmatch_list=[]# Loop through all possible initial matchesfornode_c,node_pinitertools.product(circuit_dag.get_nodes(),pattern_dag.get_nodes()):# Initial matches between two identical gates (No qubits comparison)if_compare_operation_without_qubits(node_c[1],node_p[1]):# Fix qubits from the first (target fixed and control restrained)not_fixed_qubits_confs=_not_fixed_qubits(circuit_dag.num_wires,node_c[1].wires,pattern_dag.num_wires-len(node_p[1].wires))# Loop over all possible qubits configurations given the first match constrainsfornot_fixed_qubits_confinnot_fixed_qubits_confs:fornot_fixed_qubits_conf_permutedinitertools.permutations(not_fixed_qubits_conf):forfirst_match_qubits_confin_first_match_qubits(node_c[1],node_p[1],pattern_dag.num_wires):# Qubits mapping between circuit and patternqubits_conf=_merge_first_match_and_permutation(first_match_qubits_conf,not_fixed_qubits_conf_permuted)# Update wires, target_wires, control_wireswires,target_wires,control_wires=_update_qubits(circuit_dag,qubits_conf)# Forward match part of the algorithmforward=ForwardMatch(circuit_dag,pattern_dag,node_c[0],node_p[0],wires,target_wires,control_wires,)forward.run_forward_match()# Backward match part of the algorithmbackward=BackwardMatch(circuit_dag,pattern_dag,qubits_conf,forward.match,forward.circuit_matched_with,forward.circuit_blocked,forward.pattern_matched_with,node_c[0],node_p[0],wires,control_wires,target_wires,)backward.run_backward_match()_add_match(match_list,backward.match_final)match_list.sort(key=lambdax:len(x.match),reverse=True)# Extract maximal matches and optimizes the circuit for compatible maximal matchesifmatch_list:maximal=MaximalMatches(match_list)maximal.run_maximal_matches()max_matches=maximal.max_match_listreturnmax_matchesreturnmatch_list
def_compare_operation_without_qubits(node_1,node_2):"""Compare two operations without taking the qubits into account. Args: node_1 (.CommutationDAGNode): First operation. node_2 (.CommutationDAGNode): Second operation. Return: Bool: True if similar operation (no qubits comparison) and False otherwise. """return(node_1.op.name==node_2.op.name)and(node_1.op.data==node_2.op.data)def_not_fixed_qubits(n_qubits_circuit,exclude,length):""" Function that returns all possible combinations of qubits given some restrictions and using itertools. Args: n_qubits_circuit (int): Number of qubit in the circuit. exclude (list): list of qubits from the first matched circuit operation that needs to be excluded. length (int): length of the list to be returned (number of qubits in pattern - number of qubits from the first matched operation). Yield: iterator: Iterator of the possible lists. """circuit_range=range(0,n_qubits_circuit)forsublistinitertools.combinations([eforeincircuit_rangeifenotinexclude],length):yieldlist(sublist)def_first_match_qubits(node_c,node_p,n_qubits_p):""" Returns the list of qubits for circuit given the first match, the unknown qubit are replaced by -1. Args: node_c (.CommutationDAGNode): First matched node in the circuit. node_p (.CommutationDAGNode): First matched node in the pattern. n_qubits_p (int): number of qubit in the pattern. Returns: list: list of qubits to consider in circuit (with specific order). """# pylint: disable=too-many-branchescontrol_base={"CNOT":"PauliX","CZ":"PauliZ","CCZ":"PauliZ","CY":"PauliY","CH":"Hadamard","CSWAP":"SWAP","Toffoli":"PauliX","ControlledPhaseShift":"PhaseShift","CRX":"RX","CRY":"RY","CRZ":"RZ","CRot":"Rot","MultiControlledX":"PauliX","ControlledOperation":"ControlledOperation",}first_match_qubits=[]# Controlled gateiflen(node_c.op.control_wires)>=1:circuit_control=node_c.op.control_wirescircuit_target=Wires([wforwinnode_c.op.wiresifwnotinnode_c.op.control_wires])# Not symmetric target gate or acting on 1 wire (target wires cannot be permuted) (For example Toffoli)ifcontrol_base[node_p.op.name]notinsymmetric_over_all_wires:# Permute controlforcontrol_permutedinitertools.permutations(circuit_control):control_permuted=list(control_permuted)first_match_qubits_sub=[-1]*n_qubits_pforqinnode_p.wires:node_circuit_perm=control_permuted+circuit_targetfirst_match_qubits_sub[q]=node_circuit_perm[node_p.wires.index(q)]first_match_qubits.append(first_match_qubits_sub)# Symmetric target gate (target wires can be permuted) (For example CSWAP)else:forcontrol_permutedinitertools.permutations(circuit_control):control_permuted=list(control_permuted)fortarget_permutedinitertools.permutations(circuit_target):target_permuted=list(target_permuted)first_match_qubits_sub=[-1]*n_qubits_pforqinnode_p.wires:node_circuit_perm=control_permuted+target_permutedfirst_match_qubits_sub[q]=node_circuit_perm[node_p.wires.index(q)]first_match_qubits.append(first_match_qubits_sub)# Not controlledelse:# Not symmetric gate (target wires cannot be permuted)ifnode_p.op.namenotinsymmetric_over_all_wires:first_match_qubits_sub=[-1]*n_qubits_pforqinnode_p.wires:first_match_qubits_sub[q]=node_c.wires[node_p.wires.index(q)]first_match_qubits.append(first_match_qubits_sub)# Symmetric target gate (target wires cannot be permuted)else:forperm_qinitertools.permutations(node_c.wires):first_match_qubits_sub=[-1]*n_qubits_pforqinnode_p.wires:first_match_qubits_sub[q]=perm_q[node_p.wires.index(q)]first_match_qubits.append(first_match_qubits_sub)returnfirst_match_qubitsdef_merge_first_match_and_permutation(list_first_match,permutation):""" Function that returns the final qubits configuration given the first match constraints and the permutation of qubits not in the first match. Args: list_first_match (list): list of qubits indices for the first match. permutation (list): possible permutation for the circuit qubits not in the first match. Returns: list: list of circuit qubits for the given permutation and constraints from the initial match. """list_circuit=[]counter=0foreleminlist_first_match:ifelem==-1:list_circuit.append(permutation[counter])counter=counter+1else:list_circuit.append(elem)returnlist_circuitdef_update_qubits(circuit_dag,qubits_conf):""" Update the qubits, target qubits and the control qubits given the mapping configuration between the circuit and the pattern. Args: circuit_dag (.CommutationDAG): the DAG representation of the circuit. qubits_conf (list): list of qubits of the mapping configuration. Return: list(list(int)): Wires list(list(int)): Target wires list(list(int)): Control wires """# pylint: disable=too-many-argumentswires=[]control_wires=[]target_wires=[]fori,nodeinenumerate(circuit_dag.get_nodes()):# Wireswires.append([])forqinnode[1].wires:ifqinqubits_conf:wires[i].append(qubits_conf.index(q))iflen(node[1].wires)!=len(wires[i]):wires[i]=[]# Control wirescontrol_wires.append([])forqinnode[1].control_wires:ifqinqubits_conf:control_wires[i].append(qubits_conf.index(q))iflen(node[1].control_wires)!=len(control_wires[i]):control_wires[i]=[]# Target wirestarget_wires.append([])forqinnode[1].target_wires:ifqinqubits_conf:target_wires[i].append(qubits_conf.index(q))iflen(node[1].target_wires)!=len(target_wires[i]):target_wires[i]=[]returnwires,target_wires,control_wiresdef_add_match(match_list,backward_match_list):""" Add a match configuration found by pattern matching if it is not already in final list of matches. If the match is already in the final list, the qubit configuration is added to the existing Match. Args: match_list (list): match from the backward part of the algorithm. backward_match_list (list): List of matches found by the algorithm for a given configuration. """already_in=Falseforb_matchinbackward_match_list:forl_matchinmatch_list:ifb_match.match==l_match.match:index=match_list.index(l_match)match_list[index].qubit.append(b_match.qubit[0])already_in=Trueifnotalready_in:match_list.append(b_match)def_compare_qubits(node1,wires1,control1,target1,wires2,control2,target2):"""Compare the qubit configurations of two operations. The operations are supposed to be similar up to their qubits configuration. Args: node1 (.CommutationDAGNode): First node. wires1 (list(int)): Wires of the first node. control1 (list(int)): Control wires of the first node. target1 (list(int)): Target wires of the first node. wires2 (list(int)): Wires of the second node. control2 (list(int)): Control wires of the second node. target2 (list(int)): Target wires of the second node. """# pylint: disable=too-many-instance-attributes, too-many-argumentscontrol_base={"CNOT":"PauliX","CZ":"PauliZ","CY":"PauliY","CSWAP":"SWAP","Toffoli":"PauliX","ControlledPhaseShift":"PhaseShift","CRX":"RX","CRY":"RY","CRZ":"RZ","CRot":"Rot","MultiControlledX":"PauliX","ControlledOperation":"ControlledOperation",}ifcontrol1andset(control1)==set(control2):ifcontrol_base[node1.op.name]insymmetric_over_all_wiresandset(target1)==set(target2):returnTrueiftarget1==target2:returnTrueelse:ifnode1.op.nameinsymmetric_over_all_wiresandset(wires1)==set(wires2):returnTrueifwires1==wires2:returnTruereturnFalseclassForwardMatch:# pylint: disable=too-many-instance-attributes,too-few-public-methods""" Class to apply pattern matching in the forward direction. """def__init__(self,circuit_dag,pattern_dag,node_id_c,node_id_p,wires,control_wires,target_wires):""" Create the ForwardMatch class. Args: circuit_dag (.CommutationDAG): circuit as commutation DAG. pattern_dag (.CommutationDAG): pattern as commutation DAG. node_id_c (int): index of the first gate matched in the circuit. node_id_p (int): index of the first gate matched in the pattern. """# pylint: disable=too-many-branches, too-many-arguments# Commutation DAG of the circuitself.circuit_dag=circuit_dag# Commutation DAG of the patternself.pattern_dag=pattern_dag# Node ID in the circuitself.node_id_c=node_id_c# Node ID in the patternself.node_id_p=node_id_p# List of mapped wires for each nodeself.wires=wires# List of mapped control wires for each nodeself.control_wires=control_wires# List of mapped target wires for each nodeself.target_wires=target_wires# Successors to visitself.successors_to_visit=[None]*circuit_dag.size# Blocked nodes in the circuitself.circuit_blocked=[None]*circuit_dag.size# Matched nodes circuitself.circuit_matched_with=[None]*circuit_dag.size# Matched nodes patternself.pattern_matched_with=[None]*pattern_dag.size# Updated qubits for each nodeself.updated_qubits=[]# List of matchself.match=[]# List of candidates for the forward matchself.candidates=[]# List of nodes in circuit which are matchedself.matched_nodes_list=[]def_init_successors_to_visit(self):""" Initialize the list of successors to visit. """foriinrange(0,self.circuit_dag.size):ifi==self.node_id_c:self.successors_to_visit[i]=self.circuit_dag.direct_successors(i)else:self.successors_to_visit[i]=[]def_init_matched_with_circuit(self):""" Initialize the list of corresponding matches in the pattern for the circuit. """foriinrange(0,self.circuit_dag.size):ifi==self.node_id_c:self.circuit_matched_with[i]=[self.node_id_p]else:self.circuit_matched_with[i]=[]def_init_matched_with_pattern(self):""" Initialize the list of corresponding matches in the circuit for the pattern. """foriinrange(0,self.pattern_dag.size):ifi==self.node_id_p:self.pattern_matched_with[i]=[self.node_id_c]else:self.pattern_matched_with[i]=[]def_init_is_blocked_circuit(self):""" Initialize the list of blocked nodes in the circuit. """foriinrange(0,self.circuit_dag.size):self.circuit_blocked[i]=Falsedef_init_list_match(self):""" Initialize the list of matched nodes between the circuit and the pattern with the first match found. """self.match.append([self.node_id_p,self.node_id_c])def_find_forward_candidates(self,node_id_p):"""Find the candidate nodes to be matched in the pattern for a given node in the pattern. Args: node_id_p (int): Node ID in pattern. """matches=[i[0]foriinself.match]pred=matches.copy()iflen(pred)>1:pred.sort()pred.remove(node_id_p)ifself.pattern_dag.direct_successors(node_id_p):maximal_index=self.pattern_dag.direct_successors(node_id_p)[-1]foreleminpred:ifelem>maximal_index:pred.remove(elem)block=[]fornode_idinpred:fordir_succinself.pattern_dag.direct_successors(node_id):ifdir_succnotinmatches:succ=self.pattern_dag.successors(dir_succ)block=block+succself.candidates=list(set(self.pattern_dag.direct_successors(node_id_p))-set(matches)-set(block))def_init_matched_nodes(self):""" Initialize the list of current matched nodes. """self.matched_nodes_list.append([self.node_id_c,self.circuit_dag.get_node(self.node_id_c),self.successors_to_visit[self.node_id_c],])def_get_node_forward(self,list_id):""" Return node and successors from the matched_nodes_list for a given ID. Args: list_id (int): considered list id of the desired node. Returns: CommutationDAGNode: Node from the matched_node_list. list(int): List of successors. """node=self.matched_nodes_list[list_id][1]succ=self.matched_nodes_list[list_id][2]returnnode,succdef_remove_node_forward(self,list_id):"""Remove a node of the current matched_nodes_list for a given ID. Args: list_id (int): considered list id of the desired node. """self.matched_nodes_list.pop(list_id)defrun_forward_match(self):"""Apply the forward match algorithm and returns the list of matches given an initial match and a qubits configuration. """# pylint: disable=too-many-branches,too-many-nested-blocks# Initializationself._init_successors_to_visit()self._init_matched_with_circuit()self._init_matched_with_pattern()self._init_is_blocked_circuit()# Initialize the list of matches and the stack of matched nodes (circuit)self._init_list_match()self._init_matched_nodes()# While the list of matched nodes is not emptywhileself.matched_nodes_list:# Return first element of the matched_nodes_list and removes it from the listv_first,successors_to_visit=self._get_node_forward(0)self._remove_node_forward(0)# If there is no successors to visit go to the endifnotsuccessors_to_visit:continue# Get the label and the node of the first successor to visitlabel=successors_to_visit[0]v=[label,self.circuit_dag.get_node(label)]# Update of the successors to visit.successors_to_visit.pop(0)# Update the matched_nodes_list with new attribute successor to visit and sort the list.self.matched_nodes_list.append([v_first.node_id,v_first,successors_to_visit])self.matched_nodes_list.sort(key=lambdax:x[2])# If the node is blocked and already matched go to the endifself.circuit_blocked[v[0]]|(self.circuit_matched_with[v[0]]!=[]):continue# Search for potential candidates in the patternself._find_forward_candidates(self.circuit_matched_with[v_first.node_id][0])match=False# For loop over the candidates from the pattern to find a match.foriinself.candidates:# Break the for loop if a match is found.ifmatch:breaknode_circuit=self.circuit_dag.get_node(label)node_pattern=self.pattern_dag.get_node(i)# Necessary but not sufficient conditions for a match to happen.if(len(self.wires[label])!=len(node_pattern.wires)orset(self.wires[label])!=set(node_pattern.wires)ornode_circuit.op.name!=node_pattern.op.name):continue# Compare two operationsif_compare_operation_without_qubits(node_circuit,node_pattern):if_compare_qubits(node_circuit,self.wires[label],self.target_wires[label],self.control_wires[label],node_pattern.wires,node_pattern.control_wires,node_pattern.target_wires,):# A match happensself.circuit_matched_with[label]=[i]self.pattern_matched_with[i]=[label]# Append the new match to the list of matches.self.match.append([i,label])# Potential successors to visit (circuit) for a given match.potential=self.circuit_dag.direct_successors(label)# If the potential successors to visit are blocked or match, it is removed.forpotential_idinpotential:ifself.circuit_blocked[potential_id]|(self.circuit_matched_with[potential_id]!=[]):potential.remove(potential_id)sorted_potential=sorted(potential)# Update the successor to visit attributesuccessorstovisit=sorted_potential# Add the updated node to the stack.self.matched_nodes_list.append([v[0],v[1],successorstovisit])self.matched_nodes_list.sort(key=lambdax:x[2])match=Truecontinue# If no match is found, block the node and all the successors.ifnotmatch:self.circuit_blocked[label]=Trueforsuccinv[1].successors:self.circuit_blocked[succ]=TrueclassMatch:# pylint: disable=too-few-public-methods""" Object to represent a match and its qubits configurations. """def__init__(self,match,qubit):"""Create a Match class with necessary arguments. Args: match (list): list of matched gates. qubit (list): list of qubits configuration. """# Match listself.match=match# Qubits list for circuitifany(isinstance(el,list)forelinqubit):self.qubit=qubitelse:self.qubit=[qubit]classMatchingScenarios:# pylint: disable=too-few-public-methods""" Class to represent a matching scenario in the Backward part of the algorithm. """def__init__(self,circuit_matched,circuit_blocked,pattern_matched,pattern_blocked,matches,counter):"""Create a MatchingScenarios class for the Backward match. Args: circuit_matched (list): list representing the matched gates in the circuit. circuit_blocked (list): list representing the blocked gates in the circuit. pattern_matched (list): list representing the matched gates in the pattern. pattern_blocked (list): list representing the blocked gates in the pattern. matches (list): list of matches. counter (int): counter of the number of circuit gates already considered. """# pylint: disable=too-many-argumentsself.circuit_matched=circuit_matchedself.pattern_matched=pattern_matchedself.circuit_blocked=circuit_blockedself.pattern_blocked=pattern_blockedself.matches=matchesself.counter=counterclassMatchingScenariosList:""" Object to define a list of MatchingScenarios, with method to append and pop elements. """def__init__(self):""" Create an empty MatchingScenariosList. """self.matching_scenarios_list=[]defappend_scenario(self,matching):""" Append a scenario to the list. Args: matching (MatchingScenarios): a scenario of match. """self.matching_scenarios_list.append(matching)defpop_scenario(self):""" Pop the first scenario of the list. Returns: MatchingScenarios: a scenario of match. """# Pop the first MatchingScenario and returns itfirst=self.matching_scenarios_list[0]self.matching_scenarios_list.pop(0)returnfirstclassBackwardMatch:# pylint: disable=too-many-instance-attributes, too-few-public-methods""" Class BackwardMatch allows to run backward direction part of the pattern matching algorithm. """def__init__(self,circuit_dag,pattern_dag,qubits_conf,forward_matches,circuit_matched,circuit_blocked,pattern_matched,node_id_c,node_id_p,wires,control_wires,target_wires,):""" Create a ForwardMatch class with necessary arguments. Args: circuit_dag (DAGDependency): circuit in the dag dependency form. pattern_dag (DAGDependency): pattern in the dag dependency form. forward_matches (list): list of match obtained in the forward direction. node_id_c (int): index of the first gate matched in the circuit. node_id_p (int): index of the first gate matched in the pattern. wires (list): control_wires (list): target_wires (list): """# pylint: disable=too-many-argumentsself.circuit_dag=circuit_dagself.pattern_dag=pattern_dagself.circuit_matched=circuit_matchedself.circuit_blocked=circuit_blockedself.pattern_matched=pattern_matchedself.qubits_conf=qubits_confself.wires=wiresself.control_wires=control_wiresself.target_wires=target_wiresself.node_id_c=node_id_cself.node_id_p=node_id_pself.forward_matches=forward_matchesself.match_final=[]self.matching_list=MatchingScenariosList()def_find_backward_candidates(self,pattern_blocked,matches):"""Function which returns the list possible backward candidates in the pattern dag. Args: pattern_blocked (list(bool)): list of blocked nodes in the pattern circuit. matches (list(int)): list of matches. Returns: list(int): list of backward candidates ID. """pattern_block=[]fornode_idinrange(self.node_id_p,self.pattern_dag.size):ifpattern_blocked[node_id]:pattern_block.append(node_id)matches_pattern=sorted(match[0]formatchinmatches)successors=self.pattern_dag.get_node(self.node_id_p).successorspotential=[]forindexinrange(self.node_id_p+1,self.pattern_dag.size):if(indexnotinsuccessors)and(indexnotinpattern_block):potential.append(index)candidates_indices=list(set(potential)-set(matches_pattern))candidates_indices=sorted(candidates_indices)candidates_indices.reverse()returncandidates_indicesdefrun_backward_match(self):"""Run the backward match algorithm and returns the list of matches given an initial match, a forward scenario and a circuit qubits configuration. """# pylint: disable=too-many-branches,too-many-statements,too-many-nested-blocksmatch_store_list=[]counter=1# Initialize the blocked pattern listpattern_blocked=[False]*self.pattern_dag.size# First Scenario is stored in the MatchingScenariosList().first_match=MatchingScenarios(self.circuit_matched,self.circuit_blocked,self.pattern_matched,pattern_blocked,self.forward_matches,counter,)self.matching_list=MatchingScenariosList()self.matching_list.append_scenario(first_match)# Set the circuit indices that can be matched.gate_indices=_gate_indices(self.circuit_matched,self.circuit_blocked)number_of_gate_to_match=(self.pattern_dag.size-(self.node_id_p-1)-len(self.forward_matches))# While the scenario stack is not empty.whileself.matching_list.matching_scenarios_list:scenario=self.matching_list.pop_scenario()circuit_matched=scenario.circuit_matchedcircuit_blocked=scenario.circuit_blockedpattern_matched=scenario.pattern_matchedpattern_blocked=scenario.pattern_blockedmatches_scenario=scenario.matchescounter_scenario=scenario.counter# Part of the match list coming from the backward match.match_backward=[matchformatchinmatches_scenarioifmatchnotinself.forward_matches]# Matches are storedif(counter_scenario>len(gate_indices)orlen(match_backward)==number_of_gate_to_match):matches_scenario.sort(key=lambdax:x[0])match_store_list.append(Match(matches_scenario,self.qubits_conf))continue# First circuit candidate.circuit_id=gate_indices[counter_scenario-1]node_circuit=self.circuit_dag.get_node(circuit_id)# If the circuit candidate is blocked, only the counter is changed.ifcircuit_blocked[circuit_id]:matching_scenario=MatchingScenarios(circuit_matched,circuit_blocked,pattern_matched,pattern_blocked,matches_scenario,counter_scenario+1,)self.matching_list.append_scenario(matching_scenario)continue# The backward candidates in the pattern.candidates_indices=self._find_backward_candidates(pattern_blocked,matches_scenario)# Get the different wires variableswires1=self.wires[circuit_id]control_wires1=self.control_wires[circuit_id]target_wires1=self.target_wires[circuit_id]global_match=Falseglobal_broken=[]# Loop over the pattern candidates.forpattern_idincandidates_indices:node_pattern=self.pattern_dag.get_node(pattern_id)wires2=self.pattern_dag.get_node(pattern_id).wirescontrol_wires2=self.pattern_dag.get_node(pattern_id).control_wirestarget_wires2=self.pattern_dag.get_node(pattern_id).target_wires# Necessary but not sufficient conditions for a match to happen.if(len(wires1)!=len(wires2)orset(wires1)!=set(wires2)ornode_circuit.op.name!=node_pattern.op.name):continue# Compare two operationsif_compare_operation_without_qubits(node_circuit,node_pattern):if_compare_qubits(node_circuit,wires1,control_wires1,target_wires1,wires2,control_wires2,target_wires2,):# A match happens.# If there is a match the attributes are copied.circuit_matched_match=circuit_matched.copy()circuit_blocked_match=circuit_blocked.copy()pattern_matched_match=pattern_matched.copy()pattern_blocked_match=pattern_blocked.copy()matches_scenario_match=matches_scenario.copy()block_list=[]broken_matches_match=[]# Loop to check if the match is not connected, in this case# the successors matches are blocked and unmatched.forpotential_blockinself.pattern_dag.successors(pattern_id):ifnotpattern_matched_match[potential_block]:pattern_blocked_match[potential_block]=Trueblock_list.append(potential_block)forblock_idinblock_list:forsucc_idinself.pattern_dag.successors(block_id):pattern_blocked_match[succ_id]=Trueifpattern_matched_match[succ_id]:new_id=pattern_matched_match[succ_id][0]circuit_matched_match[new_id]=[]pattern_matched_match[succ_id]=[]broken_matches_match.append(succ_id)ifbroken_matches_match:global_broken.append(True)else:global_broken.append(False)new_matches_scenario_match=[elemforeleminmatches_scenario_matchifelem[0]notinbroken_matches_match]condition=Trueforback_matchinmatch_backward:ifback_matchnotinnew_matches_scenario_match:# pragma: no covercondition=Falsebreak# First option greedy match.if([self.node_id_p,self.node_id_c]innew_matches_scenario_match)and(conditionornotmatch_backward):pattern_matched_match[pattern_id]=[circuit_id]circuit_matched_match[circuit_id]=[pattern_id]new_matches_scenario_match.append([pattern_id,circuit_id])new_matching_scenario=MatchingScenarios(circuit_matched_match,circuit_blocked_match,pattern_matched_match,pattern_blocked_match,new_matches_scenario_match,counter_scenario+1,)self.matching_list.append_scenario(new_matching_scenario)global_match=Trueifglobal_match:circuit_matched_block_s=circuit_matched.copy()circuit_blocked_block_s=circuit_blocked.copy()pattern_matched_block_s=pattern_matched.copy()pattern_blocked_block_s=pattern_blocked.copy()matches_scenario_block_s=matches_scenario.copy()circuit_blocked_block_s[circuit_id]=Truebroken_matches=[]# Second option, not a greedy match, block all successors (push the gate# to the right).forsuccinself.circuit_dag.get_node(circuit_id).successors:circuit_blocked_block_s[succ]=Trueifcircuit_matched_block_s[succ]:broken_matches.append(succ)new_id=circuit_matched_block_s[succ][0]pattern_matched_block_s[new_id]=[]circuit_matched_block_s[succ]=[]new_matches_scenario_block_s=[elemforeleminmatches_scenario_block_sifelem[1]notinbroken_matches]condition_not_greedy=Trueforback_matchinmatch_backward:ifback_matchnotinnew_matches_scenario_block_s:condition_not_greedy=Falsebreakif([self.node_id_p,self.node_id_c]innew_matches_scenario_block_s)and(condition_not_greedyornotmatch_backward):new_matching_scenario=MatchingScenarios(circuit_matched_block_s,circuit_blocked_block_s,pattern_matched_block_s,pattern_blocked_block_s,new_matches_scenario_block_s,counter_scenario+1,)self.matching_list.append_scenario(new_matching_scenario)# Third option: if blocking the succesors breaks a match, we consider# also the possibility to block all predecessors (push the gate to the left).ifbroken_matchesandall(global_broken):circuit_matched_block_p=circuit_matched.copy()circuit_blocked_block_p=circuit_blocked.copy()pattern_matched_block_p=pattern_matched.copy()pattern_blocked_block_p=pattern_blocked.copy()matches_scenario_block_p=matches_scenario.copy()circuit_blocked_block_p[circuit_id]=Trueforpredinself.circuit_dag.get_node(circuit_id).predecessors:circuit_blocked_block_p[pred]=Truematching_scenario=MatchingScenarios(circuit_matched_block_p,circuit_blocked_block_p,pattern_matched_block_p,pattern_blocked_block_p,matches_scenario_block_p,counter_scenario+1,)self.matching_list.append_scenario(matching_scenario)# If there is no match then there are three options.ifnotglobal_match:circuit_blocked[circuit_id]=Truefollowing_matches=[]successors=self.circuit_dag.get_node(circuit_id).successorsforsuccinsuccessors:ifcircuit_matched[succ]:following_matches.append(succ)# First option, the circuit gate is not disturbing because there are no# following match and no predecessors.predecessors=self.circuit_dag.get_node(circuit_id).predecessorsifnotpredecessorsornotfollowing_matches:matching_scenario=MatchingScenarios(circuit_matched,circuit_blocked,pattern_matched,pattern_blocked,matches_scenario,counter_scenario+1,)self.matching_list.append_scenario(matching_scenario)else:circuit_matched_nomatch=circuit_matched.copy()circuit_blocked_nomatch=circuit_blocked.copy()pattern_matched_nomatch=pattern_matched.copy()pattern_blocked_nomatch=pattern_blocked.copy()matches_scenario_nomatch=matches_scenario.copy()# Second option, all predecessors are blocked (circuit gate is# moved to the left).forpredinpredecessors:circuit_blocked[pred]=Truematching_scenario=MatchingScenarios(circuit_matched,circuit_blocked,pattern_matched,pattern_blocked,matches_scenario,counter_scenario+1,)self.matching_list.append_scenario(matching_scenario)# Third option, all successors are blocked (circuit gate is# moved to the right).broken_matches=[]successors=self.circuit_dag.get_node(circuit_id).successorsforsuccinsuccessors:circuit_blocked_nomatch[succ]=Trueifcircuit_matched_nomatch[succ]:broken_matches.append(succ)circuit_matched_nomatch[succ]=[]new_matches_scenario_nomatch=[elemforeleminmatches_scenario_nomatchifelem[1]notinbroken_matches]condition_block=Trueforback_matchinmatch_backward:ifback_matchnotinnew_matches_scenario_nomatch:condition_block=Falsebreakif([self.node_id_p,self.node_id_c]inmatches_scenario_nomatch)and(condition_blockornotmatch_backward):new_matching_scenario=MatchingScenarios(circuit_matched_nomatch,circuit_blocked_nomatch,pattern_matched_nomatch,pattern_blocked_nomatch,new_matches_scenario_nomatch,counter_scenario+1,)self.matching_list.append_scenario(new_matching_scenario)length=max(len(m.match)forminmatch_store_list)# Store the matches with maximal length.forscenarioinmatch_store_list:if(len(scenario.match)==length)andnotany(scenario.match==x.matchforxinself.match_final):self.match_final.append(scenario)def_gate_indices(circuit_matched,circuit_blocked):"""Function which returns the list of gates that are not matched and not blocked for the first scenario. Returns: list(int): list of gate id. """gate_indices=[]fori,(matched,blocked)inenumerate(zip(circuit_matched,circuit_blocked)):if(notmatched)and(notblocked):gate_indices.append(i)gate_indices.reverse()returngate_indicesclassMaximalMatches:# pylint: disable=too-few-public-methods""" Class MaximalMatches allows to sort and store the maximal matches from the list of matches obtained with the pattern matching algorithm. """def__init__(self,pattern_matches):"""Initialize MaximalMatches with the necessary arguments. Args: pattern_matches (list): list of matches obtained from running the algorithm. """self.pattern_matches=pattern_matchesself.max_match_list=[]defrun_maximal_matches(self):"""Method that extracts and stores maximal matches in decreasing length order."""self.max_match_list=[Match(sorted(self.pattern_matches[0].match),self.pattern_matches[0].qubit,)]formatchesinself.pattern_matches[1::]:present=Falseformax_matchinself.max_match_list:foreleminmatches.match:ifeleminmax_match.matchandlen(matches.match)<=len(max_match.match):present=Trueifnotpresent:self.max_match_list.append(Match(sorted(matches.match),matches.qubit))classSubstitutionConfig:# pylint: disable=too-many-arguments, too-few-public-methods"""Class to store the configuration of a given match substitution, which circuit gates, template gates, qubits and predecessors of the match in the circuit. """def__init__(self,circuit_config,template_config,pred_block,qubit_config,template_dag,):self.template_dag=template_dagself.circuit_config=circuit_configself.template_config=template_configself.qubit_config=qubit_configself.pred_block=pred_blockclassTemplateSubstitution:# pylint: disable=too-few-public-methods"""Class to run the substitution algorithm from the list of maximal matches."""def__init__(self,max_matches,circuit_dag,template_dag,custom_quantum_cost=None):""" Initialize TemplateSubstitution with necessary arguments. Args: max_matches (list(int)): list of maximal matches obtained from the running the pattern matching algorithm. circuit_dag (.CommutationDAG): circuit in the dag dependency form. template_dag (.CommutationDAG): template in the dag dependency form. custom_quantum_cost (dict): Optional, quantum cost that overrides the default cost dictionnary. """self.match_stack=max_matchesself.circuit_dag=circuit_dagself.template_dag=template_dagself.substitution_list=[]self.unmatched_list=[]ifcustom_quantum_costisnotNone:self.quantum_cost=dict(custom_quantum_cost)else:self.quantum_cost={"Identity":0,"PauliX":1,"PauliY":1,"PauliZ":1,"RX":1,"RY":1,"RZ":1,"Hadamard":1,"T":1,"Adjoint(T)":1,"S":1,"Adjoint(S)":1,"CNOT":2,"CZ":4,"SWAP":6,"CSWAP":63,"Toffoli":21,}def_pred_block(self,circuit_sublist,index):"""It returns the predecessors of a given part of the circuit. Args: circuit_sublist (list): list of the gates matched in the circuit. index (int): Index of the group of matches. Returns: list: List of predecessors of the current match circuit configuration. """predecessors=set()fornode_idincircuit_sublist:predecessors=predecessors|set(self.circuit_dag.get_node(node_id).predecessors)exclude=set()foreleminself.substitution_list[:index]:exclude=exclude|set(elem.circuit_config)|set(elem.pred_block)pred=list(predecessors-set(circuit_sublist)-exclude)pred.sort()returnpreddef_quantum_cost(self,left,right):"""Compare the two parts of the template and returns True if the quantum cost is reduced. Args: left (list): list of matched nodes in the template. right (list): list of nodes to be replaced. Returns: bool: True if the quantum cost is reduced """cost_left=0foriinleft:cost_left+=self.quantum_cost[self.template_dag.get_node(i).op.name]cost_right=0forjinright:cost_right+=self.quantum_cost[self.template_dag.get_node(j).op.name]returncost_left>cost_rightdef_rules(self,circuit_sublist,template_sublist,template_complement):"""Set of rules to decide whether the match is to be substitute or not. Args: circuit_sublist (list): list of the gates matched in the circuit. template_sublist (list): list of matched nodes in the template. template_complement (list): list of gates not matched in the template. Returns: bool: True if the match respects the given rule for replacement, False otherwise. """ifself._quantum_cost(template_sublist,template_complement):forelemincircuit_sublist:forconfiginself.substitution_list:ifany(elem==xforxinconfig.circuit_config):returnFalsereturnTruereturnFalsedef_template_inverse(self,template_list,template_sublist,template_complement):"""The template circuit realizes the identity operator, then given the list of matches in the template, it returns the inverse part of the template that will be replaced. Args: template_list (list): list of all gates in the template. template_sublist (list): list of the gates matched in the circuit. template_complement (list): list of gates not matched in the template. Returns: list(int): the template inverse part that will substitute the circuit match. """inverse=template_complementleft=[]right=[]pred=set()forindexintemplate_sublist:pred=pred|set(self.template_dag.get_node(index).predecessors)pred=list(pred-set(template_sublist))succ=set()forindexintemplate_sublist:succ=succ|set(self.template_dag.get_node(index).successors)succ=list(succ-set(template_sublist))comm=list(set(template_list)-set(pred)-set(succ))forelemininverse:ifeleminpred:left.append(elem)elifeleminsucc:right.append(elem)elifelemincomm:right.append(elem)left.sort()right.sort()left.reverse()right.reverse()total=left+rightreturntotaldef_substitution_sort(self):"""Sort the substitution list."""ordered=Falsewhilenotordered:ordered=self._permutation()def_permutation(self):# pragma: no cover"""Permute two groups of matches if first one has predecessors in the second one. Returns: bool: True if the matches groups are in the right order, False otherwise. """forscenarioinself.substitution_list:predecessors=set()formatchinscenario.circuit_config:predecessors=predecessors|set(self.circuit_dag.get_node(match).predecessors)predecessors=predecessors-set(scenario.circuit_config)index=self.substitution_list.index(scenario)forscenario_binself.substitution_list[index::]:ifset(scenario_b.circuit_config)&predecessors:index1=self.substitution_list.index(scenario)index2=self.substitution_list.index(scenario_b)scenario_pop=self.substitution_list.pop(index2)self.substitution_list.insert(index1,scenario_pop)returnFalsereturnTruedef_remove_impossible(self):# pragma: no cover"""Remove matched groups if they both have predecessors in the other one, they are not compatible."""list_predecessors=[]remove_list=[]# Initialize predecessors for each group of matches.forscenarioinself.substitution_list:predecessors=set()forindexinscenario.circuit_config:predecessors=predecessors|set(self.circuit_dag.get_node(index).predecessors)list_predecessors.append(predecessors)# Check if two groups of matches are incompatible.forscenario_ainself.substitution_list:ifscenario_ainremove_list:continueindex_a=self.substitution_list.index(scenario_a)circuit_a=scenario_a.circuit_configforscenario_binself.substitution_list[index_a+1::]:ifscenario_binremove_list:continueindex_b=self.substitution_list.index(scenario_b)circuit_b=scenario_b.circuit_configif(set(circuit_a)&list_predecessors[index_b])and(set(circuit_b)&list_predecessors[index_a]):remove_list.append(scenario_b)# Remove the incompatible groups from the list.ifremove_list:self.substitution_list=[scenarioforscenarioinself.substitution_listifscenarionotinremove_list]defsubstitution(self):"""From the list of maximal matches, it chooses which one will be used and gives the necessary details for each substitution(template inverse, predecessors of the match). """whileself.match_stack:# Get the first match scenario of the listcurrent=self.match_stack.pop(0)current_match=current.matchcurrent_qubit=current.qubittemplate_sublist=[x[0]forxincurrent_match]circuit_sublist=[x[1]forxincurrent_match]circuit_sublist.sort()template_list=range(0,self.template_dag.size)template_complement=list(set(template_list)-set(template_sublist))# If the match obey the rule then it is added to the list.ifself._rules(circuit_sublist,template_sublist,template_complement):template_sublist_inverse=self._template_inverse(template_list,template_sublist,template_complement)config=SubstitutionConfig(circuit_sublist,template_sublist_inverse,[],current_qubit,self.template_dag,)self.substitution_list.append(config)# Remove incompatible matches.self._remove_impossible()# First sort the matches according to the smallest index in the matches (circuit).self.substitution_list.sort(key=lambdax:x.circuit_config[0])# Change position of the groups due to predecessors of other groups.self._substitution_sort()forscenarioinself.substitution_list:index=self.substitution_list.index(scenario)scenario.pred_block=self._pred_block(scenario.circuit_config,index)circuit_list=[]foreleminself.substitution_list:circuit_list=circuit_list+elem.circuit_config+elem.pred_block# Unmatched gates that are not predecessors of any group of matches.self.unmatched_list=sorted(list(set(range(0,self.circuit_dag.size))-set(circuit_list)))