Fast algorithms for classical specifications of stabiliser states and Clifford gates

The stabiliser formalism plays a central role in quantum computing, error correction, and fault-tolerance. Stabiliser states are used to encode quantum data. Clifford gates are those which can be easily performed fault-tolerantly in the most common error correction schemes. Their mathematical properties are the subject of significant research interest. Numerical experiments are critical to formulating and testing conjectures involving the stabiliser formalism. Conversions between different specifications of stabiliser states and Clifford gates are also important components of classical algorithms for simulating quantum circuits. In this note, we provide fast methods for verifying that a vector is a stabiliser state, and interconverting between its specification as amplitudes, a quadratic form, and a check matrix. We use these to rapidly check if a given unitary matrix is a Clifford gate and to convert between the matrix of a Clifford gate and its compact specification as a stabiliser tableau. For example, we extract the stabiliser tableau of a Clifford gate matrix with $N^2$ entries, which naively requires $O(N^3 \log N)$ time, in time $O(N \log N)$. Our methods outperform the best-known brute force methods by some orders of magnitude with asymptotic improvements that are exponential in the number of qubits. We provide example implementations of our algorithms in Python.