Optimising Clifford Circuits with Quantomatic

Remarkable advances in the past two years have seen quantum computing hardware reach the point where the deployment of quantum devices for nontrivial tasks is now a near-term prospect. However, these machines still suffer from severe limitations, both in terms of memory size and the coherence time of their qubits. It is therefore of paramount importance to extract the most useful work from the fewest operations: a poorly optimised quantum program may not be able to finish before it is undone by noise. In this paper we study the automated optimisation of Clifford circuits. Clifford circuits are not universal for quantum computation - they are well known to be efficiently simulable by a classical computer [2] - however adding any non-Clifford gate to the Cliffords yields a set of approximately universal operations hence it is likely that the vast majority of operations in any quantum program will be Clifford operations, and hence reducing the Clifford depth and gate count of a circuit will have substantial benefit.