Simulating quantum computation by contracting tensor networks

Igor L. Markov, Yaoyun Shi

The treewidth of a graph is a useful combinatorial measure of how close the graph is to a tree. We prove that a quantum circuit with $T$ gates whose underlying graph has treewidth…