  We establish a classical heuristic algorithm for exactly computing quantum
probability amplitudes. Our algorithm is based on mapping output probability
amplitudes of quantum circuits to evaluations of the Tutte polynomial of
graphic matroids. The algorithm evaluates the Tutte polynomial recursively
using the deletion-contraction property while attempting to exploit structural
properties of the matroid. We consider several variations of our algorithm and
present experimental results comparing their performance on two classes of
random quantum circuits. Further, we obtain an explicit form for Clifford
circuit amplitudes in terms of matroid invariants and an alternative efficient
classical algorithm for computing the output probability amplitudes of Clifford
circuits.
