T-count and T-depth of any multi-qubit unitary

While implementing a quantum algorithm it is crucial to reduce the quantum resources, in order to obtain the desired computational advantage. For most fault-tolerant quantum error-correcting codes the cost of implementing the non-Clifford gate is the highest among all the gates in a universal fault-tolerant gate set. In this paper we design provable algorithm to determine T-count of any $n$-qubit ($n\geq 1$) unitary $W$ of size $2^n\times 2^n$, over the Clifford+T gate set. The space and time complexity of our algorithm are $O\left(2^{2n}\right)$ and $O\left(2^{2n\mathcal{T}_{\epsilon}(W)+4n}\right)$ respectively. $\mathcal{T}_{\epsilon}(W)$ ($\epsilon$-T-count) is the (minimum possible) T-count of an exactly implementable unitary $U$ i.e. $\mathcal{T}(U)$, such that $d(U,W)\leq\epsilon$ and $\mathcal{T}(U)\leq\mathcal{T}(U')$ where $U'$ is any exactly implementable unitary with $d(U',W)\leq\epsilon$. $d(.,.)$ is the global phase invariant distance. Our algorithm can also be used to determine the (minimum possible) T-depth of any multi-qubit unitary and the complexity has exponential dependence on $n$ and $\epsilon$-T-depth. This is the first algorithm that gives T-count or T-depth of any multi-qubit ($n\geq 1$) unitary. For small enough $\epsilon$, we can synthesize the T-count and T-depth-optimal circuits. Our results can be used to determine the minimum count (or depth) of non-Clifford gates required to implement any multi-qubit unitary with a universal gate set consisting of Clifford and non-Clifford gates like Clifford+CS, Clifford+V, etc. To the best of our knowledge, there were no such optimal-synthesis algorithm for arbitrary multi-qubit unitaries in any universal gate set.
Comment: Accepted for publication in Nature Partner Journal Quantum Information. Not structured according to the journal policies. Compared to v3 : A note about implementation of 2-qubit QFT in Table 3