  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.
