Abstract
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 deletioncontraction 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.
Original language  English 

Journal  arXiv 
Publication status  Unpublished  1 Jan 2021 
Keywords
 quantph
 cs.CC
 cs.DS
 math.CO
Fingerprint
Dive into the research topics of 'Simulating Quantum Computations with Tutte Polynomials'. Together they form a unique fingerprint.Datasets

Data from "Simulating Quantum Computations with Tutte Polynomials"
Mann, R. L. (Creator) & Montanaro, A. M. R. (Data Manager), University of Bristol, 1 Jan 2021
DOI: 10.5523/bris.kbhgclva863q21tjkqpyr5uvq, http://data.bris.ac.uk/data/dataset/kbhgclva863q21tjkqpyr5uvq
Dataset