Quantum Compilers for Reducing Non-Clifford Gate Counts

Quantum computers can solve certain problems much faster than classical computers. However, in order to benefit from the speed-up granted by quantum algorithms, they must first be rendered as hardware-level instructions (i.e. quantum circuits) in a process known as quantum compiling. Any choice of discrete gate set from which our compilation result is constructed should be both universal and fault-tolerant, such that any quantum algorithm can be compiled and successfully executed despite the presence of environmental noise. From these requirements, it follows that it is impossible to avoid including at least one gate that is disproportionately expensive relative to the others. Many leading proposals for the first generation of qubit-based quantum computers designate the T gate, otherwise known as the pi/8 gate, to be this necessary yet costly gate. In this thesis, we present novel algorithms for compiling quantum circuits that reduce the T count of input circuits. In addition, we present analogous compilation algorithms for qudit-based quantum computers, for which the M gate is the designated expensive gate.