Joel Wallman

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.

A promising technological advancement meant to enlarge our computational means is the quantum computer. Such a device would harvest the natural complexity of the physical world on the quantum scale in order to unfold concrete mathematical problems more efficiently. This is for instance demonstrated by the exponential advantage of Shor's factoring algorithm over the best know previous factoring method. However, while this natural complexity forms the backbone of quantum computing, it also rises important issues. Indeed, the inevitable errors emerging from the implementation of quantum operations are likewise quantum, and hence share a similar level of intricacy.