# qml.pattern_matching¶

pattern_matching(circuit_dag, pattern_dag)[source]

Function that applies the pattern matching algorithm and returns the list of maximal matches.

Parameters
• circuit_dag (CommutationDAG) – A commutation DAG representing the circuit to be optimized.

• pattern_dag (CommutationDAG) – A commutation DAG representing the pattern.

Returns

the list of maximal matches.

Return type

list(Match)

Example

First let’s consider the following circuit

def circuit():
qml.S(wires=0)
qml.PauliZ(wires=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.PauliX(wires=0))


Assume that we want to find all maximal matches of a pattern containing a sequence of two S gates and a PauliZ gate:

def pattern():
qml.S(wires=0)
qml.S(wires=0)
qml.PauliZ(wires=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 provides 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 (S) in the pattern with the first gate in the circuit and also the third gate in the pattern (PauliZ) with the second circuit gate.

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