Data Structures Options

Choosing Appropriate Tableau Data Structure

There are four different data structures used to represent stabilizer states. If you will never need projective measurements you probably would want to use Stabilizer. If you require projective measurements, but only on pure states, Destabilizer should be the appropriate data structure. If mixed stabilizer states are involved, MixedStabilizer would be necessary.

Stabilizer is simply a list of Pauli operators in a tableau form. As a data structure it does not enforce the requirements for a pure stabilizer state (the rows of the tableau do not necessarily commute, nor are they forced to be Hermitian; the tableau might be underdetermined, redundant, or contradictory). It is up to the user to ensure that the initial values in the tableau are meaningful and consistent.

canonicalize!, project!, and generate! can accept an under determined (mixed state) Stabilizer instance and operate correctly. canonicalize! can also accept a redundant Stabilizer (i.e. not all rows are independent), leaving as many identity rows at the bottom of the canonicalized tableau as the number of redundant stabilizers in the initial tableau.

canonicalize! takes $\mathcal{O}(n^3)$ steps. generate! expects a canonicalized input and then takes $\mathcal{O}(n^2)$ steps. project! takes $\mathcal{O}(n^3)$ for projecting on commuting operators due to the need to call canonicalize! and generate!. If the projections is on an anticommuting operator (or if keep_result=false) then it takes $\mathcal{O}(n^2)$ steps.

MixedStabilizer provides explicit tracking of the rank of the mixed state and works properly when the projection is on a commuting operator not in the stabilizer (see table below for details). Otherwise it has the same performance as Stabilizer.

The canonicalization can be made unnecessary if we track the destabilizer generators. There are two data structures capable of that.

Destabilizer stores both the destabilizer and stabilizer states. project! called on it never requires a stabilizer canonicalization, hence it runs in $\mathcal{O}(n^2)$. However, project! will raise an exception if you try to project on a commuting state that is not in the stabilizer as that would be an expensive $\mathcal{O}(n^3)$ operation.

MixedDestabilizer tracks both the destabilizer operators and the logical operators in addition to the stabilizer generators. It does not require canonicalization for measurements and its project! operations always takes $\mathcal{O}(n^2)$.

For the operation _, anticom_index, result = project!(...) we have the following behavior:

Notice the results when the projection operator commutes with the state but is not generated by the stabilizers of the state (the last row of the table). In that case we have _, anticom_index, result = project!(...) where both anticom_index==rank and result===nothing, with rank being the new rank after projection, one more than the number of rows in the tableau before the measurement.

Non-Clifford State Representations

For circuits containing non-Clifford gates, two state types are available:

PureGeneralizedStabilizer represents a pure state as a superposition (with arbitrary amplitudes) of stabilizer states. It supports the non-Clifford gates sT and sCCZ. Use directly with apply! and mctrajectory! as usual, but be aware that it has limited support for measurements. Use it with emtrajectories to sample Z-basis measurement outcomes at the end of a circuit. This is the right choice when you have a unitary circuit (no mid-circuit measurements) and only need measurement statistics at the end.

GeneralizedStabilizer represents a mixed state as a weighted sum ∑ ϕᵢⱼ Pᵢ ρ Pⱼ†, i.e. a weighted sum of "basis" density matrices, each of which is itself represented as a (projector on) stabilizer state. It supports arbitrary (non-unitary) Pauli channels such as PauliChannel and UnitaryPauliChannel, applied via apply!. Use it with mctrajectory!. Can be used with expect as well. Pauli measurements on arbitrary (non-unitary) Pauli channels are also supported via projectrand! which performs a randomized projection of the state represented by the GeneralizedStabilizer, based on the measurement of a PauliOperator.

Bit Packing in Integers and Array Order

We do not use boolean arrays to store information about the qubits as this would be wasteful (7 out of 8 bits in the boolean would be unused). Instead, we use all 8 qubits in a byte and perform bitwise logical operations as necessary. Implementation details of the object in RAM can matter for performance. The library permits any of the standard UInt types to be used for packing the bits, and larger UInt types (like UInt64) are usually faster as they permit working on 64 qubits at a time (instead of 1 if we used a boolean, or 8 if we used a byte).

Memory Layout: fastrow vs fastcolumn

How a tableau is stored in memory significantly affects performance, as different memory layouts provide better cache locality for different operations.

Default: fastrow Layout

The fastrow layout is the default for Stabilizer, Destabilizer, MixedStabilizer, and MixedDestabilizer. In this layout, each Pauli string (row of the tableau) is stored contiguously in memory. This corresponds to column-major storage of the underlying xzs matrix.

This layout is optimized for:

• Canonicalization operations (canonicalize!) - $\mathcal{O}(n^3)$ operations performing row operations
• Projective measurements (project!) - which frequently iterate over rows
• Row operations like mul_left!
• Measuring large Pauli operators
• Applying large dense n-qubit Clifford operations

Alternative: fastcolumn Layout

The fastcolumn layout is the default for PauliFrame. In this layout, the bits of a given qubit (tableau columns) are stored (mostly) contiguously in memory. This corresponds to row-major storage of the underlying xzs matrix.

This layout is optimized for:

• Applying sparse gates like apply!(s, sCNOT(i,j)) - operations that only touch a few qubits
• Single-qubit and two-qubit gate applications
• Operations where column locality matters more than row locality

Converting Between Layouts

The functions fastrow and fastcolumn can be used to convert between memory layouts without changing the logical content of the tableau:

s = random_stabilizer(1000)          # Uses default fastrow layout
s_col = fastcolumn(copy(s))          # Convert to fastcolumn layout
s_row = fastrow(copy(s_col))         # Convert back to fastrow layout

pf = PauliFrame(100, 50, 10)         # Uses default fastcolumn layout  
pf_row = fastrow(copy(pf))           # Convert to fastrow layout

These functions work on all stabilizer data structures: Stabilizer, Destabilizer, MixedStabilizer, MixedDestabilizer, and PauliFrame.

Technical Details: Indexing Convention

Important: Regardless of the memory layout (fastrow or fastcolumn), the indexing convention for the xzs matrix is always xzs[tableau_column_index, tableau_row_index].

• The X component of qubit i in stabilizer j is at xzs[i_big, j]
• The Z component is at xzs[i_big + end÷2, j]

where i_big accounts for bit packing (multiple qubits packed into each packed integer).

What changes between fastrow and fastcolumn is the underlying storage order of the matrix:

• fastrow: column-major Julia array → bits of a stabilizer row are contiguous in memory
• fastcolumn: row-major Julia array (via transpose trick) → bits of a qubit column are contiguous in memory

The performance difference becomes apparent when examining different operation types:

julia> s_row = fastrow(random_stabilizer(1000));

julia> s_col = fastcolumn(random_stabilizer(1000));

julia> @time canonicalize!(copy(s_row));
  0.012 seconds

julia> @time canonicalize!(copy(s_col));
  0.033 seconds

julia> @time apply!(copy(s_row), sCNOT(1, 2));
  0.000028 seconds

julia> @time apply!(copy(s_col), sCNOT(1, 2));
  0.000019 seconds

The fastrow layout excels at canonicalization and other row-focused operations, while fastcolumn is faster for sparse single-gate applications on specific qubits. In most practical scenarios, the default fastrow layout is optimal for Stabilizer types, while fastcolumn is optimal for PauliFrame simulations.