Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities

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 nonclassical resources in quantum computation.

Figure 1

Plot of the difference ${\widehat{p}}_s-⟨\widehat{p}⟩$ between the estimated probability and the true probability of the outcome $|0⟩⟨0|$ for the first qutrit as a function of the number of magic states $k$. Each data point represents a random 100-qutrit Clifford circuit with the nonmagic states initialized to the $|0⟩$ state. The number of samples $s(k)$ was chosen using Eq. (12) with target precision $\epsilon =0.01$ (indicated by the solid line) with 95% confidence ($\delta =0.05$), so the number of samples increases exponentially with $k$ (color scale).