Counting unitaries of T-depth one

Abstract

We show that the number of T-depth one unitaries on $n$ qubits is ${\sum }_{m=1}^n\frac{1}{m!}{\prod }_{k=0}^{m-1}(4^n/2^k-2^k)\times \#{\mathcal{C}}_n,$ where $\#{\mathcal{C}}_n$ is the size of the $n$-qubit Clifford group, that is the number of unitaries of T-depth zero. The number of T-depth one unitaries on $n$ qubits grows as $2^{\Omega (n^2)}\cdot \#{\mathcal{C}}_n$.

7 pages