  The approximate stabilizer rank of a quantum state is the minimum number of
terms in any approximate decomposition of that state into stabilizer states.
Bravyi and Gosset showed that the approximate stabilizer rank of a so-called
"magic" state like $|T\rangle^{\otimes n}$, up to polynomial factors, is an
upper bound on the number of classical operations required to simulate an
arbitrary quantum circuit with Clifford gates and $n$ number of $T$ gates. As a
result, an exponential lower bound on this quantity seems inevitable. Despite
this intuition, several attempts using various techniques could not lead to a
better than a linear lower bound on the "exact" rank of ${|T\rangle}^{\otimes
n}$, meaning the minimal size of a decomposition that exactly produces the
state. For the "approximate" rank, which is more realistically related to the
cost of simulating quantum circuits, no lower bound better than $\tilde
\Omega(\sqrt n)$ has been known. In this paper, we improve the lower bound on
the approximate rank to $\tilde \Omega (n^2)$ for a wide range of the
approximation parameters. An immediate corollary of our result is the existence
of polynomial time computable functions which require a super-linear number of
terms in any decomposition into exponentials of quadratic forms over
$\mathbb{F}_2$, resolving a question in [Wil18]. Our approach is based on a
strong lower bound on the approximate rank of a quantum state sampled from the
Haar measure, a step-by-step analysis of the approximate rank of a magic-state
teleportation protocol to sample from the Haar measure, and a result about
trading Clifford operations with $T$ gates by [LKS18].
