Lower T-count with faster algorithms

Among the cost metrics characterizing a quantum circuit, the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math>-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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math>-count reduction problem by proposing efficient <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math>-count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math>-count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math>-count than the state of the art on most quantum circuits evaluated. We also prove that the number of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> qubits is upper bounded by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:math>, which improves on the worst-case <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math>-count of existing optimization algorithms. From this we derive an upper bound of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn><mml:mi>h</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:math> for the number of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> gates in a Clifford<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>+</mml:mo><mml:mi>T</mml:mi></mml:math> circuit where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>h</mml:mi></mml:math> is the number of internal Hadamard gates in the circuit, i.e. the number of Hadamard gates lying between the first and the last <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>T</mml:mi></mml:math> gate of the circuit.