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

Abstract

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\ge 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}}_{ϵ}(W)+4n}\right)$ respectively. ${\mathcal{T}}_{ϵ}(W)$ ($ϵ$-T-count) is the (minimum possible) T-count of an exactly implementable unitary $U$ i.e. $\mathcal{T}(U)$, such that $d(U,W)\le ϵ$ and $\mathcal{T}(U)\le \mathcal{T}(U^{\prime })$ where $U^{\prime }$ is any exactly implementable unitary with $d(U^{\prime },W)\le ϵ$. $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 $ϵ$-T-depth. This is the first algorithm that gives T-count or T-depth of any multi-qubit ($n\ge 1$) unitary. For small enough $ϵ$, 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.