Faster stabilizer-state simulation based on graph states

Classical simulation is a crucial element of the performance prediction and design of Noisy-Intermediate Scale Quantum (NISQ) computers. Since it is well-known that quantum circuits with only Clifford gates can be simulated in polynomial time in the number of gates, current research is mainly focused on speedups for non-Clifford gates. However, many scenarios would still benefit greatly from faster Clifford-gate simulation. One example are quantum networks, since most quantum network protocols only contain Cliffords and current hardware can to a large extent be modelled by Clifford noise. Moreover, for e.g. design optimization and Monte Carlo methods, the simulation algorithm will be run many times, thus amplifying any runtime gains manifold. Our contributions regard improvement of existing Clifford-gate simulation based on a graph state formalism, which is in many cases faster than the conventional stabilizer-based simulation approach. Specifically, we focus on faster simulation of individual two-qubit gates, as well as scheduling algorithms for sequences of two-qubit gates. We also provide algorithms for fidelity and partial trace. Numerics confirm our approach yields significant runtime improvements in many situations.