Fast sparse Gaussian elimination over an arbitrary field and applications to quantum stabilizer states

We present a new LDL factorization algorithm that requires O(nt^{omega-1}) field operations, where t is the treewidth of the graph associated with the nonzeros of a full-rank sparse matrix. This algorithm matches the best known bounds for Cholesky and extends to LU. For low-rank matrices or rectangular LU, our algorithm also gives the factorization in implicit form. Obtaining an explicit form of low rank factors in O(nt^{\omega-1}) time remains an open problem. The main idea of the new algorithm is based on iterative application of a block factorization of saddle-point systems that is equivalent to the null space method and to LDL. We also discuss connections of tree-decomposition-based LDL and butterfly/hierarchical low-rank factorization of the inverse of a sparse matrix.

We then discuss the relationship between LDL and the representation of quantum stabilizer states, which enable polynomial-time simulation of Clifford circuits. In particular, we provide a simple explicit formula for the amplitudes of a Hadamard-transformed graph state, based on a modified Gauss-Jordan matrix inversion process that is closely related to LDL factorization. This formula enables us to directly characterize all pairs of graphs states that are equivalent under application of local Clifford unitaries, as well as match the best known bounds for Clifford circuit simulation. Overall, the LDL and stabilizer-state results reverse the construction of Gosset, Grier, Kerzner, and Schaeffer (Quantum 2024), who provide an O(nt^{omega-1})-time LDL algoithm for solving symmetric linear systems over GF(2) by reduction to a tree-decomposition-based Clifford circuit simulation algorithm.

This seminar is part of the Recent Progress and Open Directions in Matrix Computations series.