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

Question

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<n$. 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.

Answer 1

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<n$. 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.

Answer 2

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.