  In this short note we show that Boolean satisfiability reduces to finding the
optimal number of T gates of a quantum circuit, and hence that optimising
T-count is NP-hard. We show that the same argument extends to optimising the
number of Toffoli gates in a reversible classical circuit, and we furthermore
find an upper bound to the T-count problem of $\text{NP}^{\text{NQP}}$.
