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:
| projection | Stabilizer | MixedStabilizer | Destabilizer | MixedDestabilizer |
|---|---|---|---|---|
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.
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).
Moreover, how a tableau is stored in memory can affect performance, as a row-major storage usually permits more efficient use of the CPU cache (for the particular algorithms we use).
Both of these parameters are benchmarked (testing the application of a Pauli operator, which is an $\mathcal{O}(n^2)$ operation; and testing the canonicalization of a Stabilizer, which is an $\mathcal{O}(n^3)$ operation). Row-major UInt64 is the best performing and it is used by default in this library.
- 1This can occur only if the state being projected is mixed. Both
StabilizerandDestabilizercan 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 usingMixedStabilizerandMixedDestabilizerbut should be avoided otherwise.project!works correctly or raises an explicit warning on all 4 data structures.