# Clifford element/tableau composition as matrix multiplication

Elements of the $$n$$-qubit Clifford group (or more precisely, elements of the projected $$n$$-qubit Clifford group, see Is the Clifford group finite?) may be represented as $$2n \times 2n + 1$$ binary-valued matrices called tableaus. The tableaus define the stabilizer group for a quantum state, as well as its so-called destabilizer group. Each row defines a different Pauli string, and the columns 1 to 2n correspond to Pauli operators on each of the qubits (the first n columns correspond to Pauli X's, and the next n columns correspond to Pauli Z's). The final column contains the phase bits, which signifies whether a given stabilizer should be multiplied by an overall factor of +1 or -1. In particular, a tableau $$T$$ is written as:

$$T = \begin{pmatrix} \tilde{X} & \tilde{Z} & \tilde{p} \\ X & Z & p \\ \end{pmatrix} \,,$$ where $$\tilde{X}, X, \tilde{Z}, Z$$ are $$n \times n$$ matrices and $$\tilde{p}, p$$ are length-$$n$$ vectors. All quantities are binary-valued.

If the phase-bits are dropped,

$$T' = \begin{pmatrix} \tilde{X} & \tilde{Z} \\ X & Z \\ \end{pmatrix} \,,$$

then a nice property emerges which is that the composition of two tableaus is naturally implemented as matrix multiplication, i.e., $$T_{ab}' = T'_a T_b' \text{ mod } 2$$ is the phase-bit-omitted tableau corresponding to the composition of Clifford elements $$a, b$$. This, combined with the fact that the $$T'$$ matrices are symplectic matrices, is helpful in working out the dimension of the Clifford group.

My question is: is there an extension of this matrix expression $$T_{ab}' = T'_a T_b' \text{ mod } 2$$ which allows for the incorporation of the phase bits?

I understand that matrix multiplication is less efficient than the way most Clifford simulators work, but it would still be useful to understand how to represent the group composition operation directly in terms of matrix algebra.

• Not an answer, as it is not a formulation which is as nice as the matrix multiplication, but have a look at this paper: arxiv.org/pdf/1603.03999.pdf, in particular section 4, which mentions how to calculate the phase. Feb 23 at 14:12

The columns of a tableau correspond to the Pauli strings. Each one is the result of conjugating one of the generators $$X_0, Z_0, X_1, Z_2, \dots, X_{n-1}, Z_{n-1}$$ by the Clifford represented by the tableau.

When you perform the computation $$T = B \cdot A$$, the $$k$$'th column of $$T$$ is created by multiplying together columns from $$B$$ as determined by the entries in the $$k$$'th column of $$A$$. For example, if you're computing the $$X5$$ column of $$T$$, and $$A_{X5,3} = Y$$ then you will need to multiply $$B_{Y3}$$ into that column at some point. You can test this out by comparing against Stim's Tableau composition methods:

from typing import Literal

import stim

def compute_ba_col(
B: stim.Tableau,
A: stim.Tableau,
col: int,
basis: Literal['X', 'Y', 'Z'],
) -> stim.PauliString:
ax = A.x_output(col)
az = A.z_output(col)
ay = ax * az * 1j
a = {'X': ax, 'Y': ay, 'Z': az}[basis]

result = stim.PauliString(len(B))
result *= a.sign
for row in range(len(B)):
a_pauli = 'IXYZ'[a[row]]
x = B.x_output(row)
z = B.z_output(row)
if a_pauli == 'X':
result *= x
elif a_pauli == 'Y':
result *= x
result *= z
result *= 1j
elif a_pauli == 'Z':
result *= z

return result

def test_compute_ab_col():
A = stim.Tableau.random(10)
B = stim.Tableau.random(10)
T = B * A
assert T.x_output(3) == compute_ba_col(B, A, 3, 'X')
assert T.y_output(4) == compute_ba_col(B, A, 4, 'Y')
assert T.z_output(5) == compute_ba_col(B, A, 5, 'Z')

if __name__ == '__main__':
test_mul()


The reason I'm pointing this out is that, when looking at things from this column perspective, the issue is simpler. Normal matrix multiplication creates linear combinations of vectors, and this creates products of Pauli strings, so how do we make products of Pauli strings look more like normal linear combinations of vectors.

Two things stand out to me, that make this code look different from matrix multiplication. First is the shenanigans with the sign bit. You can see it sort of manually coming along for the ride in the code. Also, behind the scenes, the pauli string multiplications have phase kickbacks of 1, i, -i, or -1 that are going into the sign of the output. We will fold this into the definition of $$+$$. Second is the manual multiplexing between $$X$$, $$Y$$, and $$Z$$. We'll fold this into the definition of $$\times$$.

To fix the sign issue, we'll distribute the sign over the entire column. Instead of storing it separately from the Paulis, we'll expand from storing a Pauli in each cell of the column to storing a signed-pauli from $${I, X, Y, Z}$$ to $$\{I, X, Y, Z\} \otimes \{1, -1, i, -i\}$$ in each cell of the column. This allows the signs to be computed entirely within the Pauli-with-sign product, without needing to accumulate it separately. It means the representation will be degenerate, since each of $$(-X) \otimes Y = X \otimes (-Y) = (iX) \otimes (iY)$$ will be stored with different bits, but now the composition operation is just doing linear combinations where vector addition is broadcasting the group operator "Pauli-with-sign-multiplication" over the two vectors. Essentially, this is making Pauli string multiplication behave in the way you'd expect so that the vector addition $$u + v$$ works by broadcasting $$+$$ over the entries of $$u$$ and $$v$$, where $$u_k + v_k$$ is doing Pauli-with-sign multiplication.

With $$+$$ doing the right thing, you now need $$\times$$ to do the right thing. I think for this to work you need to expand the group to pairs-of-paulis-with-signs. This allows you to fuse the column $$T_{Xk}$$ and the column $$T_{Zk}$$ for each $$k$$ into a single column $$T_k$$ that has pair-of-signed-paulis cells. This allows the multiplexing logic in the code that looks like "pick X or Z or XZi depending on the Pauli" into the definition of the $$\times$$ operator. This should leave behind code that looks exactly like matrix multiplication, where $$T_{i,k} = \sum_j B_{i,j} \times A_{j,k}$$, thanks to the right choice of definition of $$+$$ and $$\times$$.

I'm writing my bachelor's thesis on this topic, and I have done some computations. Below is an extract from the text I'm writing.

As far as I know, I don't think the sign vectors can be very easily computed for qubits (but I believe it's easier for odd prime power dimensions), since in the qubit case, the function $$\beta:\mathbb{F}_2^{2n}\to\mathbb{Z}_4$$ below cannot be further simplified.

Note that for $$v\in\mathbb{F}_2^{2n}$$ with $$v=(x,z)$$ where $$x,z\in\mathbb{F}_2^{n}$$, I defined $$[[v]] = [[(x,z)]] := i^{z^T x} X(x) Z(z) ,$$ and the symbol $$\oplus$$ is for bit-wise binary addition.

Basically, it's the same argument as the comment above from M. Stern, or as in section 4.4 of Markus Heinrich's PhD thesis (https://kups.ub.uni-koeln.de/50465/).

• I have also just implemented this $O(n^3)$ tableau multiplication (with the sign vector) in python, so it is possible. Feb 27 at 19:06
• By the way, qiskit (github.com/Qiskit/qiskit/blob/stable/1.0/qiskit/quantum_info/…) already has a Python implementation for composing Clifford operators, and it's also the same idea. Feb 28 at 18:07