Check if a Pauli string belongs to a stabilizer tableau

Question

Given a Pauli string and a stabilizer tableau, how do I know that the Pauli string belongs to the tableau, i.e. can be written as a product of strings already in the tableau. Thanks.

Answer 1

To this end, the binary representation of stabilizers is useful. For $z_i,x_i\in\mathbb F_2$, let $Z(z_1,\dots,z_n):=Z^{z_1}\otimes\dots\otimes Z^{z_n}$ be a $Z$-type operator and define $X(x_1,\dots,x_n)$ similarly. Then, every generator of a stabilizer code is proportional to operator of the form $Z(z_1,\dots,z_n)X(x_1,\dots,x_n)$, and it is convenient to collect these binary numbers into a single vector, say $a=(z_1,\dots,z_n,x_1,\dots,x_n)\in\mathbb F_2^{2n}$.

Now suppose you have $k$ generators $g_1,\dots,g_k$, you get $k$ vectors $a_1,\dots,a_k$ in this way. If you want to know whether a Pauli operator $P$, here represented by $b\in\mathbb F_2^{2n}$ is in the stabilizer group or not, a necessary condition to check is whether $$ b = \sum_{i=1}^k \lambda_i a_i, $$ has a solution. You can do this efficiently with (binary) Gaussian elimination. This equation is nothing but a reformulation of your question whether the Pauli operator $P$ can be written as a product of generators $g_1,\dots,g_k$. In fact, having found a solution to the above equation, you know that $$ P = \pm \prod_{i=1}^k g_i^{\lambda_i}. $$

As you might have noticed, there's still some ambiguity in the phase. This is because we haven't considered the phases of the generators yet. To finally decide whether $P$ or $-P$ is in the stabilizer group, you have to evaluate the phase that appears when multiplying the generators and compare it with the one of $P$. Unfortunately, evaluating this phase is not super straightforward, since on top of multiplying the phases from the generators, you get an additional contribution coming from the fact that sometimes you get an $i$ phase when multiplying Pauli operators, e.g. $ZX = i Y$.

Answer 2

A Pauli product $P$ is in the stabilizer group of a tableau $T$ if and only if $T^{-1}(P)$ is a stabilizer of the identity tableau (i.e. a positive-signed Pauli product containing no X or Y terms).

import stim

def is_stabilizer_of_tableau(
    pauli_product: stim.PauliString,
    tableau: stim.Tableau,
) -> bool:
    inv_tableau = tableau.inverse()
    p2 = inv_tableau(pauli_product)
    return p2.sign == +1 and "X" not in str(p2) and "Y" not in str(p2)

It takes $O(n^3)$ time to compute the inverse tableau (where $n$ is the number of qubits) and $O(np)$ time to apply it to the Pauli product (where $p$ is the number of non-identity Pauli terms). So if you need to do this a lot, you ideally would arrange to already have the inverse when needed. For example, because "is this measurement a stabilizer of the tableau" is a common question to encounter during circuit simulation, it's better for a simulator to track the inverse tableau instead of the normal tableau.

---

Explanation.

A tableau $T$ corresponds to a Clifford operation $C$. Applying a tableau $T$ to a Pauli product $P$ gives you $P_2 = T(P) = C P C^{-1}$. It gives you the result of conjugating the Pauli product by the Clifford operation, which will also be a Pauli product. It tells you the Pauli product $P_2$ after $C$ that is equivalent to $P$ before $C$.

Applying the inverse tableau means that you have a Pauli product after the Tableau's Clifford and are asking for the equivalent Pauli product before that Clifford. Conceptually, this is like moving your question about stabilizers from the middle of a quantum circuit to the very beginning, right after all the qubits were initialized into the $|0\rangle$ state. Which makes answering the is-it-a-stabilizer question easy, because the $|0\rangle^{\otimes n}$ state is very simple.

Sanity checking:

tableau = stim.Tableau.from_conjugated_generators(
    xs=[
        stim.PauliString("+___Z"),
        stim.PauliString("+ZX_Z"),
        stim.PauliString("+__X_"),
        stim.PauliString("+Z__Z"),
    ],
    zs=[
        # These are the stabilizer generators.
        stim.PauliString("+XXXX"),
        stim.PauliString("+ZZ__"),
        stim.PauliString("+__ZZ"),
        stim.PauliString("+YY__"),
    ],
)
assert is_stabilizer_of_tableau(stim.PauliString("+XXXX"), tableau)
assert not is_stabilizer_of_tableau(stim.PauliString("-XXXX"), tableau)
assert is_stabilizer_of_tableau(stim.PauliString("-YYXX"), tableau)
assert not is_stabilizer_of_tableau(stim.PauliString("ZIII"), tableau)
assert not is_stabilizer_of_tableau(stim.PauliString("IXXI"), tableau)
assert is_stabilizer_of_tableau(stim.PauliString("+YYYY"), tableau)
assert not is_stabilizer_of_tableau(stim.PauliString("-__YY"), tableau)