Everyone is welcome to attend the online QuSoft lecture of Ryan Mann (University of Bristol) with the title 'Simulating Quantum Computations with Tutte Polynomials'.
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 graphs. The algorithm evaluates the Tutte polynomial recursively using the deletion-contraction property while attempting to exploit structural properties of the graph. 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. Contrary to the paper, this talk will avoid the language of matroids.
Please contact Suhasree Patro or Jop Briet for the zoom link.
