Lower T-count with faster algorithms

Among the cost metrics characterizing a quantum circuit, the T-count stands out as one of the most crucial as its minimization is particularly important in various areas of quantum computation such as fault-tolerant quantum computing and quantum circuit simulation. In this work, we contribute to the T-count reduction problem by proposing efficient T-count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best T-count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of T gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal T-count than the state of the art on most quantum circuits evaluated. We also prove that the number of T gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of n qubits is upper bounded by n(n+1)/2+1, which improves on the worst-case T-count of existing optimization algorithms. From this we derive an upper bound of (n+1)(n+2h)/2+1 for the number of T gates in a Clifford+T circuit where h is the number of internal Hadamard gates in the circuit, i.e. the number of Hadamard gates lying between the first and the last T gate of the circuit.