Canonical Form and Finite Blocklength Bounds for Stabilizer Codes

Abstract

First, a canonical form for stabilizer parity check matrices of arbitrary size and rank is derived. Next, it is shown that the closely related canonical form of the Clifford group can be computed in time $O(n^3)$ for $n$ qubits, which improves upon the previously known time $O(n^6)$. Finally, the related problem of finite blocklength bounds for stabilizer codes and Pauli noise is studied. A finite blocklength refinement of the hashing bound is derived, and it is shown that no argument that uses guessing the error as a substitute for guessing the coset can lead to a significantly better achievability bound.