Optimal algorithms for materializing stabilizer states and Clifford gates from compact descriptions
Pith reviewed 2026-05-10 10:50 UTC · model grok-4.3
The pith
Stabilizer states can be materialized into full amplitude vectors in optimal O(2^n) time from quadratic-form descriptions.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Starting from the standard quadratic-form representation of stabilizer states, we give an algorithm that runs in O(2^n) time and O(2^n) space. The idea is to maintain a cached parity word that records all future off-diagonal quadratic phase increments simultaneously. As consequences, we obtain an optimal procedure for materializing a stabilizer state vector from a standard check-matrix description, and an optimal algorithm for expanding a Clifford tableau into its full dense matrix. These results close the asymptotic gap for dense stabilizer and Clifford materialization.
What carries the argument
A cached parity word that records all future off-diagonal quadratic phase increments simultaneously, allowing one-time precomputation instead of per-element updates.
If this is right
- Materialization of any stabilizer state vector from a standard check-matrix description runs in O(2^n) time.
- Expansion of any Clifford tableau into its full dense matrix representation runs in O(2^n) time.
- The asymptotic gap between compact and dense forms for all stabilizer and Clifford objects is closed.
Where Pith is reading between the lines
- Hybrid algorithms that alternate between compact and dense representations can now switch at linear cost in the dense size.
- Classical simulators of Clifford circuits gain a constant-factor improvement when they must occasionally produce explicit vectors.
- The parity-cache idea may extend to other phase-structured states such as certain graph states or CSS codes.
Load-bearing premise
The quadratic phase structure permits all off-diagonal increments to be tracked together by one parity word with no hidden per-step costs.
What would settle it
Run the algorithm on random n-qubit stabilizer states for n from 5 to 20 and measure whether wall-clock time scales linearly with 2^n rather than with any extra n^k factor.
read the original abstract
Stabilizer states admit compact classical descriptions, but many downstream tasks still require their full amplitude vectors. Since the output itself has size $2^n$, the main algorithmic question is whether one can materialize an $n$-qubit stabilizer state vector in optimal $O(2^n)$ time, rather than paying an additional polynomial overhead. We answer this question in the affirmative. Starting from the standard quadratic-form representation of stabilizer states, we give an algorithm that runs in $O(2^n)$ time and $O(2^n)$ space. The idea is to maintain a cached parity word that records all future off-diagonal quadratic phase increments simultaneously. As consequences, we obtain an optimal procedure for materializing a stabilizer state vector from a standard check-matrix description, and an optimal algorithm for expanding a Clifford tableau into its full dense matrix. These results close the asymptotic gap for dense stabilizer and Clifford materialization.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that stabilizer states given in quadratic-form (or check-matrix) representation can be materialized into their full 2^n-dimensional amplitude vector in optimal O(2^n) time and space by maintaining a single cached parity word that simultaneously tracks all future off-diagonal quadratic phase increments; the same technique yields an optimal algorithm for expanding a Clifford tableau into its dense matrix representation. These results are said to close the asymptotic gap between compact descriptions and dense output for stabilizer states and Clifford gates.
Significance. If the O(2^n) bound is achieved without hidden polynomial factors, the work would be significant for quantum simulation and Clifford-circuit analysis, as it supplies the first explicit optimal-time procedures for these standard materialization tasks. The cached-parity-word construction is a clean algebraic device that directly exploits the quadratic-form structure over GF(2) and avoids the usual n-factor overheads.
major comments (1)
- [Abstract (and the algorithm description in the main text)] The central optimality claim rests on the cached parity word permitting constant-time updates while traversing the 2^n states. The abstract states that the word 'records all future off-diagonal quadratic phase increments simultaneously,' but provides no explicit accounting of the per-step bit operations required to maintain or apply it. If each update touches Θ(n) bits (as is common for n-bit parity registers), the total cost becomes Θ(n 2^n), contradicting the stated O(2^n) bound. A concrete complexity analysis or pseudocode for the parity-word maintenance is needed to substantiate the claim.
minor comments (1)
- [Abstract] The abstract would be strengthened by a one-sentence statement of the input representation (quadratic form vs. check matrix) and a brief indication of how the parity word is initialized.
Simulated Author's Rebuttal
We thank the referee for their positive evaluation of the significance of our results and for the constructive comment on the complexity analysis. We address the point below and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: [Abstract (and the algorithm description in the main text)] The central optimality claim rests on the cached parity word permitting constant-time updates while traversing the 2^n states. The abstract states that the word 'records all future off-diagonal quadratic phase increments simultaneously,' but provides no explicit accounting of the per-step bit operations required to maintain or apply it. If each update touches Θ(n) bits (as is common for n-bit parity registers), the total cost becomes Θ(n 2^n), contradicting the stated O(2^n) bound. A concrete complexity analysis or pseudocode for the parity-word maintenance is needed to substantiate the claim.
Authors: We thank the referee for highlighting the need for an explicit accounting. Our algorithm assumes the standard word-RAM model with word size Θ(n) bits, in which bitwise operations (XOR, AND, shifts) on the full parity word execute in O(1) time. The n-qubit quadratic form is encoded such that the cached parity word aggregates all relevant off-diagonal increments; the Gray-code traversal ensures only one basis bit flips per step, and the update consists of a constant number of word-parallel bitwise operations (specifically, XOR with a precomputed mask derived from the quadratic-form matrix row corresponding to the flipped bit). Thus each of the 2^n steps costs O(1) time with no hidden n-factor. We will add a dedicated subsection containing the pseudocode for the parity-word maintenance routine together with the explicit statement of the computational model. revision: yes
Circularity Check
No significant circularity; derivation is constructive from quadratic-form algebra
full rationale
The paper derives an O(2^n) materialization algorithm directly from the standard quadratic-form representation of stabilizer states by introducing a cached parity word to track off-diagonal phase increments. This is a self-contained algorithmic construction with no fitted parameters, no self-definitional reductions, and no load-bearing self-citations. The claimed complexity follows from the explicit maintenance of the parity word during enumeration, independent of any prior fitted quantities or external uniqueness theorems. The derivation chain does not reduce any prediction or result to its own inputs by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Stabilizer states admit a standard quadratic-form representation over GF(2) whose phase factors can be tracked via parity words.
Reference graph
Works this paper leans on
-
[1]
Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits.Physical Review A—Atomic, Molecular, and Optical Physics, 70(5):052328, 2004
work page 2004
-
[2]
Stim: a fast stabilizer circuit simulator.Quantum, 5:497, 2021
Craig Gidney. Stim: a fast stabilizer circuit simulator.Quantum, 5:497, 2021
work page 2021
-
[3]
Nadish de Silva, Wilfred Salmon, and Ming Yin. Fast algorithms for classical specifications of stabiliser states and Clifford gates.Quantum, 9:1586, 2025
work page 2025
-
[4]
Fast exhaustive search for polynomial systems inF2
Charles Bouillaguet, Hsieh-Chung Chen, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, Adi Shamir, and Bo-Yin Yang. Fast exhaustive search for polynomial systems inF2. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 203–218. Springer, 2010
work page 2010
-
[5]
Jeroen Dehaene and Bart De Moor. Clifford group, stabilizer states, and linear and quadratic operations over GF(2).Physical Review A, 68(4):042318, 2003. 16
work page 2003
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.