1
$\begingroup$

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 \}$?

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – JMark
    Commented May 30, 2023 at 23:46
  • $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Commented May 31, 2023 at 7:26
  • $\begingroup$ To conclude this entry, see [quantumcomputing.stackexchange.com/questions/28292/… $\endgroup$
    – JMark
    Commented May 31, 2023 at 10:54

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.