Improved graph formalism for quantum circuit simulation
Alexander Tianlin Hu, Andrey Boris Khesin · Physical Review A · 2022
Improving the simulation of quantum circuits on classical computers is important for understanding quantum advantage and increasing development speed. In this paper, we explore a way to express stabilizer states and further improve the speed of simulating stabilizer circuits with a current existing approach. First, we discover a unique and elegant canonical form for stabilizer states based on graph states to better represent stabilizer states and show how to efficiently simplify stabilizer states to canonical form. Second, we develop an improved algorithm for graph state stabilizer simulation and establish limitations on reducing the quadratic runtime of applying controlled Pauli $Z$ gates. We do so by creating a simpler formula for combining two Pauli-related stabilizer states into one. Third, to better understand the linear dependence of stabilizer states, we characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our controlled Pauli $Z$ algorithm, we improve runtime for inner product computation from $O({n}^{3})$ to $O(n{d}^{2})$, where $d$ is the maximum degree of the graph encountered during the calculation.