# How to find the stabilizer generators for a post-measurement state?

My question is closely related to this one.

## A bit of vocabulary and a reminder of basic properties:

I consider the total Hilbert space of the problem has dimension $$2^n$$.

I call a "well defined family of generators" a family of $$n$$-Pauli matrices $$\{h_i\}_{i=i}^p$$ such that all the $$h_i$$ are commuting between themselves, no element can be written as a product of the others, and any product of elements in this family cannot be equal to $$-I$$. This family of generator allows me to define a stabilizer group $$S_h=\langle h_1,...,h_p\rangle$$. A stabilizer group defines a subspace of the total Hilbert space that is of dimension $$2^{n-p}$$. It corresponds to the common eigenspace of eigenvalue $$+1$$ (for instance) of all the elements in the stabilizer.

## My question:

I consider that at time $$t=0$$, I have a state $$|\psi\rangle$$ that is somewhere in the subspace stabilized by the group $$S_g=\langle g_1,...,g_k \rangle$$, where the family $$\{g_i\}$$ is a well defined family of generators.

Now, at time $$t=t_1$$, I measure my system with the family $$\{\widetilde{g}_1,...,\widetilde{g}_p\}$$, $$p. I assume that this family is a well defined family of generators.

Is there a systematic way to deduce the group $$S'$$ which will stabilize the final quantum state. What we know is that it will be inside the space stabilized by the group $$S_{\widetilde{g}}=\langle \widetilde{g}_1,...,\widetilde{g}_p \rangle$$, but we can be more precise than that. For instance if the subspace at time $$t=0$$ described a quantum state, we will still be in some quantum state at $$t=t_1$$. Hence, the quantum state will be stabilized by a group composed of $$n$$ elements.

The thing that is disturbing me occurs when an element $$g_i$$ anti-commutes with a $$\widetilde{g}_j$$. We could naïvely believe that $$g_i$$ cannot be in $$S'$$ and we could completely discard it. But it could occur that $$g_i g_l$$ commutes with all the family $$\{\widetilde{g}_j\}$$. Hence, while $$g_i$$ is discarded we should check that there doesn't exist any product involving $$g_i$$ with other elements of $$S_g$$ that would commute with all the family $$\{\widetilde{g}_j\}$$ (and hence be a potential candidate to belong in $$S'$$). Because of this fact it makes me hard to find an easy way to find $$S'$$. Everything I have in mind would be very computational intensive (and not intuitive).

My question in summary: Is there an intuitive reasoning (i.e that doesn't require a computer doing linear algebra) to find $$S'$$. If there is no such intuitive reasoning, what is the simplest algorithm that allows to solve this problem?

## One simple example illustrating the problem with $$n=3$$

Let's assume that at $$t=0$$ my state is $$|\psi\rangle=|000\rangle$$. It is stabilized by $$S_g=\langle Z_1 Z_2, Z_2 Z_3, Z_1 Z_2 Z_3 \rangle$$.

At time $$t=t_1$$, I measure $$X_2$$ (and I find the outcome $$+1$$). The state then becomes:

$$|\psi \rangle \to \frac{1+X_2}{2} |\psi \rangle = |0 \rangle |+\rangle |0\rangle$$

It is easy to verify that it is stabilized by $$S'=\langle Z_1 Z_3, X_2, Z_1 \rangle$$. (To make a link with my previous section, it is also trivially consistent with the fact it is necessarily in the space stabilized by $$S_{\widetilde{g}} = \langle X_2 \rangle$$).

However, $$X_2$$ anti-commutes with $$Z_2 Z_3$$ and $$Z_1 Z_2 Z_3$$. The naive reasoning would then "forget" about $$Z_2 Z_3$$ and $$Z_1 Z_2 Z_3$$ while actually $$X_2$$ commutes with their product which is $$Z_1$$. This is those kind of events that makes the situation much more complicated for me.

Yes, there exists a relatively straightforward algorithm for finding the stabilizer generators of the post-measurement state.

TL;DR: Instead of "forgetting" about the stabilizer generators that anti-commute with the operator being measured $$\tilde{g}$$, we use one of the anti-commuting operators to turn all the other anti-commuting operators into operators that commute with $$\tilde{g}$$. Finally, we "forget" only this one selected anti-commuting generator by replacing it with $$\tilde{g}$$ or its negative depending on the measurement outcome.

## Background

First, notice that since $$\tilde{g_i}$$ commute pairwise, the order of the measurements does not matter and we can update the set of stabilizer generators one measurement at a time. Therefore, we focus on how to update the stabilizer generators following a measurement of a single operator $$\tilde{g}$$.

There are two cases. Either $$\tilde{g}$$ commutes with $$g_i$$ for all $$i=1,\dots,p$$ or there exists one or more $$g_i$$ that anti-commute with $$\tilde{g}$$. In the first case, the post-measurement state $$|\psi'\rangle$$ is stabilized by all $$g_i$$ and by $$(-1)^m\tilde{g}$$ where $$m\in\{0,1\}$$ is the measurement outcome. Therefore, $$S'=\langle g_1,\dots,g_p,(-1)^m\tilde{g}\rangle$$. Note that $$(-1)^m\tilde{g}$$ may or may not be independent of the generators $$g_1,\dots,g_p$$.

If $$\tilde{g}$$ anti-commutes with one or more of the generators of $$S$$, then $$S$$ is generated by some operators $$\bar{g}_1,\bar{g}_2,\dots,\bar{g}_p$$ such that $$\tilde{g}$$ anti-commutes with $$\bar{g}_1$$ and commutes with all $$\bar{g}_i$$ for $$i=2,\dots,p$$. We can construct such a generator list as follows. Assume w.l.o.g. that $$\tilde{g}$$ anti-commutes with $$g_1$$. Set $$\bar{g}_1:=g_1$$. For $$i=2,\dots,p$$ set $$\bar{g}_i:=g_i$$ if $$\tilde{g}$$ and $$g_i$$ commute and $$\bar{g}_i:=g_1g_i$$ otherwise. It is easy to see that $$\tilde{g}$$ anti-commutes with $$\bar{g}_1$$, commutes with all other generators $$\bar{g}_i$$ for $$i=2,\dots,p$$ and $$S=\langle\bar{g}_1,\bar{g}_2,\dots,\bar{g}_p\rangle$$.

## Procedure

Thus, we can compute a list of stabilizer generators of the post-measurement state as follows

1. Search in $$\{g_1,\dots,g_p\}$$ for an operator that anti-commutes with $$\tilde{g}$$. If one is found, let $$g_k$$ be that operator and go to $$3$$.
2. If $$\tilde{g}\in S$$ or $$-\tilde{g}\in S$$, return $$\{g_1,\dots,g_p\}$$. In this case the measurement outcome is deterministic. Otherwise, measure $$\tilde{g}$$, set $$m\in\{0,1\}$$ to the measurement outcome and return $$\{g_1,\dots,g_p,(-1)^m\tilde{g}\}$$.
3. Swap $$g_1$$ and $$g_k$$.
4. For $$i=2,\dots,p$$ check if $$g_i$$ anti-commutes with $$\tilde{g}$$. If it does, update $$g_i:=g_1g_i$$.
5. Finally, measure $$\tilde{g}$$, set $$m\in\{0,1\}$$ to the measurement outcome and return $$\{(-1)^m\tilde{g},g_2,\dots,g_p\}$$.

where in the last step we use three facts. First, $$g_1$$ does not stabilize the post-measurement state so we remove it from the generator list. Second, $$(-1)^m\tilde{g}$$ becomes a new stabilizer, so we add it to the list. Third, since $$\tilde{g}$$ and $$g_i$$ for $$i\in\{2,\dots,p\}$$ commute, the post-measurement state is stabilized by $$g_i$$.

Note that the list of stabilizer generators may only grow if $$p. This makes sense since the largest stabilizer group on $$n$$ qubits has $$n$$ generators. In this case $$p=n$$ and the input state is a stabilizer state. This allows us to avoid checking whether $$\tilde{g}$$ or $$-\tilde{g}$$ belong to the stabilizer in the second step above, because we know that one of them does.

• Thank you a lot for your answer it is a very nice one. I think I understood everything. I would just have minor comments/questions. Do you agree with me with the following points. (i) If my measurement commutes with all the elements in $S$, the space stabilized either had its dimension divided by two, either keeps having the same dimension (this is straightforward to see). (ii) If my measurement anti-commutes with at least one element in $S$ the space stabilized necessarily has the same dimension (I think I managed to prove it but I need to double check it, it seems way less obvious). Feb 1 at 13:03
• (iii) In the procedure, here you explained what is the new stabilizer space when we are measuring a single Pauli $\widetilde{g}_1$. The stabilized space went from $S \to S_1$. If I have $k$ observable that I measure I simply re-iterate the process: I would do the same reasoning starting with the new $S_1$ but now measuring the new $\widetilde{g}_2$. This is also relatively "obvious" but I wanted to be sure. Feb 1 at 13:05
• For (ii) what I found not so "quick" to show (but I probably missed an obvious point) is that $\{(-1)^m \widetilde{g},g_2,...,g_p\}$ is a list of independent generators. Using a bit of algebra it is possible to show it but there are many sub-cases to check. However you may probably have a smart reason why the list is necessarily composed of independent generators which would avoid doing boring algebra. If so I would be very interested to hear about!! Feb 1 at 13:11
• Thanks! Re (i): Yes, that's right. These two cases correspond to the two cases in step two of the procedure where the number of generators increases by one or stays the same. Re (ii): Yes, that's right also. This case corresponds to step five in the procedure where the number of generators stays the same. Re independence: if $(-1)^m\tilde{g}$ anti-commutes with an operator in $S$ then $(-1)^m\tilde{g}\notin \langle g_1,\dots,g_p\rangle=S$, so $(-1)^m\tilde{g}\notin\langle g_2,\dots,g_p\rangle\subset S$. IOW, $(-1)^m\tilde{g}$ is independent of $\{g_2,\dots,g_p\}$. Re (iii): Yes, exactly. Feb 1 at 22:35

Let $$n$$ be the observable you measured, and let $$S$$ be the set of stabilizer generators for the state before the measurement.

Some of the old stabilizers generators anti-commute with the new stabilizer generator $$n$$. Call these the "at risk" stabilizer generators $$R$$.

$$R = \{r | r \in S \land \text{anticommutes}(n, r)\}$$

Pick one element $$s$$ from $$R$$. This is the stabilizer generator you are going to sacrifice to save the others. Multiply $$s$$ into every other element of $$R$$ to get the saved stabilizer generators $$R^\prime$$. Multiplying works because, for Pauli products, anticommute * anticommute = commute.

$$R^\prime = \{r \cdot s | r \in R \land r \neq s\}$$

The new stabilizer generator set is the stabilizer generators that commuted with $$n$$, and also the saved stabilizer generators, and also $$n$$:

$$T = \{\text{commutes}(n, r) | r \in S\}$$

$$S^\prime = T \cup R^\prime \cup \{n\}$$

Note that $$|S^\prime| = |S|$$. We sacrificed one stabilizer generator $$s$$ to introduce one stabilizer generator $$n$$.

You can see this logic playing out in Stim's source code, although framed in terms of "appending operations at the start of time" instead of in terms of multiplying a sacrifice into the others.

• Thank you for your answer. I need a little bit of time to fully understand it but I think I get your overall point (which seems similar in its philosophy to the other answer). Feb 2 at 11:09
• @Craig Gidney : what about the results of the measurement? The accepted answer keeps track of it; your approach doesn't...what's the logic behind ignoring it? May 25 at 17:05
• @unknown you give s a random sign to make the measurement random. May 25 at 19:20
• @CraigGidney but the measurement can sometimes be deterministic (step 2 in procedure)...I guess the main point is do we need to keep track of the sign? is it relevant? May 25 at 20:29
• @unknown It's never deterministic if it anticommutes with the stabilizer generators. If it does commute then you need to build it out of the other generators. May 26 at 0:30