  We present two classical algorithms for the simulation of universal quantum
circuits on $n$ qubits constructed from $c$ instances of Clifford gates and $t$
arbitrary-angle $Z$-rotation gates such as $T$ gates. Our algorithms complement
each other by performing best in different parameter regimes. The
$\tt{Estimate}$ algorithm produces an additive precision estimate of the Born
rule probability of a chosen measurement outcome with the only source of
run-time inefficiency being a linear dependence on the stabilizer extent (which
scales like $\approx 1.17^t$ for $T$ gates). Our algorithm is state-of-the-art
for this task: as an example, in approximately $25$ hours (on a standard
desktop computer), we estimated the Born rule probability to within an additive
error of $0.03$, for a $50$ qubit, $60$ non-Clifford gate quantum circuit with
more than $2000$ Clifford gates. The $\tt{Compute}$ algorithm calculates the
probability of a chosen measurement outcome to machine precision with run-time
$O(2^{t-r} (t-r)t)$ where $r$ is an efficiently computable, circuit-specific
quantity. With high probability, $r$ is very close to $\min \{t, n-w\}$ for
random circuits with many Clifford gates, where $w$ is the number of measured
qubits. $\tt{Compute}$ can be effective in surprisingly challenging parameter
regimes, e.g., we can randomly sample Clifford+$T$ circuits with $n=55$, $w=5$,
$c=10^5$ and $t=80$ $T$-gates, and then compute the Born rule probability with
a run-time consistently less than $10^4$ seconds using a single core of a
standard desktop computer. We provide a C+Python implementation of our
algorithms.
