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.


2 Answers 2


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.


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


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.

  • $\begingroup$ 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). $\endgroup$ Commented Feb 1, 2022 at 13:03
  • $\begingroup$ (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. $\endgroup$ Commented Feb 1, 2022 at 13:05
  • $\begingroup$ 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!! $\endgroup$ Commented Feb 1, 2022 at 13:11
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 1, 2022 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.

  • $\begingroup$ 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). $\endgroup$ Commented Feb 2, 2022 at 11:09
  • $\begingroup$ @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? $\endgroup$
    – unknown
    Commented May 25, 2022 at 17:05
  • $\begingroup$ @unknown you give s a random sign to make the measurement random. $\endgroup$ Commented May 25, 2022 at 19:20
  • $\begingroup$ @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? $\endgroup$
    – unknown
    Commented May 25, 2022 at 20:29
  • $\begingroup$ @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. $\endgroup$ Commented May 26, 2022 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.