Error Correction

Abstract: We present a simple algorithm that implements an arbitrary $n$-qubit unitary operator using a Clifford+T circuit with T-count $O(2^{4n/3} n^{2/3})$. This improves upon the previous best known upper bound of $O(2^{3n/2} n)$, while the best known lower bound remains $\Omega(2^n)$. Our construction is based on a recursive application of the cosine-sine decomposition, together with a generalization of the optimal diagonal unitary synthesis method by Gosset, Kothari, and Wu to multi-controlled $k$-qubit unitaries.

Abstract: The Clifford hierarchy is a fundamental structure in quantum computation whose mathematical properties are not fully understood. In this work, we characterize permutation gates---unitaries which permute the $2^n$ basis states---in the third level of the hierarchy. We prove that any permutation gate in the third level must be a product of Toffoli gates in what we define as \emph{staircase form}, up to left and right multiplications by Clifford permutations. We then present necessary and sufficient conditions for a staircase form permutation gate to be in the third level of the Clifford hierarchy. As a corollary, we construct a family of non-semi-Clifford permutation gates $\{U_k\}_{k\geq 3}$ in staircase form such that each $U_k$ is in the third level but its inverse is \emph{not} in the $k$-th level.