  We consider quantum circuits composed of Clifford and T gates. In this
context the T gate has a special status since it confers universal computation
when added to the (classically simulable) Clifford gates. However it can be
very expensive to implement fault-tolerantly. We therefore view this gate as a
resource which should be used only when necessary. Given an n-qubit unitary U
we are interested in computing a circuit that implements it using the minimum
possible number of T gates (called the T-count of U). A related task is to
decide if the T-count of U is less than or equal to m; we consider this problem
as a function of N=2^n and m. We provide a classical algorithm which solves it
using time and space both upper bounded as O(N^m poly(m,N)). We implemented our
algorithm and used it to show that any Clifford+T circuit for the Toffoli or
the Fredkin gate requires at least 7 T gates. This implies that the known 7 T
gate circuits for these gates are T-optimal. We also provide a simple
expression for the T-count of single-qubit unitaries.
