Catalytic z-rotations in constant T-depth

We show that the T-depth of any single-qubit z-rotation can be reduced to $3$ if a certain catalyst state is available. To achieve an $ε$-approximation, it suffices to have a catalyst state of size polynomial in log(1/ε). This implies that QNC⁰f/qpoly admits a finite universal gate set consisting of Clifford+T. In particular, there are catalytic constant T-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 log (1/ε).