Unifying Graph Measures and Stabilizer Decompositions for the Classical Simulation of Quantum Circuits

Various algorithms have been developed to simulate quantum circuits on classical hardware. Among the most prominent are approaches based on stabilizer decompositions and tensor network contraction. In this work, we present a unified framework that bridges these two approaches, placing them under a common formalism. Using this, we present two new algorithms to simulate an n-qubit circuit C: one that runs in {O}\(T^{mathsf{tw}(C\)}) time and the other in {O}\(T^{γcdot mathsf{tw}(C\)}) time, where mathsf{tw}(C) and mathsf{rw}(C) refer to the the tree-width and rank-width, respectively, of a tensor network associated to C, T is the number of non-Clifford gates in C, and γapprox 3.42. The proposed algorithms are simple, only require a linear amount of memory, are trivially parallelizable, and interact nicely with ZX-diagram simplification routines. Furthermore, we introduce the refined complexity measures focused tree-width and focused rank-width, which are always at least as efficient as their standard equivalent; these can be directly applied within our simulation algorithms, allowing for a more precise upper bound on the run time.