Optimal dense materialization of the stabilizer formalism without polynomial overhead

Abstract

Stabilizer states and Clifford transformations constitute the exactly tractable backbone of quantum information science, from error correction and fault tolerance to benchmarking and simulation. Although these objects admit compact classical descriptions, many physical and computational workflows still require their explicit dense forms such as a full wavefunction for a stabilizer state or a full matrix for a Clifford transformation. In such explicit output tasks, exponential scaling is unavoidable because the outputs themselves have sizes $2^n$ and $4^n$. The fundamental question is therefore whether compact stabilizer and Clifford descriptions can be expanded with no additional polynomial overhead. Here we answer this question affirmatively. We present optimal algorithms that materialize an $n$-qubit stabilizer state vector in $O(2^n)$ time and a full dense Clifford matrix in $O(4^n)$ time. The same framework also yields an optimal conversion from standard stabilizer check matrices to state vectors and, for every fixed odd prime qudit dimension $\ell$, gives $O({\ell }^n)$-time materialization of qudit stabilizer states. As an additional compact-to-compact result, we design a sign-aware Four Russians method for converting stabilizer check matrices to quadratic forms faster than Gaussian elimination. These results close the asymptotic gap between compact descriptions of the stabilizer formalism and their dense representations.

31 pages, 3 figures