To the recorded seminar

A general quantum circuit can be simulated in exponential time on a classical computer. If the circuit has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally exponential in the treewidth of the underlying graph. Separately, Gottesman and Knill showed that if all gates in a quantum circuit are restricted to be Clifford, then there is a polynomial time simulation. We combine these two ideas and show that treewidth and planarity can be used to improve Clifford circuit simulation. Our main result is a classical algorithm with runtime upper bounded as n^{1.19} which samples from the output distribution obtained by measuring each qubit of a quantum planar graph state in given Pauli bases. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. This is joint work with Daniel Grier, Alex Kerzner, and Luke Schaeffer.