  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.
