Compilation Algorithms for Gate-Based Quantum Computing

Abstract

This thesis addresses the compilation of quantum circuits by swap gate insertion, a process in which a series of quantum gates, is to be made executable on a given device by manipulating its storage pattern. Utilizing results by Even and Miltzow et al. we find an abstract linear programming formulation of sequential quantum compilation approximately minimizing the compilation effort on lattice quantum architectures for a broad class of quantum circuits. The linear program is polynomial-time solvable and its solution can be used to extract feasible compilations at polylogarithmic overhead in total gate count by adaption of results on high-dimensional embeddings and random projections by Feige and Vempala. A method of Rotter and Vygen can be applied to improve the approximation ratio under the assumption of a conjecture on optimal solutions for periodic boundary conditions. For a general parallel model of quantum compilation we find that attaining similar approximations reduces to the choice of an appropriate gate execution order, applying results by Demaine et al. on parallel motion planning. Furthermore two locally optimal compilation heuristics are presented and their performance tested on benchmarks from Tan and Cong's optimality study of existing quantum computing layout synthesis tools.