Quantum circuits are considered more powerful than classical circuits and require exponential resources to simulate classically. Clifford circuits are a special class of quantum circuits that can be simulated in polynomial time but still show important quantum effects such as entanglement. In this work, we present an algorithm that simulates Clifford circuits by performing Gaussian elimination on a modified adjacency matrix derived from the circuit structure. Our work builds on an ZX-calculus tensor network representation of Clifford circuits that reduces to quantum graph states. We give a concise formula of amplitudes of graph states based on the LDL decomposition of matrices over GF(2), and use it to get efficient algorithms for strong and weak simulation of Clifford circuits using tree-decomposition-based fast LDL algorithm. The complexity of our algorithm matches the state of art for weak graph state simulation and improves the state of art for strong graph state simulation by taking advantage of Strassen-like fast matrix multiplication. Our algorithm is also efficient when computing many amplitudes or samples of a Clifford circuit. Further, our amplitudes formula provides a new characterization of locally Clifford equivalent graph states as well as an efficient protocol to learn graph states with low-rank adjacency matrices.

翻译：量子电路被认为比经典电路更强大，且需要指数级资源才能在经典计算机上模拟。克利福德电路是一类特殊的量子电路，可在多项式时间内模拟，但仍展现出如纠缠等重要量子效应。本研究提出一种算法，通过对从电路结构导出的修正邻接矩阵执行高斯消元来模拟克利福德电路。我们的工作基于克利福德电路的ZX演算张量网络表示，该表示可简化为量子图态。我们基于GF(2)域上矩阵的LDL分解，给出了图态振幅的简明公式，并利用基于树分解的快速LDL算法，为克利福德电路的强模拟与弱模拟提供了高效算法。该算法的复杂度与弱图态模拟的现有最优技术持平，并通过利用类Strassen快速矩阵乘法，改进了强图态模拟的现有最优技术。在计算克利福德电路的多个振幅或样本时，我们的算法同样高效。此外，我们的振幅公式为局部克利福德等价图态提供了新的表征方法，并为学习具有低秩邻接矩阵的图态提供了一种高效协议。