# Gottesman-Knill theorem -- last measurement step

In the Gottesman-Knill theorem, the stabilizer set is updated after each Clifford gate. These steps are quite simple. At the end, the measurement is simulated. In some on-line explanations, I have seen seen that the stabilizers could be diagonalized to obtain a set of stabilizers of the form $$I_1 \otimes \cdots I_{i-1} \otimes X_i / Z_i \otimes I_{i+1} \otimes \cdots I_n$$, for $$1 \leq i \leq n$$. I do not see how to achieve this last step for a stabilizer set such as $$\{ I \otimes I \otimes X \otimes X, I \otimes I \otimes Z \otimes Z, X \otimes X \otimes I \otimes I, Z \otimes Z \otimes I \otimes I \}$$?

• Please link to the "on-line explanations" you're referring to. Commented May 29, 2023 at 18:42

Let's assume that you're making a $$Z$$ measurement on qubit $$i$$ (if you're doing more than one measurement, you can just go through this process one measurement at a time). Let the set of stabilizer generators be $$\{g_j\}$$. Then, after the measurement, you know that you get an answer $$\pm 1$$. This means that your system is in a $$+1$$ eigenstate of the stabilizer $$K_i=\pm I\otimes I\otimes\ldots \otimes I\otimes Z\otimes I\otimes\ldots \otimes I$$. So, you know that that stabilizer must be in your list of stabilizers. The question is how to insert it. There are three different cases:

1. there exists at least one $$g_j$$ such that $$\{g_j,K\}=0$$ (i.e.\ they anti-commute). Note that if there's more than one that anti-commutes, we can rewrite the set of generators so that exactly one anti-commutes (if you have $$g_1,g_2,g_3$$, replace them with $$g_1,g_1g_2,g_1g_3$$). In the act of the measurement the anti-commuting term $$g$$ will be replaced by $$K$$ (with the $$\pm$$ options occurring with 50:50 probability).

2. if all the stabilizer generators commute with $$K$$, then there might exist a product of generators that is equal to $$K$$. If so, then when you find this, it directly tells you which $$\pm$$ version you have, and you are guaranteed to get that measurement outcome. Nothing in the state changes. To find this out, it's a simple linear calculation: can you find an $$x\in\{0,1\}^{k}$$ such that $$S^Tx=e \text{ mod }2$$ where $$S$$ is the $$k\times 2n$$ binary matrix describing the generators, and $$e\in\{0,1\}^{2n}$$ is the binary vector describing $$K$$.

3. if all the stabilizer generators commute with $$K$$, but there's no product of generators that creates $$K$$, then we know that the number of generators, $$k. At that point, you can just insert $$K$$ into your set of generators.

Let's take the example you gave. I'll write the stabilizers as $$X_1X_2,X_3X_4,Z_1Z_2,Z_3Z_4$$. I'll measure qubit 1 in the $$Z$$ basis. $$Z_1$$ anti-commutes with exactly 1 term, $$X_1X_2$$, so my outcome will be the stabilizers $$\pm Z_1,X_3X_4,Z_1Z_2,Z_3Z_4$$. Note that I can also rewrite this as $$\pm Z_1,X_3X_4,\pm Z_2,Z_3Z_4$$, so that if I measure the second qubit in $$Z$$, I see that I'll get the same answer as the first measurement (that's an example of case 2).

• One detail, in Point 2, $S$ is a n x 2n binary matrix, x is a 2n x 1 binary vector, the result is a n x 1 binary vector. Not a 2n x 1 vector representing the solution. By I see the point, find the subset of generators which product gives the operator $K$. Do we have to do the measurements one after the other? Or is it possible to do three measurements at the same time? In this case, if the global phase is +1, there are four possible outcomes to verify-less efficient. My goal is to understand this last step using the Gaussian elimination and not to use the more efficient Aaronson-Gottesman sln. Commented May 30, 2023 at 23:46
• I'm sure you could do the measurements all in one go, but the one-at-a-time approach manages things quite nicely. One option to do it more efficiently is to think about the observables you're measuring, $Z_i$. Can you rewrite, via linear combinations, some of them to be equal to existing stabilizers? Roughly speaking, what you're trying to do is take the matrix $S$ and, via row reduction, convert the $X$-type and $Z$-type operators into identity blocks for the qubits you're measuring. That shows you which are (anti)commuting. Commented May 31, 2023 at 7:26
• To conclude this entry, see [quantumcomputing.stackexchange.com/questions/28292/… Commented May 31, 2023 at 10:54