Hi all,
Tomorrow we again have two master thesis talks, this time by Romain Moyard and Christian Bertoni. Romain worked with Raban on circuit optimization, and Christian worked with me on information theory and renormalization. Titles and abstracts for their talks are below. Here's the zoom link: https://ethz.zoom.us/j/362994444
Best,
-joe
----------------
Romain Moyard ~
Title: Implementation, improvement and testing of an efficient template matching algorithm
Abstract: Given a large and a small quantum circuit, an algorithm to find all maximal matches of the small circuit, called template, in the large circuit under consideration of pairwise commutation relations between quantum gates was suggested by Iten et al. in arXiv:1909.05270. In this talk, we present the result of the implementation of this algorithm into the software library Qiskit-terra. We check its correctness by comparing it with another, less efficient, algorithm that finds all the maximal matches. We find two kinds of cases that were not correctly handled in the efficient matching algorithm and correct them. Our implementation shows that the average time complexity of the algorithm scales much better than the theoretical worst-case time complexity. In addition, we present different heuristics to speed up the matching algorithm with the trade-off of probably not finding all maximal matches. We apply the matching algorithm for circuit optimization on random circuits and also on benchmark circuits that are already heavily optimized. In both cases, we can significantly improve the implementation cost of the circuits. Finally we present an adapted version of the algorithm that finds all maximal gate sequences acting on a given qubit set in a circuit. This is promising for peephole optimization.
Preprint: arXiv:1909.05270
------
Christian Bertoni ~
Title: Information theory and renormalization in statistical mechanics
Abstract: Renormalization in statistical mechanics is a process in which a system is mapped to a different scale. It arises naturally when considering phase transitions, since statistical systems exhibit scale invariance at criticality. It is natural to think that this process eliminates information, and that it should have an information theoretic interpretation. In this talk I will present two different ways in which tools from information theory can be applied to the problem of renormalization, focusing on the question of whether one can select an appropriate renormalization map by using simple information theoretic criteria.