How to get the stabilizer group for a given state?

Question

Let's say we have the GHZ state with 3 qubits:

$$ |\mathrm{GHZ}\rangle = \dfrac{1}{\sqrt{2}}\Big(|000\rangle + |111\rangle \Big)$$

I want to find the stabilizer group of this state, that is, the $M_i$ operators such that $M_i|\mathrm{GHZ}\rangle = |\mathrm{GHZ}\rangle$ with $M_i \in P_3$, being $P_3$ the Pauli group for $3$ qubits.

Of course, in this case, by testing with brute force we can find: $$\begin{align} M_1 &= XXX\\ M_2 &= ZZ1\\ M_3 &= Z1Z\\ M_4 &= 1ZZ \end{align} $$

But I do have a couple of questions:

1. Shouldn't I get $3$ stabilizers instead of $4$? because as I understand it, the number of stabilizers is given by $n-k$ where $n$ is the number of physical bits and $k$ is the number of logical or information bits, and in our case we have $n=3,\ k=0$.
2. There is no more rigorous method to find the stabilizers, without having to try all the combinations? perhaps through the Hamming matrix as in the classical codes?

Answer 1

You need to watch out when you say 'stabilizer' or 'stabilizers' because there is a little bit of ambiguity in that terminology$^{1}$.

The stabilizer $\mathcal{S}$ of a state $|\psi \rangle$ is the group of $n$-qubit Paulis of which $|\psi \rangle$ is a $+1$ eigenstate. That is, $|\psi \rangle$ is the shared $+1$ eigenspace of all these operators. We can generalize this by having a stabilizer code where the shared eigenspace is of dimension $2^{n-l}$ instead of $1$, because we now take only $l$ Paulis for an $n$-qubit system. We then get $k = n-l$ logical qubits.

The number of elements in any stabilizer is $2^{l}$, because if $P_{1}, P_{2} \in \mathcal{S}$, then evidently $P_{12} = P_{1}P_{2} \in \mathcal{S}$ as well. That is, the elements of $\mathcal{S}$ form a group (hence why we refer to it as the stabilizer group). Our $l$ Paulis are generators for the group; but there are $2^{l}$ elements in the group, because any multiplication of our generators will give an element of the stabilizer as well.

Shouldn't I get 3 stabilizers instead of 4? because as I understand it, the number of stabilizers is given by n−k where n is the number of physical bits and k is the number of logical or information bits, and in our case we have n=3, k=0

You should get $3$ generators for the state, since the number of generators is $l = n-k = (3 - 0)$. The four Paulis that you have listed are not mutual exclusive generators, because $M_4 = M_{2}M_{3}$ (or any other permutation). Hence, to generate this specific stabilizer we only need $M_{1}$ and any two of the set $M_{2},M_{3},M_{4}$.

To illustrate, consider the operator $M_{5} = M_{1}M_{4} = (XXX)(IZZ) = (XYY)$ (up to a phase). Evidently, $M_{5}|\psi\rangle = XYY|\psi\rangle = (+1)|\psi\rangle$, so $M_{5}$ is also an element of the stabilizer of $|\psi\rangle$. However, we can 'generate' $M_{5}$ with $M_{1}\& M_{4}$ (and therefore with $M_{1}, M_{2} \& M_{3}$ as well), so we don't need to keep track of $M_{5}$.

There is no more rigorous method to find the stabilizers, without having to try all the combinations? perhaps through the Hamming matrix as in the classical codes?

This is actually pretty hard to do in general. However, it is also not needed very often: normally we define a stabilizer and then 'just' find the corresponding state or codespace. Also, please note that only a subset of all valid quantum states can have a stabilizer comprised of Pauli matrices.

1. In fact,Daniel Gottesman, who developed the stabilizer formalism, said (and I paraphrase): "I can't stop you from calling them stabilizers, but I do not condone it." :)

Answer 2

If you know the quantum circuit for generating a particular state, starting from the all-zero state, it's easy enough to work out the stabilizers. You just start with stabilizers $K=III\ldots IZII\ldots I$, where you have one with a $Z$ on each qubit (i.e. the stabilizers of the all-zero state), and you just update them to $UKU^\dagger$. Particularly if you're using a circuit comprised of Clifford gates, there are good methods (basically, see Gottesman-Knill theorem) for updating the stabilizers from one gate to the next. Of course, for a generic $U$, there's no guarantee that the output will be a nice tensor product of Paulis.

Answer 3

The paper "Fast algorithms for classical specifications of stabiliser states and Clifford gates" covers various algorithms for tasks like this. In your case you would start at 3.1 [S_V] → [S_Q]: Amplitudes to a quadratic form triple.

Stim has a method stim.Tableau.from_state_vector, which also solves the problem (a tableau is just a list of stabilizers and destabilizers; you want the stabilizers). The way it works is by basically trying to use simple Clifford gates to iteratively compress the state. It uses X gates to get a non-zero amplitude at $|0\rangle$, and then CNOT gates to get a non-zero amplitude at $|1\rangle$, and then chooses a single qubit Clifford gate that will destructively interfere the amplitude at $|1\rangle$, and keeps doing that until only $|0\rangle$ remains. It then streams the gates it recorded doing through its tableau simulator to get their tableau.

Both those references only work when the state is a stabilizer state. They are capable of checking that as part of running. For more general states I don't know fast algorithms for finding the Pauli product stabilizers.