Catalytic <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>z</mml:mi> </mml:math> -rotations in constant <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> -depth

We show that the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> -depth of any single-qubit <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>z</mml:mi> </mml:math> -rotation can be reduced to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mn>3</mml:mn> </mml:math> if a certain catalyst state is available. To achieve an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>&amp;#x03F5;</mml:mi> </mml:math> -approximation, it suffices to have a catalyst state of size polynomial in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>log</mml:mi> <mml:mo>&amp;#x2061;</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>&amp;#x03F5;</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> . This implies that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="sans-serif">Q</mml:mi> <mml:mi mathvariant="sans-serif">N</mml:mi> <mml:mi mathvariant="sans-serif">C</mml:mi> </mml:mrow> <mml:mi>f</mml:mi> <mml:mn>0</mml:mn> </mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="sans-serif">q</mml:mi> <mml:mi mathvariant="sans-serif">p</mml:mi> <mml:mi mathvariant="sans-serif">o</mml:mi> <mml:mi mathvariant="sans-serif">l</mml:mi> <mml:mi mathvariant="sans-serif">y</mml:mi> </mml:mrow> </mml:math> admits a finite universal gate set consisting of Clifford+ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> . In particular, there are catalytic constant <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> -depth circuits that approximate multi-qubit Toffoli, adder, and quantum Fourier transform arbitrarily well. We also show that the catalyst state can be prepared in time polynomial in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>log</mml:mi> <mml:mo>&amp;#x2061;</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>&amp;#x03F5;</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> .