  Simulating quantum circuits classically is an important area of research in
quantum information, with applications in computational complexity and
validation of quantum devices. One of the state-of-the-art simulators, that of
Bravyi et al, utilizes a randomized sparsification technique to approximate the
output state of a quantum circuit by a stabilizer sum with a reduced number of
terms. In this paper, we describe an improved Monte Carlo algorithm for
performing randomized sparsification. This algorithm reduces the runtime of
computing the approximate state by the factor $\ell/m$, where $\ell$ and $m$
are respectively the total and non-Clifford gate counts. The main technique is
a circuit recompilation routine based on manipulating exponentiated Pauli
operators. The recompilation routine also facilitates numerical search for
Clifford decompositions of products of gates, which can further reduce the
runtime in certain cases. It may additionally lead to a framework for
optimizing circuit implementations over a gate set, reducing the overhead for
state-injection in fault-tolerant implementations. We provide a concise
exposition of randomized sparsification, and describe how to use it to estimate
circuit amplitudes in a way which can be generalized to a broader class of
gates and states. This latter method can be used to obtain additive error
estimates of circuit probabilities with a faster runtime than the full
techniques of Bravyi et al. Such estimates are useful for validating near-term
quantum devices provided that the target probability is not exponentially
small.
