  We present a method for estimating the probabilities of outcomes of a quantum
circuit using Monte Carlo sampling techniques applied to a quasiprobability
representation. Our estimate converges to the true quantum probability at a
rate determined by the total negativity in the circuit, using a measure of
negativity based on the 1-norm of the quasiprobability. If the negativity grows
at most polynomially in the size of the circuit, our estimator converges
efficiently. These results highlight the role of negativity as a measure of
non-classical resources in quantum computation.
