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 C0 log2(1=”)+E(n; k), where k is the number of distinct phases in the diagonal n-qubit unitary, ” is the desired precision, C0 is a quality factor of the implementation method (1 < C0 < 4), and E(n; k) is the total entanglement cost (in T gates). We determine an optimal decision boundary in (k; n; “)-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 ” values and diagonal operators and can reduce the number of T gates exponentially in n when k << 2n.