Efficient Approximation of Diagonal Unitaries over the Clifford+T Basis

We present an algorithm for the approximate decomposition of diagonal operators, focusing specifically on decompositions over the Clifford+$T$ basis, that minimize the number of phase-rotation gates in the synthesized approximation circuit. The equivalent $T$-count of the synthesized circuit is bounded by $k \, C_0 \log_2(1/\varepsilon) + E(n,k)$, where $k$ is the number of distinct phases in the diagonal $n$-qubit unitary, $\varepsilon$ is the desired precision, $C_0$ is a quality factor of the implementation method ($1<C_0<4$), and $E(n,k)$ is the total entanglement cost (in $T$ gates). We determine an optimal decision boundary in $(k,n,\varepsilon)$-space where our decomposition algorithm achieves lower entanglement cost than previous state-of-the-art techniques. Our method outperforms state-of-the-art techniques for a practical range of $\varepsilon$ values and diagonal operators and can reduce the number of $T$ gates exponentially in $n$ when $k << 2^n$.