January 1, 2021
I have just uploaded to arXiv the paper "Simulating Quantum Computations with Tutte Polynomials". In this paper 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. Our algorithm proceeds to evaluate the Tutte polynomial recursively using the deletion-contraction property. At each step in the recursion, our algorithm computes certain structural properties of the matroid in order to attempt to prune the computational tree. This approach to computing Tutte polynomials was first studied by Haggard, Pearce, and Royle. Our algorithm can be seen as an adaption of their work to special points of the Tutte plane where we can exploit additional structural properties.
The performance of algorithms for computing Tutte polynomials based on the deletion-contraction property depends on the heuristic used to decide the ordering of the recursion. We consider several heuristics introduced by Pearce, Haggard, and Royle and a new heuristic, which is specific to our algorithm. We present some experimental results comparing the performance of these heuristics on two classes of random quantum circuits corresponding to dense and sparse instances.
The correspondence between output probability amplitudes of quantum circuits and evaluations of Tutte polynomials also allows us to obtain an explicit form for Clifford circuit amplitudes in terms of matroid invariants by a theorem of Pendavingh. This gives rise to an alternative efficient classical algorithm for computing output probability amplitudes of Clifford circuits.