Tomorrow Raban will tell us about "Efficient template matching in quantum circuits", which appears in arXiv:1909.05270. The abstract appears below.

Best,

-joe

Abstract: In this talk, I will introduce an efficient algorithm to search for maximal matches of a small quantum circuit, called template, in a large circuit under consideration of pairwise commutation relations between quantum gates. Our algorithm provably finds all maximal matches with a running time that is polynomial in the number of gates and the number of qubits of the circuit for a fixed template size. Such an algorithm finds direct applications in quantum circuit optimization. Given a template circuit for which a lower-cost implementation is known, we may search for all instances of the template in a large circuit and replace them with their optimized version.