Speaker
Description
Pattern matching of quantum circuits, the task of finding sub-circuits of a quantum circuit that match a given pattern, is an essential tool of quantum circuit compilation. It can be used for instance to find redundant gate sequences that can be rewritten as more efficient computations. We propose an algorithm that performs this task for many patterns simultaneously, independently of the number of patterns. After a pre-computation step, in which the patterns are compiled into a decision tree, all pattern matches can be enumerated in time linear in the size of the input quantum circuit and in the size of the output. More precisely, given a set of patterns with at most $N$ qubits and circuit depth $\delta$, we enumerate all $m$ pattern matches of a circuit with $|C|$ gates in time $O(N)^{N + \frac{1}{2}} \cdot \delta \log \delta \cdot |C| + O(m)$.
