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 by
substitution."""
import copy
import itertools
from collections import OrderedDict
import numpy as np
import pennylane as qml
from pennylane import adjoint
from pennylane.ops.qubit.attributes import symmetric_over_all_wires
from pennylane.tape import QuantumScript, QuantumScriptBatch
from pennylane.transforms import transform
from pennylane.transforms.commutation_dag import commutation_dag
from pennylane.typing import PostprocessingFn
from pennylane.wires import Wires
# pylint: disable=too-many-statements
[docs]@transform
def pattern_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-branches
consecutive_wires = Wires(range(len(tape.wires)))
inverse_wires_map = OrderedDict(zip(consecutive_wires, tape.wires))
original_tape_meas = tape.measurements
for pattern in pattern_tapes:
# Check the validity of the pattern
if not isinstance(pattern, QuantumScript):
raise qml.QuantumFunctionError("The pattern is not a valid quantum tape.")
# Check that it does not contain a measurement.
if pattern.measurements:
raise qml.QuantumFunctionError("The pattern contains measurements.")
# Verify that the pattern is implementing the identity
if not np.allclose(
qml.matrix(pattern, wire_order=pattern.wires), np.eye(2**pattern.num_wires)
):
raise qml.QuantumFunctionError("Pattern is not valid, it does not implement identity.")
# Verify that the pattern has less qubits or same number of qubits
if tape.num_wires < pattern.num_wires:
raise qml.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 matches
if max_matches:
# Initialize the optimization by substitution of the different matches
substitution = TemplateSubstitution(
max_matches, circuit_dag, pattern_dag, custom_quantum_cost
)
substitution.substitution()
already_sub = []
# If some substitutions are possible, we create an optimized circuit.
if substitution.substitution_list:
# Create a tape that does not affect the outside context.
with qml.queuing.AnnotatedQueue() as q_inside:
# Loop over all possible substitutions
for group in substitution.substitution_list:
circuit_sub = group.circuit_config
template_inverse = group.template_config
pred = group.pred_block
# Choose the first configuration
qubit = group.qubit_config[0]
# First add all the predecessors of the given match.
for elem in pred:
node = circuit_dag.get_node(elem) # pylint: disable=no-member
inst = copy.deepcopy(node.op)
qml.apply(inst)
already_sub.append(elem)
already_sub = already_sub + circuit_sub
# Then add the inverse of the template.
for index in template_inverse:
all_qubits = tape.wires.tolist()
all_qubits.sort()
wires_t = group.template_dag.get_node(index).wires
wires_c = [qubit[x] for x in wires_t]
wires = [all_qubits[x] for x in wires_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.
for node_id in substitution.unmatched_list:
node = circuit_dag.get_node(node_id) # pylint: disable=no-member
inst = 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 = type(tape)(tape.operations, original_tape_meas, shots=tape.shots)
def null_postprocessing(results):
"""A postprocesing function returned by a transform that only converts the batch of results
into a result for a single ``QuantumTape``.
"""
return results[0]
return [new_tape], null_postprocessing
[docs]def pattern_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 list
match_list = []
# Loop through all possible initial matches
for node_c, node_p in itertools.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 constrains
for not_fixed_qubits_conf in not_fixed_qubits_confs:
for not_fixed_qubits_conf_permuted in itertools.permutations(not_fixed_qubits_conf):
for first_match_qubits_conf in _first_match_qubits(
node_c[1], node_p[1], pattern_dag.num_wires
):
# Qubits mapping between circuit and pattern
qubits_conf = _merge_first_match_and_permutation(
first_match_qubits_conf, not_fixed_qubits_conf_permuted
)
# Update wires, target_wires, control_wires
wires, target_wires, control_wires = _update_qubits(
circuit_dag, qubits_conf
)
# Forward match part of the algorithm
forward = 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 algorithm
backward = 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=lambda x: len(x.match), reverse=True)
# Extract maximal matches and optimizes the circuit for compatible maximal matches
if match_list:
maximal = MaximalMatches(match_list)
maximal.run_maximal_matches()
max_matches = maximal.max_match_list
return max_matches
return match_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)
for sublist in itertools.combinations([e for e in circuit_range if e not in exclude], length):
yield list(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-branches
control_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 gate
if len(node_c.op.control_wires) >= 1:
circuit_control = node_c.op.control_wires
circuit_target = Wires([w for w in node_c.op.wires if w not in node_c.op.control_wires])
# Not symmetric target gate or acting on 1 wire (target wires cannot be permuted) (For example Toffoli)
if control_base[node_p.op.name] not in symmetric_over_all_wires:
# Permute control
for control_permuted in itertools.permutations(circuit_control):
control_permuted = list(control_permuted)
first_match_qubits_sub = [-1] * n_qubits_p
for q in node_p.wires:
node_circuit_perm = control_permuted + circuit_target
first_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:
for control_permuted in itertools.permutations(circuit_control):
control_permuted = list(control_permuted)
for target_permuted in itertools.permutations(circuit_target):
target_permuted = list(target_permuted)
first_match_qubits_sub = [-1] * n_qubits_p
for q in node_p.wires:
node_circuit_perm = control_permuted + target_permuted
first_match_qubits_sub[q] = node_circuit_perm[node_p.wires.index(q)]
first_match_qubits.append(first_match_qubits_sub)
# Not controlled
else:
# Not symmetric gate (target wires cannot be permuted)
if node_p.op.name not in symmetric_over_all_wires:
first_match_qubits_sub = [-1] * n_qubits_p
for q in node_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:
for perm_q in itertools.permutations(node_c.wires):
first_match_qubits_sub = [-1] * n_qubits_p
for q in node_p.wires:
first_match_qubits_sub[q] = perm_q[node_p.wires.index(q)]
first_match_qubits.append(first_match_qubits_sub)
return first_match_qubits
def _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 = 0
for elem in list_first_match:
if elem == -1:
list_circuit.append(permutation[counter])
counter = counter + 1
else:
list_circuit.append(elem)
return list_circuit
def _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-arguments
wires = []
control_wires = []
target_wires = []
for i, node in enumerate(circuit_dag.get_nodes()):
# Wires
wires.append([])
for q in node[1].wires:
if q in qubits_conf:
wires[i].append(qubits_conf.index(q))
if len(node[1].wires) != len(wires[i]):
wires[i] = []
# Control wires
control_wires.append([])
for q in node[1].control_wires:
if q in qubits_conf:
control_wires[i].append(qubits_conf.index(q))
if len(node[1].control_wires) != len(control_wires[i]):
control_wires[i] = []
# Target wires
target_wires.append([])
for q in node[1].target_wires:
if q in qubits_conf:
target_wires[i].append(qubits_conf.index(q))
if len(node[1].target_wires) != len(target_wires[i]):
target_wires[i] = []
return wires, target_wires, control_wires
def _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 = False
for b_match in backward_match_list:
for l_match in match_list:
if b_match.match == l_match.match:
index = match_list.index(l_match)
match_list[index].qubit.append(b_match.qubit[0])
already_in = True
if not already_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-arguments
control_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",
}
if control1 and set(control1) == set(control2):
if control_base[node1.op.name] in symmetric_over_all_wires and set(target1) == set(target2):
return True
if target1 == target2:
return True
else:
if node1.op.name in symmetric_over_all_wires and set(wires1) == set(wires2):
return True
if wires1 == wires2:
return True
return False
class ForwardMatch: # 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 circuit
self.circuit_dag = circuit_dag
# Commutation DAG of the pattern
self.pattern_dag = pattern_dag
# Node ID in the circuit
self.node_id_c = node_id_c
# Node ID in the pattern
self.node_id_p = node_id_p
# List of mapped wires for each node
self.wires = wires
# List of mapped control wires for each node
self.control_wires = control_wires
# List of mapped target wires for each node
self.target_wires = target_wires
# Successors to visit
self.successors_to_visit = [None] * circuit_dag.size
# Blocked nodes in the circuit
self.circuit_blocked = [None] * circuit_dag.size
# Matched nodes circuit
self.circuit_matched_with = [None] * circuit_dag.size
# Matched nodes pattern
self.pattern_matched_with = [None] * pattern_dag.size
# Updated qubits for each node
self.updated_qubits = []
# List of match
self.match = []
# List of candidates for the forward match
self.candidates = []
# List of nodes in circuit which are matched
self.matched_nodes_list = []
def _init_successors_to_visit(self):
"""
Initialize the list of successors to visit.
"""
for i in range(0, self.circuit_dag.size):
if i == 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.
"""
for i in range(0, self.circuit_dag.size):
if i == 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.
"""
for i in range(0, self.pattern_dag.size):
if i == 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.
"""
for i in range(0, self.circuit_dag.size):
self.circuit_blocked[i] = False
def _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] for i in self.match]
pred = matches.copy()
if len(pred) > 1:
pred.sort()
pred.remove(node_id_p)
if self.pattern_dag.direct_successors(node_id_p):
maximal_index = self.pattern_dag.direct_successors(node_id_p)[-1]
for elem in pred:
if elem > maximal_index:
pred.remove(elem)
block = []
for node_id in pred:
for dir_succ in self.pattern_dag.direct_successors(node_id):
if dir_succ not in matches:
succ = self.pattern_dag.successors(dir_succ)
block = block + succ
self.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]
return node, succ
def _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)
def run_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
# Initialization
self._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 empty
while self.matched_nodes_list:
# Return first element of the matched_nodes_list and removes it from the list
v_first, successors_to_visit = self._get_node_forward(0)
self._remove_node_forward(0)
# If there is no successors to visit go to the end
if not successors_to_visit:
continue
# Get the label and the node of the first successor to visit
label = 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=lambda x: x[2])
# If the node is blocked and already matched go to the end
if self.circuit_blocked[v[0]] | (self.circuit_matched_with[v[0]] != []):
continue
# Search for potential candidates in the pattern
self._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.
for i in self.candidates:
# Break the for loop if a match is found.
if match:
break
node_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)
or set(self.wires[label]) != set(node_pattern.wires)
or node_circuit.op.name != node_pattern.op.name
):
continue
# Compare two operations
if _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 happens
self.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.
for potential_id in potential:
if self.circuit_blocked[potential_id] | (
self.circuit_matched_with[potential_id] != []
):
potential.remove(potential_id)
sorted_potential = sorted(potential)
# Update the successor to visit attribute
successorstovisit = 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=lambda x: x[2])
match = True
continue
# If no match is found, block the node and all the successors.
if not match:
self.circuit_blocked[label] = True
for succ in v[1].successors:
self.circuit_blocked[succ] = True
class Match: # 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 list
self.match = match
# Qubits list for circuit
if any(isinstance(el, list) for el in qubit):
self.qubit = qubit
else:
self.qubit = [qubit]
class MatchingScenarios: # 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-arguments
self.circuit_matched = circuit_matched
self.pattern_matched = pattern_matched
self.circuit_blocked = circuit_blocked
self.pattern_blocked = pattern_blocked
self.matches = matches
self.counter = counter
class MatchingScenariosList:
"""
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 = []
def append_scenario(self, matching):
"""
Append a scenario to the list.
Args:
matching (MatchingScenarios): a scenario of match.
"""
self.matching_scenarios_list.append(matching)
def pop_scenario(self):
"""
Pop the first scenario of the list.
Returns:
MatchingScenarios: a scenario of match.
"""
# Pop the first MatchingScenario and returns it
first = self.matching_scenarios_list[0]
self.matching_scenarios_list.pop(0)
return first
class BackwardMatch: # 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-arguments
self.circuit_dag = circuit_dag
self.pattern_dag = pattern_dag
self.circuit_matched = circuit_matched
self.circuit_blocked = circuit_blocked
self.pattern_matched = pattern_matched
self.qubits_conf = qubits_conf
self.wires = wires
self.control_wires = control_wires
self.target_wires = target_wires
self.node_id_c = node_id_c
self.node_id_p = node_id_p
self.forward_matches = forward_matches
self.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 = []
for node_id in range(self.node_id_p, self.pattern_dag.size):
if pattern_blocked[node_id]:
pattern_block.append(node_id)
matches_pattern = sorted(match[0] for match in matches)
successors = self.pattern_dag.get_node(self.node_id_p).successors
potential = []
for index in range(self.node_id_p + 1, self.pattern_dag.size):
if (index not in successors) and (index not in pattern_block):
potential.append(index)
candidates_indices = list(set(potential) - set(matches_pattern))
candidates_indices = sorted(candidates_indices)
candidates_indices.reverse()
return candidates_indices
def run_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-blocks
match_store_list = []
counter = 1
# Initialize the blocked pattern list
pattern_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.
while self.matching_list.matching_scenarios_list:
scenario = self.matching_list.pop_scenario()
circuit_matched = scenario.circuit_matched
circuit_blocked = scenario.circuit_blocked
pattern_matched = scenario.pattern_matched
pattern_blocked = scenario.pattern_blocked
matches_scenario = scenario.matches
counter_scenario = scenario.counter
# Part of the match list coming from the backward match.
match_backward = [
match for match in matches_scenario if match not in self.forward_matches
]
# Matches are stored
if (
counter_scenario > len(gate_indices)
or len(match_backward) == number_of_gate_to_match
):
matches_scenario.sort(key=lambda x: 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.
if circuit_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 variables
wires1 = self.wires[circuit_id]
control_wires1 = self.control_wires[circuit_id]
target_wires1 = self.target_wires[circuit_id]
global_match = False
global_broken = []
# Loop over the pattern candidates.
for pattern_id in candidates_indices:
node_pattern = self.pattern_dag.get_node(pattern_id)
wires2 = self.pattern_dag.get_node(pattern_id).wires
control_wires2 = self.pattern_dag.get_node(pattern_id).control_wires
target_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)
or set(wires1) != set(wires2)
or node_circuit.op.name != node_pattern.op.name
):
continue
# Compare two operations
if _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.
for potential_block in self.pattern_dag.successors(pattern_id):
if not pattern_matched_match[potential_block]:
pattern_blocked_match[potential_block] = True
block_list.append(potential_block)
for block_id in block_list:
for succ_id in self.pattern_dag.successors(block_id):
pattern_blocked_match[succ_id] = True
if pattern_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)
if broken_matches_match:
global_broken.append(True)
else:
global_broken.append(False)
new_matches_scenario_match = [
elem
for elem in matches_scenario_match
if elem[0] not in broken_matches_match
]
condition = True
for back_match in match_backward:
if back_match not in new_matches_scenario_match: # pragma: no cover
condition = False
break
# First option greedy match.
if ([self.node_id_p, self.node_id_c] in new_matches_scenario_match) and (
condition or not match_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 = True
if global_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] = True
broken_matches = []
# Second option, not a greedy match, block all successors (push the gate
# to the right).
for succ in self.circuit_dag.get_node(circuit_id).successors:
circuit_blocked_block_s[succ] = True
if circuit_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 = [
elem for elem in matches_scenario_block_s if elem[1] not in broken_matches
]
condition_not_greedy = True
for back_match in match_backward:
if back_match not in new_matches_scenario_block_s:
condition_not_greedy = False
break
if ([self.node_id_p, self.node_id_c] in new_matches_scenario_block_s) and (
condition_not_greedy or not match_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).
if broken_matches and all(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] = True
for pred in self.circuit_dag.get_node(circuit_id).predecessors:
circuit_blocked_block_p[pred] = True
matching_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.
if not global_match:
circuit_blocked[circuit_id] = True
following_matches = []
successors = self.circuit_dag.get_node(circuit_id).successors
for succ in successors:
if circuit_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).predecessors
if not predecessors or not following_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).
for pred in predecessors:
circuit_blocked[pred] = True
matching_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).successors
for succ in successors:
circuit_blocked_nomatch[succ] = True
if circuit_matched_nomatch[succ]:
broken_matches.append(succ)
circuit_matched_nomatch[succ] = []
new_matches_scenario_nomatch = [
elem for elem in matches_scenario_nomatch if elem[1] not in broken_matches
]
condition_block = True
for back_match in match_backward:
if back_match not in new_matches_scenario_nomatch:
condition_block = False
break
if ([self.node_id_p, self.node_id_c] in matches_scenario_nomatch) and (
condition_block or not match_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) for m in match_store_list)
# Store the matches with maximal length.
for scenario in match_store_list:
if (len(scenario.match) == length) and not any(
scenario.match == x.match for x in self.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 = []
for i, (matched, blocked) in enumerate(zip(circuit_matched, circuit_blocked)):
if (not matched) and (not blocked):
gate_indices.append(i)
gate_indices.reverse()
return gate_indices
class MaximalMatches: # 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_matches
self.max_match_list = []
def run_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,
)
]
for matches in self.pattern_matches[1::]:
present = False
for max_match in self.max_match_list:
for elem in matches.match:
if elem in max_match.match and len(matches.match) <= len(max_match.match):
present = True
if not present:
self.max_match_list.append(Match(sorted(matches.match), matches.qubit))
class SubstitutionConfig: # 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_dag
self.circuit_config = circuit_config
self.template_config = template_config
self.qubit_config = qubit_config
self.pred_block = pred_block
class TemplateSubstitution: # 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_matches
self.circuit_dag = circuit_dag
self.template_dag = template_dag
self.substitution_list = []
self.unmatched_list = []
if custom_quantum_cost is not None:
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()
for node_id in circuit_sublist:
predecessors = predecessors | set(self.circuit_dag.get_node(node_id).predecessors)
exclude = set()
for elem in self.substitution_list[:index]:
exclude = exclude | set(elem.circuit_config) | set(elem.pred_block)
pred = list(predecessors - set(circuit_sublist) - exclude)
pred.sort()
return pred
def _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 = 0
for i in left:
cost_left += self.quantum_cost[self.template_dag.get_node(i).op.name]
cost_right = 0
for j in right:
cost_right += self.quantum_cost[self.template_dag.get_node(j).op.name]
return cost_left > cost_right
def _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.
"""
if self._quantum_cost(template_sublist, template_complement):
for elem in circuit_sublist:
for config in self.substitution_list:
if any(elem == x for x in config.circuit_config):
return False
return True
return False
def _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_complement
left = []
right = []
pred = set()
for index in template_sublist:
pred = pred | set(self.template_dag.get_node(index).predecessors)
pred = list(pred - set(template_sublist))
succ = set()
for index in template_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))
for elem in inverse:
if elem in pred:
left.append(elem)
elif elem in succ:
right.append(elem)
elif elem in comm:
right.append(elem)
left.sort()
right.sort()
left.reverse()
right.reverse()
total = left + right
return total
def _substitution_sort(self):
"""Sort the substitution list."""
ordered = False
while not ordered:
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.
"""
for scenario in self.substitution_list:
predecessors = set()
for match in scenario.circuit_config:
predecessors = predecessors | set(self.circuit_dag.get_node(match).predecessors)
predecessors = predecessors - set(scenario.circuit_config)
index = self.substitution_list.index(scenario)
for scenario_b in self.substitution_list[index::]:
if set(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)
return False
return True
def _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.
for scenario in self.substitution_list:
predecessors = set()
for index in scenario.circuit_config:
predecessors = predecessors | set(self.circuit_dag.get_node(index).predecessors)
list_predecessors.append(predecessors)
# Check if two groups of matches are incompatible.
for scenario_a in self.substitution_list:
if scenario_a in remove_list:
continue
index_a = self.substitution_list.index(scenario_a)
circuit_a = scenario_a.circuit_config
for scenario_b in self.substitution_list[index_a + 1 : :]:
if scenario_b in remove_list:
continue
index_b = self.substitution_list.index(scenario_b)
circuit_b = scenario_b.circuit_config
if (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.
if remove_list:
self.substitution_list = [
scenario for scenario in self.substitution_list if scenario not in remove_list
]
def substitution(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).
"""
while self.match_stack:
# Get the first match scenario of the list
current = self.match_stack.pop(0)
current_match = current.match
current_qubit = current.qubit
template_sublist = [x[0] for x in current_match]
circuit_sublist = [x[1] for x in current_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.
if self._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=lambda x: x.circuit_config[0])
# Change position of the groups due to predecessors of other groups.
self._substitution_sort()
for scenario in self.substitution_list:
index = self.substitution_list.index(scenario)
scenario.pred_block = self._pred_block(scenario.circuit_config, index)
circuit_list = []
for elem in self.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)))
_modules/pennylane/transforms/optimization/pattern_matching
Download Python script
Download Notebook
View on GitHub