Binary Matroids and Quantum Probability Distributions

Abstract

We characterise the probability distributions that arise from quantum circuits all of whose gates commute, and show when these distributions can be classically simulated efficiently. We consider also marginal distributions and the computation of correlation coefficients, and draw connections between the simulation of stabiliser circuits and the combinatorics of representable matroids, as developed in the 1990s.

24 pages (inc appendix & refs)

Cited by in corpus (5)

• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• From estimation of quantum probabilities to simulation of quantum circuits
• Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable