Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank

Abstract

We show that a form of strong simulation for $n$-qubit quantum stabilizer circuits $C$ is computable in $O(s+n^{\omega })$ time, where $\omega$ is the exponent of matrix multiplication. Solution counting for quadratic forms over ${\mathbb{F}}_2$ is also placed into $O(n^{\omega })$ time. This improves previous $O(n^3)$ bounds. Our methods in fact show an $O(n^2)$-time reduction from matrix rank over ${\mathbb{F}}_2$ to computing $p=|⟨0^n|C|0^n⟩{|}^2$ (hence also to solution counting) and a converse reduction that is $O(s+n^2)$ except for matrix multiplications used to decide whether $p>0$. The current best-known worst-case time for matrix rank is $O(n^{\omega })$ over ${\mathbb{F}}_2$, indeed over any field, while $\omega$ is currently upper-bounded by $2.3728\dots$ Our methods draw on properties of classical quadratic forms over ${\mathbb{Z}}_4$. We study possible distributions of Feynman paths in the circuits and prove that the differences in $+1$ vs. $-1$ counts and $+i$ vs. $-i$ counts are always $0$ or a power of $2$. Further properties of quantum graph states and connections to graph theory are discussed.

Main change is to conclusion section: more information about relation to matroids and the generalized Tutte polynomial

References in corpus (11)

• Improved Simulation of Stabilizer Circuits
• Improved classical simulation of quantum circuits dominated by Clifford gates
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Fast simulation of stabilizer circuits using a graph state representation
• Quantum Supremacy Is Both Closer and Farther than It Appears
• Quantum circuits and low-degree polynomials over F_2
• Further extensions of Clifford circuits and their classical simulation complexities
• Classical simulation of quantum circuits by half Gauss sums
• Computing quopit Clifford circuit amplitudes by the sum-over-paths technique
• On Tractable Exponential Sums
• Symmetric indefinite triangular factorization revealing the rank profile matrix

Cited by in corpus (3)

• Fast Stabiliser Simulation with Quadratic Form Expansions
• Simulating Quantum Computations with Tutte Polynomials
• Fast simulation of planar Clifford circuits