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 is the best known upper bound achievable in polynomial time. 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.