# Data Structures Options

## [Choosing Appropriate Tableau Data Structure](@id Choosing-Appropriate-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`](@ref). If you require projective measurements, but only on pure
states, [`Destabilizer`](@ref) should be the appropriate data structure. If
mixed stabilizer states are involved, [`MixedStabilizer`](@ref) would be
necessary.

[`Stabilizer`](@ref) 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!`](@ref), [`project!`](@ref), and [`generate!`](@ref) 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`](@ref) 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`](@ref) 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`](@ref) 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:

| projection | [`Stabilizer`](@ref) | [`MixedStabilizer`](@ref) | [`Destabilizer`](@ref) | [`MixedDestabilizer`](@ref) |
|---|---|---|---|---|
| on anticommuting operator `anticom_index>0` `result===nothing`| correct result in ``\mathcal{O}(n^2)`` steps | same as `Stabilizer` | same as `Stabilizer` | same as `Stabilizer` |
| on commuting operator in the stabilizer `anticom_index==0` `result!==nothing`| ``\mathcal{O}(n^3)``; or ``\mathcal{O}(n^2)`` if `keep_result=false` | ``\mathcal{O}(n^3)`` | ``\mathcal{O}(n^2)`` if the state is pure, throws exception otherwise | ``\mathcal{O}(n^2)`` |
| on commuting operator out of the stabilizer[^1]  `anticom_index==rank` `result===nothing`| ``\mathcal{O}(n^3)``, but the user needs to manually include the new operator to the stabilizer; or ``\mathcal{O}(n^2)`` if `keep_result=false` but then result indistinguishable from cell above and `anticom_index==0` | ``\mathcal{O}(n^3)`` and rank goes up by one | not applicable if the state is pure, throws exception otherwise | ``\mathcal{O}(n^2)`` and rank goes up by one |

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. 

[^1]:

    This can occur only if the state being projected is mixed. Both `Stabilizer`
    and `Destabilizer` can be used for mixed states by simply providing fewer
    stabilizer generators than qubits at initialization. This can be useful for
    low-level code that tries to avoid the extra memory cost of using
    `MixedStabilizer` and `MixedDestabilizer` but should be avoided otherwise.
    `project!` works correctly or raises an explicit warning on all 4 data
    structures.

## Non-Clifford State Representations

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

[`PureGeneralizedStabilizer`](@ref) represents a pure state as a superposition (with arbitrary amplitudes) of stabilizer states. It supports the non-Clifford gates [`sT`](@ref) and [`sCCZ`](@ref). Use directly with [`apply!`](@ref) and [`mctrajectory!`](@ref) as usual, but be aware that it has limited support for measurements. Use it with [`emtrajectories`](@ref) 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`](@ref) 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`](@ref) and [`UnitaryPauliChannel`](@ref), applied via [`apply!`](@ref). Use it with [`mctrajectory!`](@ref). Can be used with [`expect`](@ref) as well. Pauli measurements on arbitrary (non-unitary) Pauli channels are also supported via [`projectrand!`](@ref) which performs a randomized projection of the state represented by the [`GeneralizedStabilizer`](@ref), based on the measurement of a [PauliOperator](@ref).

## [Bit Packing in Integers and Array Order](@id 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`](@ref) layout is the default** for [`Stabilizer`](@ref), [`Destabilizer`](@ref), [`MixedStabilizer`](@ref), and [`MixedDestabilizer`](@ref). 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`](@ref) layout is the default** for [`PauliFrame`](@ref). 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`](@ref) and [`fastcolumn`](@ref) can be used to convert between memory layouts without changing the logical content of the tableau:

```julia
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`](@ref), [`Destabilizer`](@ref), [`MixedStabilizer`](@ref), [`MixedDestabilizer`](@ref), and [`PauliFrame`](@ref).

#### 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
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.
