# Is there a simple rule for the inverse of a Clifford circuit's stabilizer table?

In Improved Simulation of Stabilizer Circuits by Aaronson and Gottesman, it is explained how to compute a table describing which Pauli tensor products the X and Z observable of each qubit get mapped to as a Clifford circuit acts upon them.

Here as an example Clifford circuit:

0: -------@-----------X---
|           |
1: ---@---|---@---@---@---
|   |   |   |
2: ---|---|---@---|-------
|   |       |
3: ---@---@-------Y-------


And the table describing how it acts on the X and Z observables of each qubit:

       +---------------------+-
| 0    1    2    3    |
+------+---------------------+-
| 0    | XZ   X_   __   Z_   |
| 1    | ZZ   YZ   Z_   ZZ   |
| 2    | __   Z_   XZ   __   |
| 3    | Z_   X_   __   XZ   |
+------+---------------------+-
| sign |  ++   ++   ++   ++  |
+------+---------------------+-


Each column of the table describes how the circuit acts on the X observable (left half of column) and Z observable (right half of column) of each qubit. For example, the left side of column 3 is Z,Z,_,X meaning an X3 operation (Pauli X on qubit 3) at the right hand side of the circuit is equivalent to a Z1 * Z2 * X4 operation at the left hand side of the circuit. The 'sign' row indicates the sign of the product, which is important if you're going to simulate a measurement (it tells you whether or not to invert the result).

You can also compute the table for the inverse of a circuit. In the example case I've given, the inverse table is this:

       +---------------------+-
| 0    1    2    3    |
+------+---------------------+-
| 0    | XZ   Y_   __   Z_   |
| 1    | _Z   YZ   Z_   _Z   |
| 2    | __   Z_   XZ   __   |
| 3    | Z_   Y_   __   XZ   |
+------+---------------------+-
| sign |  ++   -+   ++   ++  |
+------+---------------------+-


The tables look almost the same if you transpose their rows and columns. But the entries aren't exactly identical. In addition to transposing, you have to encode the letters into bits (_=00, X=01, Z=10, Y=11) then swap the middle bits then decode. For example, ZZ encodes into 1010 which swaps into 1100 which decodes into Y_.

The question I have is: is there also a simple rule for the computing the inverse table's signs?

Currently I'm inverting these tables by decomposing them into circuits, inverting the circuits, then multiplying them back together. It's extremely inefficient compared to transpose+replace, but if I'm going to use transpose+replace I need a sign rule.

• To clarify the question: Let the Clifford circuit be $U$. Then reading the $j$'th column gives $U X_j U^\dagger$ and $U Z_j U^\dagger$ depending on left or right half used. And you want $U^\dagger X_j U$ and $U^\dagger Z_j U$ instead from this data. Sep 24 '18 at 5:44
• @AHusain Correct. Sep 24 '18 at 7:25
• To clarify the question: what do the @ s mean in your Clifford circuit? Sep 24 '18 at 7:53
• @JosuEtxezarretaMartinez Those are controls. When two are connected, it's a CZ gate. @ connected to an X is a controlled-X. @ connected to Y is a controlled-Y. Sep 24 '18 at 9:05

There is a very closely related representation of the tableau representation of Aaronson (and Gottesman), which works not only for qubits but for qudits of arbitrary finite dimension, which works particularly well for purely Clifford circuits (i.e. at most one terminal measurement).

In this alternative representation, one has tableaus describing how the single-qubit X and Z operators transform, with phase information, as in the usual representation. The columns describe multi-qubit Weyl operators specifically, which are a special subset of the Pauli operators. The advantage of doing so is that the tableau is not just an array of coefficients, but an actual linear operator on the vectors which represent Weyl operators and phases.

There is a small catch. For qubits, these vectors have coefficients which are integers modulo 4 (corresponding to a double cover of the non-trivial single-qubit Pauli operators by Weyl operators), rather than modulo 2. I think this is a small price to pay — though I might be slightly biased, as it's my own result [arXiv:1102.3354]. However, it does seem to be a somewhat 'naturally occurring' representation: Appleby developed the single-qubit or qudit special case somewhat earlier [arXiv:quant-ph/0412001] (something which I would really liked to have known before spending two years needlessly re-creating essentially the same conventions).

Using such a representation, by virtue of the fact that the 'tableau' $$M_C$$ of a Clifford circuit $$C$$ is now an actual matrix (and an invertible one) which transforms vectors, the tableau for the inverse circuit $$C^{\dagger}$$ is then the inverse $$M_C^{-1}$$ of the tableau. So, for this closely related representation at least, the rule for computing the tableau for the inverse circuit is easy.

• Could you link to slides or lecture notes describing Weyl operators? Sep 24 '18 at 21:04
• Is this in any way related to replacing the "Pauli basis" {I,X,Y,Z} with the "quaternion basis" {I, iX, iY, iZ} when tracking the product vectors? Sep 24 '18 at 21:12
• Presumably when talking about qubits, the original paper is this one Sep 25 '18 at 6:33
• I will try to find some good slides regarding Weyl operators (I don't have anything substantial about them myself). In the n-qubit case, they're the operators $W_{\mathbf a,\mathbf b}=i^{-(\mathbf a\codt\mathbf b)}Z_{\mathbf a}X_{\mathbf b}$ for two vectors $\mathbf a,\mathbf b\in\mathbb Z^n_4$. The motivation for this definition is summed up on p. 2 of my linked article, leading to Lemma 4. This allows one to reason about stabiliser groups using nothing more than addition mod 4 (and linear algebra mod 4 when doing Clifford circuits), subsuming the quadratic stuff mod 2 for the phases. Sep 25 '18 at 10:23
• @DaftWullie: No, [arXiv:quant-ph/9608006] is strictly different. They index powers of X and Z by mod 2 vectors (see the text preceding Eq.2), which is reflected in the additive group structure of GF(4). Their observations about symplectic transformations on p.8 thus apply to the Pauli group modulo phases. Appleby and I don't claim to be the first to have a fancy representation for the Pauli group on qubits: the point is that our representation more gracefully tracks phases. That is less important for discovering QECCs, but crucial to simulate states. Sep 25 '18 at 10:45

To draw out Aaronson and Gottesman's techniques a bit more explicitly: you can set up each stabilizer as a bit string of length $$2N$$ (for $$N$$ qubits). The first $$N$$ bits specify the locations of Z operators, and the second set of $$N$$ specify the locations of $$X$$ operators (so, $$X_1Z_2$$ for $$N=2$$ is 0110). For your circuit on four qubits, the transformation due to a Clifford circuit (up to some phases) would then be given by an $$8\times 8$$ matrix. We can think of this as a block matrix $$M=\left(\begin{array}{cc} A & B \\ C & D \end{array}\right),$$ where each of the blocks is $$N\times N$$. By the fact that the stabilizers commute, we know that $$\left(\begin{array}{cc} A & B \\ C & D \end{array}\right)\cdot\left(\begin{array}{cc} 0 & \mathbb{I} \\ \mathbb{I} & 0 \end{array}\right)\cdot \left(\begin{array}{cc} A & B \\ C & D \end{array}\right)^T\equiv 0\text{ mod }2$$ You want to find the inverse of $$M$$ modulo 2. Your claimed form of the inverse is then of the form (I think) $$\left(\begin{array}{cc} D^T & B^T \\ C^T & A^T \end{array}\right)$$ which is interestingly reminiscent of the inverse of a $$2\times 2$$ matrix (but that is not sufficient for block matrices. There is a block-wise inverse but that's not so helpful here, I think).

The mess, of course, comes from keeping track of the phases. I guess the signs will be related to a change in the number of Y operators in each stabilizer, but I haven't succeeded in a unified treatment. Niel's answer probably does a better job of taking care of it automatically.

I give working python code to compute the inverse of a Clifford tableau in this blog post.

The xz Pauli terms in the inverse table are computed by transposing the xz Pauli terms in the original table and then substituting:

II -> II
IX -> IX
IY -> XX
IZ -> XI
XI -> IZ
XX -> IY
XY -> XY
XZ -> XZ
YI -> ZZ
YX -> ZY
YY -> YY
YZ -> YZ
ZI -> ZI
ZX -> ZX
ZY -> YX
ZZ -> YI


The signs in the transposed table are computed in a naive way. Sending a generator through the inverse table and then through the original table should return it unchanged. If it instead gets negated, the sign of column corresponding to that generator in the inverse table is flipped. So...

for generator, output in list(columns.items()):
columns[generator] *= original_operation(output).coefficient


For example, this tableau:

      | 0  1  2  3
------+-xz-xz-xz-xz-
0    | ZY ZY XZ _X
1    | _Y ZY Z_ ZZ
2    | Y_ YX XX XX
3    | ZZ ZZ _X XZ
sign | -- -- -+ +-


inverts into this tableau:

      | 0  1  2  3
------+-xz-xz-xz-xz-
0    | YX XX ZZ Y_
1    | YX YX ZY Y_
2    | XZ Z_ _Y _X
3    | _X Y_ _Y XZ
sign | ++ -+ +- -+