Classical simulation of quantum circuits by graphical stabiliser decompositions - Aleks Kissinger

Classical simulation of quantum circuits by graphical stabiliser decompositions

Aleks Kissinger

Abstract: Classical simulation of arbitrary Clifford+T quantum circuits is expected to be hard. However, if such a circuit prepares a state which can be decomposed as a sum of relatively few stabiliser states, the problem becomes easy, thanks to the Gottesman-Knill theorem. While optimal stabiliser decompositions are difficult to compute in general, there exists a techniques for producing stabiliser decompositions by decomposing T gates in a circuit in "chunks" of 6 or more at a time. In this talk, I'll introduce a graphical variation on this "chunking" technique based on the ZX calculus. ZX diagrams give an efficient way to represent a state prepared by a Clifford+T circuit, which can then be iteratively decomposed to into efficiently simulable parts. The diagrammatic representation gives some extra flexibility in how we perform decompositions, and most importantly, allows us to interleave decomposition with automated diagram simplification using the ZX calculus. Since non-Clifford structure can cancel out during simplification, this sometimes yields reductions in the numbers of stabiliser terms of hundreds of orders of magnitude. Using this approach, we demonstrate strong simulation of hidden shift circuits with up to 1400 T gates, which is about 20 times as large as any previously simulated with stabiliser rank techniques.