  We investigate Clifford+$T$ quantum circuits with a small number of
$T$-gates. Using the sparsification lemma, we identify time complexity lower
bounds in terms of $T$-gate count below which a strong simulator would improve
on the state-of-the-art $3$-SAT solving.
