Lower Bounds for Quantum Circuits

Abstract

In quantum computing, computational tasks are represented by quantum circuits. These circuits are composed of gates whose physical realization comes at a cost. Typically, gates from the so-called Clifford group are considered cheap, while non Clifford gates are considered expensive. Consequently, non-Clifford operations are often seen as a resource whose use should be minimized. In this thesis, following recent work by Beverland and others, we study lower bounds for the number of non-Clifford gates in quantum circuits. We focus on lower bounds that can be derived from monotones, which are real-valued functions of quantum states that are non-increasing under Clifford operations. We first provide a detailed presentation of two recently introduced monotones: the stabilizer nullity and the dyadic monotone. We then discuss how these monotones can be used to give lower bounds for the non-Clifford resources for two important quantum operations: the multiply-controlled Pauli Z gate and the modular adder.