Optimal dense materialization of the stabilizer formalism without polynomial overhead

arXiv:2604.15405v3 Announce Type: replace 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.

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.

arXiv:2604.15405 [quant-ph]

(or arXiv:2604.15405v3 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2604.15405 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Optimal dense materialization of the stabilizer formalism without polynomial overhead

Subiecte conexe