Efficient Approximation of Diagonal Unitaries over the Clifford+T Basis

Abstract

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/\epsilon )+E(n,k)$, where $k$ is the number of distinct phases in the diagonal $n$-qubit unitary, $\epsilon$ 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,\epsilon )$-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 $\epsilon$ values and diagonal operators and can reduce the number of $T$ gates exponentially in $n$ when $k<<2^n$.