6 Stabiliser theory

In Chapter 5, we already built up a good collection of practical tools for working efficiently with Clifford diagrams and circuits using rewriting. However, this is quite different from the toolkit one more typically encounters in the literature. An alternative way to work with Clifford maps is to focus not on the maps themselves, but rather families of Pauli operators that stabilise them. This approach is sometimes referred to as stabiliser theory or the stabiliser formalism. In this section, we will see that this formalism gives a fully equivalent way to represent and efficiently simulate Clifford maps. In order to do this, we will develop a theory of Pauli projections, which are maps that project onto the

+ 1

- 1

eigenspace of an

n

-qubit Pauli operator. Interestingly, these always chop a space precisely in half: the

2^{n}

-dimensional space of

n

qubits can be regarded as the direct sum of two

2^{n - 1}

-dimensional subspaces in the range of a Pauli projection and its orthocomplement. As we’ll see, subsequent commuting Pauli projections will further chop the space in half, until we get all the way down to a

2^{0} = 1

dimensional space. This leads us to what we will call the Fundamental Theorem of Stabiliser Theory in Section 6.2.1, which states that

k

independent, commuting Pauli operators on

n

qubits uniquely fix a

2^{n - k}

-dimensional subspace of

{(ℂ^{2})}^{\otimes n}

. In particular, when

n = k

, this gives us a 1D space so that it uniquely fixes a state up to a scalar factor. We will see that these states, often called stabiliser states in the literature, are precisely the Clifford states we saw in Chapter 5. We will also see that all of the interesting things we might want to compute about a stabiliser state, such as its evolution through a Clifford circuit or measurement probabilities, can be computed in terms of its associated Pauli operators. This gives us a powerful second perspective on Clifford maps, which we will apply to quantum error correction and fault-tolerant quantum computation in Chapter 11. In Chapter 7, we will see that Pauli projections induce a related type of map, called Pauli exponentials. These are closely related to phase gadgets and give us a new way to talk about universal quantum computations as well as allowing us to synthesise circuits that simulate physical processes on a quantum computer.

6.1 Paulis and stabilisers

These are self-adjoint matrices, so they each have a basis of eigenstates. These are respectively:

When viewed on the Bloch sphere these six states lie in the corners corresponding to the three principal axes:

Each of these states is uniquely defined (up to global phase) as being the

+ 1

eigenvector of one of the Pauli matrices. In particular,

| 0 ⟩, | + ⟩

and

| + i ⟩

are the

+ 1

eigenvectors of

Z, X, Y

, respectively, while

| 1 ⟩

|−⟩

and

| - i ⟩

are the

+ 1

eigenvectors of

- Z, - X, - Y

. So while we don’t care about the global phase of the vectors, for this definition of being the

+ 1

eigenstate, we do care about the global phase of the Pauli operators, since the

+ 1

eigenvector of

Z

| 0 ⟩

while the

+ 1

eigenvector of

- Z

| 1 ⟩

An important fact about stabilisers is that the product of stabilisers is also a stabiliser. Suppose

A | ψ ⟩ = | ψ ⟩

and

B | ψ ⟩ = | ψ ⟩

. Then,

AB | ψ ⟩ = A | ψ ⟩ = | ψ ⟩

. For that reason, we’ll soon be interested not in just single operators stabilising a state, but whole groups of them. Each of the Pauli matrices is its own inverse:

X^{2} = Y^{2} = Z^{2} = I

, and if we multiply two different Pauli matrices, we get the third one, up to a factor of

i

If we multiply two Paulis going forward in the cycle, we get the third one with a factor of

+ i

, and if we multiply backwards, we get it with a factor of

- i

. Note that from the multiplications of (6.2) we also see that if we have two different Paulis

P

and

Q

that then

PQ = - QP

. We say then that these Paulis anti-commute. Accounting for scalar multiples of

i

, we get a 16-element group, called the single-qubit Pauli group:

We can then ask which subgroups of this group stabilise some state

| ψ ⟩

. The trivial subgroup

{I} \subseteq P_{1}

stabilises everything, so that’s not very interesting. Also,

- I | ψ ⟩ = - | ψ ⟩

, so any group containing

- I

doesn’t stabilise anything except the zero state, which is also not very interesting. This rules out the whole group

P_{1} \subseteq P_{1}

, and any group containing

\pm iP

, because

{(\pm iP)}^{2} = {(\pm i)}^{2} I = - I

. That leaves just 6 subgroups, corresponding exactly to the 6 points on the Bloch sphere of (6.1):

Note we write

⟨...⟩

to mean the subgroup generated by the given operators, so for example

⟨ X ⟩ = {I, X}

In this section, we will generalise this idea of groups stabilising a state from one qubit to

n

qubits, by looking at subgroups of the following group.

We will refer to the elements of the

n

-qubit Pauli group as Pauli strings, and introduce special notation for them:

Concretely, fixing a Pauli string consists of choosing a global phase from the set

{1, + i, - 1, - i}

and for each

P_{j}

, a Pauli from the set

{I, X, Y, Z}

. Since each of these choices yields a distinct element of

P_{n}

, it follows that

| P_{n} | = 4^{n + 1}

Exercise 6.2. Fix an arbitrary pair of Pauli strings $\vec{P}, \vec{Q} \in P_{n}$ , where:

\vec{P} : = i^{k} P_{1} \otimes \dots \otimes P_{n} \vec{Q} : = i^{l} Q_{1} \otimes \dots \otimes Q_{n}

Prove the following properties:

a): $\vec{P}$ is unitary.
b): ${\vec{P}}^{†} = \vec{P}$ if $k$ is even, otherwise ${\vec{P}}^{†} = - \vec{P}$ .
c): ${\vec{P}}^{2} = I$ if $k$ is even, otherwise ${\vec{P}}^{2} = - I$ .
d): $\vec{P}$ and $\vec{Q}$ either commute ( $\vec{P} \vec{Q} = \vec{Q} \vec{P}$ ) or anti-commute ( $\vec{P} \vec{Q} = - \vec{Q} \vec{P}$ ).

For the majority of this chapter and the next one, we will mostly be interested in self-adjoint Pauli strings, i.e. those whose global phase is

\pm 1

. As the name suggests, this implies that

{\vec{P}}^{†} = \vec{P}

. Since Pauli strings are unitaries, being self-adjoint implies that they are also self-inverse, i.e.

{\vec{P}}^{2} = I

6.1.1 Clifford conjugation, a.k.a. pushin’ Paulis

As we first pointed out way back in Example 3.2.2, whenever there are

Z

X

gates on the input of a Clifford circuit, we can always ‘push them through’ to the outputs using ZX rules. We now know enough about Clifford unitaries to prove this straightforwardly. We saw in Proposition 5.3.14 that any Clifford unitary

U

can be written as a circuit built out of CNOT, Hadamard, and

S

gates. Hence, we only need to check that we can push arbitrary single Pauli gates through each of these three. That is, for any single

Z

X

on any input, we can push it through to

Z

and

X

gates on the outputs. For the Hadamard gate,

Z

pushes through and becomes

X

and

X

pushes through to become

Z

Note that we picked up the global phase of

e^{iπ ∕ 2} = i

when we used the

π

-commutation rule

(π)

. Finally, for the CNOT gate, there are 4 cases to consider, corresponding to a

Z

X

gate on either of the two inputs:

Since we can push any

Z

X

gate through any Clifford gate, we can push any

Y = iXZ

gate through as well. Putting these rules together, we can see that, for any Pauli string

\vec{P}

and Clifford unitary

U

, we can push

\vec{P}

through

U

gate-by-gate, getting a (probably different) Pauli string

\vec{Q}

on the outputs.

The second equation above, written symbolically as

\vec{Q} = U \vec{P} U^{†}

, says that conjugating a Pauli string by a Clifford unitary yields another Pauli string. We will see in Section 6.4 that the converse of Proposition 6.1.3 also holds: any unitary that sends Pauli strings to Pauli strings under conjugation is Clifford. A variation on this result, which will prove to be very useful in this chapter, is that we can use Clifford unitaries to simplify a multi-qubit Pauli string to one that is non-trivial on just one qubit (say

Z_{1}

Proof. The first step will be to find a Clifford unitary that conjugates $\vec{P}$ to a Pauli string ${\vec{P}}^{'}$ where $P_{i}^{'} \in {I, Z}$ for all $i$ . Set $V_{i} = I$ if $P_{i} = I$ or $P_{i} = Z$ , set $V_{i} = H$ if $P_{i} = X$ , and set $V_{i} = X (\frac{π}{2})$ if $P_{i} = Y$ . Then $V : = V_{1} \otimes \dots \otimes V_{n}$ gives $V \vec{P} V^{†} = {\vec{P}}^{'}$ with the desired property. We will now find a CNOT circuit $W$ such that $W {\vec{P}}^{'} W^{†} = \pm Z_{j}$ . The desired unitary is then $U : = W \circ V$ , potentially composed with an additional $X_{j}$ in order to get rid of the unwanted minus sign in $\pm Z_{j}$ . We will build $W$ step by step as follows. By assumption $\vec{P}$ is non-trivial, and hence so is ${\vec{P}}^{'}$ , which means at least one $P_{k}^{'}$ is non-trivial. If $P_{j}^{'} = I$ , then we add a CNOT from $j$ to $k$ to $W$ (meaning the control is on $j$ and the target is on $k$ ). This ensures that there is a $Z$ on qubit $j$ . Now it remains to ‘clean up’ the $Z$ ’s on the other qubits. To do this, for every $P_{k}^{'}$ where $k \neq j$ and $P_{k}^{'} = Z$ we apply a CNOT from $k$ to $j$ . □

Example 6.1.5. Suppose we have $\vec{P} = - Y XIZ$ and that we want to find a $U$ that maps it to $Z_{3}$ . First conjugating $\vec{P}$ with the right single-qubit Cliffords gives us just $Z$ ’s and identities and removes the $- 1$ phase:

(6.3)

Then first doing a CNOT from the third qubit to get a $Z$ there, and then adding CNOTs to it to get rid of the $Z$ ’s on the other qubits we get the following:

Since any Clifford isometry can be written as a Clifford unitary with some ancilla qubits, the ‘Pauli pushing’ property holds for isometries as well.

Proof. By Exercise 5.14, for any Clifford isometry $V$ , there exists a Clifford unitary $U$ such that:

Since $\vec{P} \otimes I \otimes \dots \otimes I$ is a Pauli string on $n$ qubits, we can use Proposition 6.1.3 to push it through $U$ :

□

6.1.2 Stabiliser subspaces

We already noted that, if unitaries

A

and

B

both stabilise the same state

| ψ ⟩

, then their product

AB

also stabilises that state, as

AB | ψ ⟩ = A | ψ ⟩ = | ψ ⟩

. Hence, the set of stabilisers of a given state forms a group. In the other direction, if two states

| ψ ⟩

and

| ϕ ⟩

are stabilised by a map

A

, then:

This means the set of states stabilised by a group of linear operators always forms a subspace of

{(ℂ^{2})}^{\otimes n}

Note that in our definition of stabiliser group, we have explicitly ruled out those groups which only stabilise the zero state

| ψ ⟩ = 0

. This is very convenient because it immediately puts several constraints on which subgroups form stabiliser groups. Most importantly, stabiliser groups are always commutative (a.k.a. Abelian), meaning all of their elements commute.

Proof. If $- I \in S$ , then all $| ψ ⟩ \in Stab (S)$ satisfy $| ψ ⟩ = - I | ψ ⟩ = - | ψ ⟩$ , so that $Stab (S) = {0}$ . If, for some $\vec{P}$ , we have ${\vec{P}}^{2} \neq I$ , then by Exercise 6.2, ${\vec{P}}^{2} = - I$ . But then $- I \in S$ , so again $Stab (S) = {0}$ . Finally, since every element in $S$ is self-adjoint (or equivalently for unitaries, self-adjoint), $S$ must be commutative: $\vec{P} \vec{Q} = {\vec{P}}^{†} {\vec{Q}}^{†} = {(\vec{Q} \vec{P})}^{†} = \vec{Q} \vec{P}$ . □

Thus we have shown that, in order to stabilise a non-zero subspace, a subgroup of the Pauli group must satisfy several conditions. But are those conditions also sufficient? That is, does any subgroup of the Pauli group satisfying the conditions in Proposition 6.1.8, or by Remark 6.1.9 just the property that

- I \notin S

, form a stabiliser group? As it turns out, the answer is yes, and we can even figure out the dimension of the subspace stabilised by such a group. The key point to figuring this out has to do with number of independent generators of

S

Exercise 6.3. Let $S \subseteq P n$ be a group satisfying the properties of Proposition 6.1.8.

a): Show that there exists a set of independent Paulis ${\vec{P}}_{1}, \dots, {\vec{P}}_{k}$ that generates $S$ .
b): Show that any $\vec{Q} \in S$ can be written uniquely as some product of these Paulis (taking the convention that the “empty product” is equal to $I \in S$ ).
c): Show that such a product gives $\vec{Q}$ exactly, and not up to phase.

Hence, we can describe a stabiliser group by a set of independent Paulis that generate it. While

n

-qubit stabiliser groups may in general be very large, we will see that we can work with them efficiently by representing them as sets of generators.

6.2 Stabiliser measurements

In Section 2.2.4, we defined measurements as sets of projectors that sum up to the identity:

We also noted in that section that a self-adjoint operator

O

always defines such a set of projections, on to each of the subspaces associated with each distinct eigenvalue of

O

. Any self-adjoint Pauli string

\vec{P}

is, in particular, a self-adjoint operator, so we can find such a set of projectors. In fact, these projectors always take a particularly simple form.

Proof. We can show that ${(Π (k) \vec{P})}^{†} = Π (k) \vec{P}$ and $Π (k) \vec{P} Π (k) \vec{P} = Π (k) \vec{P}$ by concrete calculation, using the fact that ${\vec{P}}^{†} = \vec{P}$ and ${\vec{P}}^{2} = I$ . For (6.4), first assume $\vec{P} | ψ ⟩ = {(- 1)}^{k} | ψ ⟩$ for $k = 0, 1$ . Then:

Π (k) \vec{P} | ψ ⟩ = \frac{1}{2} (I + {(- 1)}^{k} \vec{P}) | ψ ⟩ = \frac{1}{2} (| ψ ⟩ + {(- 1)}^{2 k} | ψ ⟩) = | ψ ⟩

Conversely, if $Π (k) \vec{P} | ψ ⟩ = | ψ ⟩$ , then $\frac{1}{2} (I + {(- 1)}^{k} \vec{P}) | ψ ⟩ = | ψ ⟩$ . Multiplying both sides by 2 gives:

| ψ ⟩ + {(- 1)}^{k} \vec{P} | ψ ⟩ = 2 | ψ ⟩

Subtracting a $| ψ ⟩$ from both sides gives ${(- 1)}^{k} \vec{P} | ψ ⟩ = | ψ ⟩$ . Multiplying both sides by ${(- 1)}^{k}$ then gives $\vec{P} | ψ ⟩ = {(- 1)}^{k} | ψ ⟩$ . □

In the next exercise, you will prove some facts about Pauli projectors that will come in handy later.

Exercise 6.4. For $\vec{P}, \vec{Q}$ self-adjoint Pauli strings, show that Pauli projectors satisfy the following properties:

a): $Π (0) \vec{P} + Π (1) \vec{P} = I$ and $Π (0) \vec{P} - Π (1) \vec{P} = \vec{P}$ .
b): $U Π (k) \vec{P} U^{†} = Π (k) U \vec{P} U^{†}$ for any unitary $U$ .
c): $\vec{P} \vec{Q} = \vec{Q} \vec{P} ⟹ Π (j) \vec{P} Π (k) \vec{Q} = Π (k) \vec{Q} Π (j) \vec{P}$ .
d): $Π (0) \vec{P} Π (0) \vec{Q} = Π (0) \vec{P} Π (0) \vec{P} \vec{Q}$ .
e): $Π (0) I = I$ and $Π (1) I = 0$ .

In this section, we will derive a useful graphical representation for the projectors

Π (0) \vec{P}

and

Π (1) \vec{P}

. This representation will help us prove the Fundamental Theorem of Stabiliser Theory in the next section, as well as leading naturally to Pauli exponentials, which we’ll introduce in Chapter 7. Rather than directly building the Pauli projectors

Π (k) \vec{P}

, we will construct a “controlled” version of the projector, namely a ZX-diagram with the property that, when we plug in the computational basis effect

⟨ k |

to the first output, we’ll be left with the projector

Π (k) \vec{P}

. This will give us a handy way to build up projectors for arbitrary Pauli strings from the basic Pauli projectors for

X

Y

, and

Z

. We’ll start with

Z

. The Pauli projectors are simply the projections onto the two

Z

eigenstates, i.e. the computational basis elements:

More generally, we want to construct a new kind of generator, called a Pauli box that produces the projector

Π (k) \vec{P}

when we plug in a computational basis effect

⟨ k |

. We can get the other two basic Pauli boxes, corresponding to projectors

Π (k) X

and

Π (k) Y

, by applying unitaries to send the

Z

eigenstates to

X

and

Y

eigenstates, respectively. To do that, let’s ZX-ify the Bloch sphere picture from (6.1).

Note that, while there is one obvious choice for the

Z

and

X

eigenstates, using spiders of the opposite colours, we actually have two choices for

Y

: either using

Z

phases or (negative)

X

phases. For our purposes, it will be more convenient to use the

X

phases, so:

Recall that because the

⟨ + i |

is defined to be the adjoint of

| + i ⟩

, we need to flip the phase to represent the

⟨ + i |

. By conjugating the Z-spider with

H

X (- \frac{π}{2})

, we obtain Pauli boxes for

X

and

Y

. That is, for

P \in {X, Y, Z}

, we have:

For building up generic Pauli strings

\vec{P}

, we should also have a trivial Pauli box corresponding to

Π (k) I

. We can obtain this simply as

| 0 ⟩ \otimes I

. In summary, the four basic Pauli boxes are given as:

Curiously, we can also use Pauli boxes to ‘switch on’ the Pauli unitary by plugging in basis elements of the other colour.

There is a good reason for this, which we’ll discuss in more detail when we introduce Pauli exponentials in Chapter 7. For now, we’ll see that this gives us everything we need to construct the projectors

Π (k) \vec{P}

for longer Pauli strings.

Using this definition, we can prove the generalisation of the equation in Exercise 6.5 to any self-adjoint Pauli string

\vec{P}

Proof. This follows from decomposing the $X$ spider as a number of $Z$ spiders (i.e. X basis elements):

(6.7)

Applying (6.7), we have:

Then, by Exercise (6.6), the diagram above equals $\frac{1}{2} (I + {(- 1)}^{k} \vec{P}) = Π (k) \vec{P}$ . □

By unrolling the definition of the Pauli box, we can see that, for any Pauli string

\vec{P} = P_{1} \otimes \dots \otimes P_{n}

with

P_{i} \in {X, Y, Z}

, we have:

The general case can be obtained by additionally representing any

P_{i} = I

by simply not connecting to the

i

-th qubit, as we will see in the following example.

Example 6.2.5. The single-qubit and two-qubit Pauli projectors correspond to some simple ZX-diagrams. In particular, for a single qubit it always disconnects:

(6.9)

While $Π (0) \vec{P}$ for $\vec{P} = X \otimes X$ (abbreviated $XX$ ) becomes a 2-to-2 X spider:

(6.10)

Note that for a Pauli string $\vec{P}$ , if some $P_{i} = I$ , then the projector does not interact with the qubit $i$ :

(6.11)

We conclude this section by noting that Pauli boxes are an example of a more general object, which we call a measure box, that can be used to represent a generic 2-outcome measurement.

Exercise 6.8. Let $M : H \to ℂ^{2} \otimes H$ be a measure box.

a)

Show that the following is a projector for $k \in {0, 1}$ :

b)

Show that $M_{0} + M_{1} = I$ .

c)

Show that each of the 4 Pauli boxes:

are measure boxes.

d)

Let $N : K \to ℂ^{2} \otimes K$ be a second measure box. Show that $M$ and $N$ can be combined as follows to form a new measure box satisfying (6.12):

and hence that Pauli boxes for an arbitrary self-adjoint Pauli string $\vec{P}$ are measure boxes.

Since we’ll use it later, we’ll write down the conclusion of the above exercise explicitly in the following proposition.

6.2.1 The Fundamental Theorem of Stabiliser Theory

Any self-adjoint Pauli string (except the trivial one

I

) chops a space into two orthogonal parts: the

+ 1

eigenspace, a.k.a. the stabiliser subspace, and the

- 1

eigenspace, a.k.a. the “anti-stabiliser” subspace. It turns out that these spaces have equal dimension, so we can see a single Pauli string

\vec{P}

as chopping

n

-qubit space in half. Hence, the image of the projector

Π (0) \vec{P}

(or

Π (1) \vec{P}

) is

2^{n} ∕ 2 = 2^{n - 1}

dimensional. We can see this explicitly by splitting the projector

Π (0) \vec{P}

, i.e. finding an isometry

V : {(ℂ^{2})}^{\otimes (n - 1)} \to {(ℂ^{2})}^{\otimes n}

such that:

Proof. By Proposition 6.1.4, there exists a Clifford unitary $U$ such that $U^{†} {(- 1)}^{k} \vec{P} U = Z_{n}$ . Then, by Exercise 6.4, we have $U^{†} Π (0) {(- 1)}^{k} \vec{P} U = Π (0) U^{†} {(- 1)}^{k} \vec{P} U = Π (0) Z_{n}$ . As $V = U (I \otimes \dots \otimes I \otimes | 0 ⟩)$ is then a normalised state followed by a unitary, it is an isometry. We can show directly that it splits $Π (0) {(- 1)}^{k} \vec{P}$ :

□

As this proposition shows that a potential minus sign on the Pauli can be incorporate into the splitting isometry, we will just ignore these minus signs in this section and without loss of generality assume that every Pauli string has a constant of

+ 1

. If we split

Π (0) \vec{P}

V V^{†}

, then

Π (0) \vec{P} V = V V^{†} V = V

. Hence, for any state

| ϕ ⟩

n - 1

qubits we have

Π (0) \vec{P} (V | ϕ ⟩) = V | ϕ ⟩

, so that

V | ϕ ⟩

is stabilised by

\vec{P}

for any choice of

| ϕ ⟩

. Conversely, when

Π (0) \vec{P} | ψ ⟩ = | ψ ⟩

then

| ψ ⟩ = V (V^{†} | ψ ⟩)

so that taking

| ϕ ⟩ = V^{†} | ψ ⟩

shows that any stabilised state is of this form. We then see that

Stab (⟨ \vec{P} ⟩) = {V | ϕ ⟩ | | ϕ ⟩ \in ℂ^{2^{n - 1}}}

where we have written

⟨ \vec{P} ⟩

for the stabiliser group generated by

\vec{P}

. We hence have shown the following.

Now we claim that this ‘splitting’ of the

2^{n}

-dimensional Hilbert space into

2^{n - 1}

-dimensional parts continues on if we have an additional independent commuting Pauli. In particular, if we have two independent commuting self-inverse Paulis

\vec{P}

and

\vec{Q}

, then we claim that

\dim Stab (⟨ \vec{P}, \vec{Q} ⟩) = 2^{n - 2}

. This follows from the next lemma.

Proof. The $U$ from Proposition 6.2.8 is such that $\vec{P} = U Z_{n} U^{†}$ , and hence:

Π (0) \vec{Q} Π (0) \vec{P} = U U^{†} Π (0) \vec{Q} U U^{†} Π (0) \vec{P} U U^{†} = U Π (0) {\vec{Q}}^{'} Π (0) Z_{n} U^{†},

(6.14)

where $Q^{'} = U^{†} \vec{Q} U$ . Now, as $\vec{Q}$ and $\vec{P}$ commute, the Pauli strings that result from conjugating by the same unitary will also commute. Hence, ${\vec{Q}}^{'}$ commutes with $Z_{n}$ . This can only be the case when $Q_{n}^{'} = I$ or $Q_{n}^{'} = Z$ . In both cases we then have:

(6.15)

Note that we still write ${\vec{Q}}^{'}$ to denote ${\vec{Q}}^{'}$ where the $n$ th Pauli is removed to get a string of length $n - 1$ . We then calculate:

□

\vec{Q}

is independent from

\vec{P}

, then the

{\vec{Q}}^{'}

we get here in this lemma is non-trivial, so that we can then also split

Π (0) {\vec{Q}}^{'}

using Proposition 6.2.8. We then end up with

n - 2

wires in the middle, showing that indeed

\dim Stab (⟨ \vec{P}, \vec{Q} ⟩) = 2^{n - 2}

. We can now iterate this procedure, so that if we have

k

independent commuting Pauli strings, that the states they mutually stabilise has dimension

2^{n - k}

. In fact, this result is so crucial to this chapter, that we will give it a grand name: the Fundamental Theorem of Stabiliser Theory.

Proof. We prove this by induction on $k$ . The case of $k = 1$ is just Proposition 6.2.8. So suppose we know Eq. (6.16) holds when we have $k - 1$ independent generators. Then let $U_{1}$ be a Clifford unitary such that $U_{1} {\vec{P}}_{1} U_{1}^{†} = Z_{n}$ . We can then use an argument similar to that of Lemma 6.2.10 to write:

Here ${\vec{Q}}_{j} = U_{1} {\vec{P}}_{j} U_{1}^{†}$ . In order to use the induction hypothesis on ${\vec{Q}}_{2}, \dots, {\vec{Q}}_{k}$ we need to show that they are still commuting and independent when we are ignoring the last qubit. First note that because we conjugated them all with the same unitary $U_{1}$ that $Z_{n}, {\vec{Q}}_{2}, \dots, {\vec{Q}}_{k}$ are all still commuting and independent (not ignoring the $n$ -th qubit). As a result each of the ${\vec{Q}}_{j}$ has either an $I$ or $Z$ in the $n$ th position. This means that they all commute on the $n$ -th position, and hence the ${\vec{Q}}_{j}$ must also be commuting when we ignore this last qubit. Additionally, no product of ${\vec{Q}}_{2}, \dots, {\vec{Q}}_{k}$ can result in $Z_{n}$ due to the them being independent of $Z_{n}$ , so that no product of the ${\vec{Q}}_{j}$ can result in $\vec{I}$ when we ignore the last qubit. Hence, now ignoring the $n$ th qubit, the ${\vec{Q}}_{j}$ are independent and commuting, so that we can use the induction hypothesis. We then simply combine the resulting unitary $U$ with $U_{1}$ , and we are done. □

There is a bunch of important results that follow from this theorem. First, it allows us to bound how many independent commuting Pauli strings there can be.

Proof. Suppose $k$ is at least $n + 1$ . Then applying the proof of Theorem 6.2.11 to the first $n + 1$ generators, we end up in the following situation once we have repeated the procedure $n - 1$ times:

We see that we end up with single-qubit Pauli projectors $Π (0) Q_{n}$ and $Π (0) Q_{n + 1}$ that must be commuting, but also independent. But such single-qubit Paulis don’t exist, so we have reached a contradiction. □

This corollary allows us to answer the question we raised before: any subgroup of the Paulis satisfying the properties of Proposition 6.1.8 does in fact stabilise at least some non-zero state.

Proof. By Exercise 6.3, $S$ is generated by independent Paulis ${\vec{P}}_{1}, \dots, {\vec{P}}_{k}$ . Since $S$ is commutative, all these ${\vec{P}}_{j}$ must also commute. Hence, the previous corollary applies and we must have $k \leq n$ . Then Theorem 6.2.11 tells us that $\dim Stab (S) = 2^{n - k} \geq 2^{0} = 1$ , so that there is at least a $1$ -dimensional space of states that are stabilised by $S$ . □

In fact, recall from Remark 6.1.9 that as long as

- I \notin S

, the other properties of Proposition 6.1.8 are also satisfied, so any subgroup of

P n

that does not contain

- I

stabilises some non-zero state! We then also get the following corollary.

Proof. By definition of independence there is no non-trivial product of independent Pauli strings that produces $- I$ , so that $- I$ is not in the group. Hence, the previous corollary applies so that we see that it is a stabiliser group. □

When Paulis commute, their projections cut down the space of states they jointly stabilise. However, when they do not commute, then the second projection can be seen as applying a unitary to the space.

Exercise 6.11. Let $\vec{P}$ and $\vec{Q}$ be two self-adjoint Pauli strings that anti-commute.

1..: Show that $U = \frac{1}{\sqrt{2}} (\vec{P} + \vec{Q})$ is unitary and self-adjoint and that $U \vec{Q} = \vec{P}$ .
2..: Show that $U$ is Clifford by proving that $U \vec{R} U^{†}$ is Pauli for any Pauli string $\vec{R}$ . Hint: Make a case distinction on whether $\vec{R}$ (anti-)commutes with $\vec{P}$ and or $\vec{Q}$ .
3..: Show that $Π (0) \vec{P} Π (0) \vec{Q} = \frac{1}{\sqrt{2}} U Π (0) \vec{Q} = \frac{1}{\sqrt{2}} Π (0) \vec{P} U$ .
4..: Show that if $| ψ ⟩$ is an eigenstate of $\vec{Q}$ , that then the measurement ${Π (k) \vec{P}}$ has both outcomes occur with probability $\frac{1}{2}$ . Hint: Recall that the probability is given by $⟨ ψ | Π (0) \vec{P} | ψ ⟩$ . Now use the fact that $| ψ ⟩ = Π (0) \vec{Q} | ψ ⟩$ for both $| ψ ⟩$ and $⟨ ψ |$ .

6.3 Stabiliser states and the Clifford group

In this section we will look at states that are uniquely determined by the Pauli strings that stabilise them. That such states exist follows from Theorem 6.2.11, as we will show next. We will then look at the unitaries that map Pauli strings into Pauli strings. These unitaries form the Clifford group, and as the name suggests these are related to the Clifford unitaries we studied in Chapter 5 (in fact, they are the same thing).

6.3.1 Maximal stabiliser groups

Theorem 6.2.11 shows that if the number of generators of

S \subseteq P n

k

, that its stabiliser subspace has dimension

2^{n - k}

. This means that if the number of generators is exactly

n

, that its isometry

V

goes from

0

wires to

n

wires. But then

V

is just an

n

-qubit state! So let’s write

V = | ψ ⟩

. Then the projector onto the stabiliser subspace of

S

| ψ ⟩ ⟨ ψ |

. In other words: the only normalised state (up to global phase) that is stabilised by

S

| ψ ⟩

From Theorem 6.2.11 it also turns out that no stabiliser group can have more than

n

generators. Before we prove this it will be helpful to define a new class of stabiliser group.

Proof. Suppose $S$ is a stabiliser group with $k < n$ generators. We will show that it is not maximal, which will prove our claim. Note that the right-hand side of Eq. (6.16) says that we can write the projection to $Stab (S)$ as $U Π (0) Z_{n - k + 1} \dots Π (a_{n}) Z_{n} U^{†}$ , and hence that we can take ${\vec{P}}_{j} : = U Z_{n - j} U^{†}$ for $j = 1, \dots, k$ to be a set of generators for $S$ . Now, let $\vec{Q}$ be any non-trivial Pauli string on $n - k$ qubits. Then ${\vec{Q}}^{'} = \vec{Q} \otimes I_{2^{k}}$ commutes with all the $Z_{n - k + 1}, \dots, Z_{n}$ , and is also independent of this set. Hence $U {\vec{Q}}^{'} U^{†}$ is also independent from all the $U Z_{n - j} U^{†} = {\vec{P}}^{j}$ , and also still commutes with them. Hence, the stabiliser group generated by ${\vec{Q}}^{'}, {\vec{P}}^{1}, \dots, {\vec{P}}^{k}$ strictly includes $S$ , so that $S$ is not maximal. □

6.3.2 Stabiliser states

A maximal stabiliser group stabilises a unique state. Such states turn out to be very special, so we will give them a special name.

It might seem hard to determine when a state is stabilised by a maximal stabiliser group. Luckily, Corollary 6.3.4 offers an easier way to figure out when a state is stabiliser.

Proof. Suppose $| ψ ⟩$ is a stabiliser state, so that it is stabilised by a maximal stabiliser group $S$ . Then Corollary 6.3.4 shows that $S$ has $n$ generators. These generators are independent Pauli strings that stabilise $| ψ ⟩$ . Conversely, suppose $| ψ ⟩$ is stabilised by $n$ independent Pauli strings. Then these Pauli strings generate a stabiliser group, that again by Corollary 6.3.4 must be a maximal group, so that $| ψ ⟩$ is indeed a stabiliser state. □

Example 6.3.7. Let $| Ψ ⟩ : = \frac{1}{\sqrt{2}} (| 00 ⟩ + | 11 ⟩)$ be the maximally entangled Bell state. This state is stabilised by $ZZ$ and $XX$ . Indeed

\begin{array}{l} (Z \otimes Z) (| 00 ⟩ + | 11 ⟩) & = (Z | 0 ⟩) \otimes (Z | 0 ⟩) + (Z | 1 ⟩) \otimes (Z | 1 ⟩) \\ = | 0 ⟩ \otimes | 0 ⟩ + (- | 1 ⟩) \otimes (- | 1 ⟩) \\ = | 00 ⟩ + | 11 ⟩, \end{array}

and $(X \otimes X) (| 00 ⟩ + | 11 ⟩) = | 11 ⟩ + | 00 ⟩ = | 00 ⟩ + | 11 ⟩$ . As $| Ψ ⟩$ is a two-qubit state that is stabilised by two independent Pauli strings, it is hence a stabiliser state.

Example 6.3.8. Any graph state is a stabiliser state: recall that in a graph state $| G ⟩$ we have a one-to-one correspondence between qubits and the vertices of $G$ . We claim that the Pauli string ${\vec{P}}^{v} : = X_{v} \prod_{w \in N (v)} Z_{w}$ is a stabiliser of $| G ⟩$ , where $N (v)$ denotes the neighbourhood of the vertex $v$ , which is the set of vertices of $G$ that are connected to $v$ . As a Pauli string this stabiliser has an $X$ on the qubit corresponding to $v$ and a $Z$ on every qubit that is connected to $X$ . We can easily check this is a stabiliser of $| G ⟩$ by writing the graph state as a ZX-diagram, and pushing the $X$ into the graph state using $(π)$ and $(cc)$ :

Recall from Chapter 5 that we defined a Clifford state to be any state of the form

U | 0 \dots 0 ⟩

for some Clifford unitary

U

, and that these correspond to Clifford ZX-diagrams with no inputs. Observe that the isometries of Theorem 6.2.11 that split the projector onto a stabiliser subspace are Clifford diagrams. In particular, for a maximal stabiliser group, the isometry is a state, and hence is a Clifford state. We then have the following.

The converse is also true: any Clifford state is a stabiliser state. Recall from Theorem 5.3.8 that we can rewrite any Clifford state to a graph state with local Cliffords. Example 6.3.8 shows that all graph states are stabiliser states, so to prove that any Clifford state is a stabiliser state it remains to show that (local) Cliffords send stabiliser states to stabiliser states. This turns out to follow from the property of Clifford unitaries we proved in Section 6.1.1, namely that conjugating a Pauli string by a Clifford results in another Pauli string.

Proof. Let $| ψ ⟩$ be an $n$ -qubit stabiliser state and let ${\vec{P}}_{1}, \dots {\vec{P}}_{n}$ be a maximal set of independent stabilisers of $| ψ ⟩$ . Then we claim that the ${\vec{Q}}_{k} : = U {\vec{P}}_{k} U^{†}$ are independent stabilisers of $U | ψ ⟩$ so that $U | ψ ⟩$ is indeed a stabiliser state. First note that the ${\vec{Q}}_{k}$ are all Pauli strings because of Proposition 6.1.3. Second, they are indeed stabilisers of $U | ψ ⟩$ as ${\vec{Q}}_{k} U | ψ ⟩ = U {\vec{P}}_{k} U^{†} U | ψ ⟩ = U {\vec{P}}_{k} | ψ ⟩ = U | ψ ⟩$ . Finally, note that they are independent since if we had $I = \prod_{k_{j}} {\vec{Q}}_{k_{j}}$ then $I = U^{†} U = \prod_{k_{j}} U^{†} {\vec{Q}}_{k_{j}} U = \prod_{k_{j}} {\vec{P}}_{k_{j}}$ , which contradicts the independence of the $P_{k}$ . □

6.3.3 The Clifford group

The property we used to prove Proposition 6.3.10 above was that conjugations of Pauli strings by Cliffords produces Pauli strings. This is in fact quite a useful property that we have used many times throughout this chapter and the previous, so it is worthwhile to try and understand this a bit better. In particular, can we find more unitaries than just the Cliffords that have this property? For our next definition we need to know a little more group theory. Consider a group

G

with a subgroup

H

. An element

g \in G

normalises

H

when

g^{- 1} hg \in H

for every

h

. For instance, every

h^{'} \in H

normalises

H

, and if

G

is abelian, then every element of

G

normalises

H

. We write

N G (H)

for the set of elements of

G

that normalises

H

The group of Pauli-normalising unitaries is usually just called the Clifford group. However, as we already defined the term ‘Clifford unitaries’, we will not use the term Clifford group for now. Rest assured though that there is in fact a reason for the conflict in the naming scheme, as it turns out that Clifford unitaries and Pauli-normalising unitaries are the exact same thing. One direction of this equivalence we already have:

The

Z (\frac{π}{2})

phase gate is Clifford and hence Pauli normalising. What other

Z

phase gates are Pauli normalising? Consider the phase gate

Z (α) = diag (1, e^{iα})

. Conjugating

Z

by this gate of course preserves

Z

as they commute, so it remains to check the case for

X

The only way for this to be equal to a Pauli is for the phase

2 α

to be equal to

0

π

. Hence, we get

α = 0

(the identity),

α = π

(the

Z

Pauli),

α = \frac{π}{2}

(the

S

gate), or

α = - \frac{π}{2}

(the adjoint of

S

). There are no other

Z

phase gates that are Clifford! By symmetry (i.e. colour-changing the spiders) the same situation of course also holds for

X

phase gates: only

X (α)

gates with

α

a multiple of

\frac{π}{2}

are Pauli normalising. This seems to point towards ZX-diagrams only being Pauli normalising if all the phases involved are multiples of

\frac{π}{2}

, and this is in fact exactly right.

Proof. Let ${\vec{P}}_{k}$ be the Pauli string such that $Z_{k} U = U {\vec{P}}_{k}$ and similarly let ${\vec{Q}}_{k}$ be such that $X_{k} U = U {\vec{Q}}_{k}$ . Then we claim that ${\vec{P}}_{k}^{T} \otimes Z_{k}$ and ${\vec{Q}}_{k}^{T} \otimes X_{k}$ are stabilisers for $| U ⟩$ . Here ${\vec{P}}_{k}^{T}$ denotes the componentwise transpose of the Paulis in ${\vec{P}}_{k}$ , such that $Z^{T} = Z$ , $X^{T} = X$ , and $Y^{T} = - Y$ . That these are stabilisers is best demonstrated diagrammatically:

Here, the $Z$ is taken to appear on the $(n + k)$ th qubit. The same computation works for ${\vec{Q}}_{k}^{T} \otimes X_{k}$ . We then have $2 n$ stabilisers for a $2 n$ -qubit state. It is easily seen that these are all independent as they all have a unique non- $I$ component on the bottom $n$ qubits. Hence, by Proposition 6.3.6, $| U ⟩$ is a stabiliser state. □

Proof. Let $U$ be Pauli normalising. Then $| U ⟩$ is a stabiliser state, so that by Proposition 6.3.9 we can represent $| U ⟩$ by a Clifford ZX-diagram. Then by bending the top wires in $| U ⟩$ back to be inputs, we can also represent $U$ as a Clifford ZX-diagram. Proposition 5.3.14 then shows that $U$ must be equivalent to a circuit of CNOT, Hadamard and $S$ gates. □

6.3.4 Putting it all together

We have now seen a lot of different perspectives, definitions and equivalences between them, so let’s summarise what we have learned.

Proof. a) to b) is Lemma 6.3.15, b) to c) follows from Proposition 6.3.9, c) to d) is Proposition 5.3.14 and d) to a) is Proposition 6.1.3. □

Because of these equivalences we don’t have to make a distinction between Pauli-normalising unitaries, Clifford unitaries (those built from CNOT, Hadamard and

S

), and Clifford unitary diagrams (those whose diagram only contains

\frac{π}{2}

phases), and just refer to any of these as a Clifford unitary. We can write down a similar set of equivalences for stabiliser states.

Theorem 6.3.18. Let $| ψ ⟩$ be a state. The following are equivalent:

a): $| ψ ⟩$ is a stabiliser state.
b): $| ψ ⟩$ can be presented (up to non-zero scalar) as a Clifford diagram (that has no inputs).
c): $| ψ ⟩$ is equal (up to non-zero scalar) to a circuit of Hadamard, $S$ and CNOT gates applied to the $| 0 \dots 0 ⟩$ state.
d): $| ψ ⟩$ can be written as a graph state with local Cliffords.

Proof. a) to b) is Proposition 6.3.9, b) to c) is Proposition 5.3.10, c) to d) is Theorem 5.3.8 and d) to a) follows from Example 6.3.8 and Proposition 6.3.10. □

6.4 Stabiliser tableaux

We’ve seen that an

n

-qubit unitary is Clifford if and only if it maps every

n

-qubit Pauli string to a Pauli string under conjugation. There are exponentially many Pauli strings as

n

increases, but luckily we only have to check a few of them to verify the unitary is Clifford. In particular, it suffices to check that the

Z_{i}

and

X_{i}

are mapped to Pauli strings under conjugation. This gives us

2 n

conditions to check for an

n

-qubit unitary. We can present the resulting information in the form of a table that we call a stabiliser tableau. This is what we will look at in Section 6.4.2. Another way to present this information is as a special type of matrix that is called a symplectic matrix. This is what we will look at in Section 6.4.4. Before we do so however, let’s look a bit closer at the information encoded by knowing the result of these Pauli conjugations.

6.4.1 Cliffords are determined by Pauli conjugations

We will show that a Clifford unitary is completely determined by its action on Pauli strings.

Proof. By Lemma 6.3.15, $| U_{1} ⟩$ and $| U_{2} ⟩$ are stabiliser states. Fix $\vec{P}$ and let $\vec{Q}$ be such that $U_{1} \vec{P} = \vec{Q} U_{1}$ . Then we can check that ${\vec{P}}^{T} \otimes \vec{Q}$ is a stabiliser of $| U_{1} ⟩$ in the same way as in Lemma 6.3.15. Since $U_{1} \vec{P} U_{1}^{†} = U_{2} \vec{P} U_{2}^{†}$ we also have $U_{2} \vec{P} = \vec{Q} U_{2}$ , and hence ${\vec{P}}^{T} \otimes \vec{Q}$ is also a stabiliser of $| U_{2} ⟩$ . As $\vec{P}$ was arbitrary, $| U_{1} ⟩$ and $| U_{2} ⟩$ have the same stabilisers and hence are equal up to a global phase $α$ . Bending the wires back then shows that $U_{1} = e^{iα} U_{2}$ . □

We have been using two similar properties interchangeably: that a Pauli is mapped to a Pauli under conjugation, and that we can push a Pauli through a Clifford to get another Pauli. However, the equivalence between these relies on the map being unitary. It turns out that we can recover unitarity just by looking at whether we can push the

Z_{i}

and

X_{j}

through the map.

Proof. Taking adjoints in the equation $A Z_{i} = {\vec{P}}^{i} A$ we get $Z_{i} A^{†} = A^{†} {\vec{P}}^{i}$ . We then calculate: $A^{†} A Z_{i} = A^{†} {\vec{P}}^{i} A = Z_{i} A^{†} A$ . Analogously, $A^{†} A X_{j} = X_{j} A^{†} A$ for all $j$ . We can then check that the $2 n$ -qubit state $| A^{†} A ⟩$ has the $2 n$ stabilisers $Z_{i} Z_{n + i}$ and $X_{i} X_{n + i}$ for all $1 \leq i \leq n$ so that it is a stabiliser state. Furthermore, these stabilisers match those of $| I_{n} ⟩$ , where $I_{n}$ is the $n$ -qubit identity ( $| I_{n} ⟩$ is just $n$ overlapping cups, connecting qubit $i$ to $i + n$ ). Hence $A^{†} A = e^{iα} I_{n}$ for some $α$ . However, as $A^{†} A$ is a positive map, we must have $α = 0$ so that $A$ is indeed an isometry. Now if $n = m$ then we have an isometry from the space to itself, and these maps are necessarily unitary. □

6.4.2 Stabiliser tableaux

To check whether an

n

-qubit unitary is Clifford there are

2 n

conditions we need to check, corresponding to the conjugation of each of the

Z_{i}

and

X_{i}

Pauli strings by the unitary for

1 \leq i \leq n

. We can write this information succinctly in a table known as a stabiliser tableau. To demonstrate this principle let’s construct the stabiliser tableau for the CNOT gate. As it is a

2

-qubit gate there are

4

conditions we need to check, corresponding to the conjugation of

X_{1}

Z_{1}

X_{2}

and

Z_{2}

by the CNOT. As demonstrated in Section 6.1.1, conjugating

X_{1}

leads to the Pauli string

X_{1} X_{2}

and similarly

Z_{1}

is mapped to

Z_{1}

X_{2}

X_{2}

and

Z_{2}

Z_{1} Z_{2}

. Each of these values corresponds to a column in the stabiliser tableau, which we can now write down:

The bottom two rows indicate the Pauli that each of the

P_{i}

is sent to on each of the qubits

1

and

2

. The row labelled

\pm

denotes whether the Pauli is sent to the Pauli listed, or minus that. For instance, conjugating

Z

X

gives

XZX = - ZXX = - Z

, and hence would have a minus sign in the respective column. This phase can indeed only be a

+ 1

- 1

: the

Z_{i}

and

X_{i}

are self-adjoint, and hence so are

U Z_{i} U^{†}

and

U X_{i} U^{†}

. These minus signs are important as they allow us to distinguish the Paulis just from their tableaux:

We can use a stabiliser tableau to understand how the unitary acts on other Pauli strings than just those present in the tableau. For instance, suppose we wish to know how the Pauli string

X_{1} Y_{2}

is changed when we conjugate it by a CNOT. We realise that

X_{1} Y_{2}

is just the product

i X_{1} X_{2} Z_{2}

and hence, writing

U = CNOT

, we get:

But this latter expression is just the product of the three columns of the stabiliser tableau of the CNOT corresponding to

X_{1}

X_{2}

and

Z_{2}

(multiplied by a global factor of

i

). So we look at those columns in (6.17) and multiply them together:

Hence,

XY

is mapped to

Y Z

. If some of the

+

’s in these columns where

-

, then the standard rules for multiplying phase applies, e.g. “negative times negative is positive”. For instance, if we take the stabiliser tableau of

Y

in (6.18), and wish to find the action of

Y_{1} = i X_{1} Z_{1}

, we multiply the columns together as follows:

We then see that when

Y

is conjugated by

Y

we get

Y

, as we would expect. The information presented in a stabiliser tableau is enough to fully characterise a Clifford.

Proof. Of course, if $U_{1} = e^{iα} U_{2}$ for some global phase $α$ , then they have equal stabiliser tableaux, so let’s prove the converse. We have $U_{1} Z_{i} U_{1}^{†} = U_{2} Z_{i} U_{2}^{†}$ and $U_{1} X_{i} U_{1}^{†} = U_{2} X_{i} U_{2}^{†}$ for all $1 \leq i \leq n$ . These $Z_{i}$ and $X_{i}$ generate all $n$ -qubit Pauli strings and hence we have $U_{1} \vec{P} U_{1}^{†} = U_{2} \vec{P} U_{2}^{†}$ for all $\vec{P} \in P n$ . The result then follows from Proposition 6.4.1. □

Suppose we have a stabiliser tableau for a unitary

U_{1}

and another one for a unitary

U_{2}

. Can we then easily construct the tableau for the composition of the unitaries

U_{2} \circ U_{1}

? Suppose we wish to know the column in the stabiliser tableau of

U_{2} \circ U_{1}

corresponding to a

Z_{i}

. This is the Pauli string

U_{2} U_{1} Z_{i} U_{1}^{†} U_{2}^{†}

. Here the inner expression

U_{1} Z_{i} U_{1}^{†}

corresponds to the column of

Z_{i}

in the tableau of

U_{1}

. This will be some Pauli string

P_{1} P_{2} \dots P_{n}

, and so we need to know the values

U_{2} P_{j} U_{2}^{†}

and multiply these together. But the expressions

U_{2} P_{j} U_{2}^{†}

can be easily read from the tableau of

U_{2}

. This means that in order to know the Pauli on the

j

th qubit of the

Z_{i}

column in the tableau of

U_{2} U_{1}

, we need to look at the column of

Z_{i}

U_{1}

, and at the row corresponding to the

j

th qubit of the tableau of

U_{2}

. This feels quite like matrix multiplication. In the next sections we will see that this is in fact, exactly like matrix multiplication.

6.4.3 Paulis as bit strings

We can represent elements of the Pauli group as certain bit strings. For instance, we will write:

Generally, an element of the

n

-qubit Pauli group

P n

will be represented as a vector of

2 n

bits, followed by an integer that is taken modulo 4:

Here, the bits in the length-

n

bit strings

\vec{z}, \vec{x}

are given by the Paulis

P_{i}

via the relation

P_{i} = i^{- z_{i} x_{i}} Z^{z_{i}} X^{x_{i}}

where

z_{i}, x_{i}

are the

i

th bits of

\vec{z}

and

\vec{x}

and

s

is a complex number in the set

{1, i, - 1, - i}

. As a shorthand, we write

+

and

-

for

1

and

- 1

. This mapping between Pauli operations and bit strings is just a convention, and there are probably other ones that work just as well. The useful feature of this representation is that multiplication of Pauli group elements corresponds to addition of bit strings modulo-2, followed by some book-keeping to get the correct scalar: if we have Pauli strings

\vec{P}

and

\vec{Q}

represented as bit strings

\vec{P} = ({\vec{z}}_{1} | {\vec{x}}_{1}) a

and

\vec{Q} = ({\vec{z}}_{2} | {\vec{x}}_{2}) b

, then:

We will use the notation

⋆

to represent combining bit-representations of Pauli operators in this way. That is:

A little “gotcha” to watch out for here is that addition of the bit strings is performed modulo-2, but the dot products that appear in the exponent of

i

use normal addition of integers (or addition modulo 4, since

i^{4} = 1

). Instead of talking about ‘bit strings’ and ‘addition modulo-2’ it will be helpful to use a more mathematical way of talking about this, just like we had done in Chapter 4. We take the bits to be elements of field with two elements

𝔽 2 : = {0, 1}

. Recall from Definition 4.1.1 that the addition operation in this field is defined by

0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 0

, and the multiplication is the standard multiplication of the numbers

0

and

1

. As this is a field, we can view the bit strings as being part of a vector space over

𝔽 2

. In particular, ignoring the global phases for now, we can represent

n

-qubit Pauli strings as elements of the vector space

𝔽 2^{2 n}

. We can use these bit-representations to read off whether two Paulis commute or not. For Paulis

\vec{P} = ({\vec{z}}_{1} | {\vec{x}}_{1}) a

and

\vec{Q} = ({\vec{z}}_{2} | {\vec{x}}_{2}) b

we have

The reason for this formula is that we are counting the number of places where there is a

Z

on a qubit

i

\vec{P}

that matches to an

X

on a qubit

i

\vec{Q}

(and vice versa for

X

’s on

\vec{P}

and

Z

’s on

\vec{Q}

). Each of these matches results in an anti-commutation, but as long as there are an even amount, the Pauli strings commute. It turns out that the expression

{\vec{z}}_{1} \cdot {\vec{x}}_{2} \oplus {\vec{z}}_{2} \cdot {\vec{x}}_{1}

fits into the language of a well-studied subject in mathematics: symplectic forms.

Definition 6.4.4. Let $𝔽$ be a field (such as $𝔽 2$ ), and let $V = 𝔽^{2 n}$ be an even-dimensional vector space over this field. Then the symplectic inner product $ω : V \times V \to 𝔽$ on $V$ is defined as

ω ((\vec{a}, \vec{b}), (\vec{c}, \vec{d})) = \vec{a} \cdot \vec{d} - \vec{b} \cdot \vec{c},

where $\vec{a}, \vec{b}, \vec{c}, \vec{d} \in 𝔽^{n}$ are arbitrary vectors and $\cdot$ denotes the standard dot-product of elements of $𝔽^{n}$ : $\vec{a} \cdot \vec{d} = \sum_{i} a_{i} d_{i}$ .

In words: we take the dot product of the top half of the first vector with the bottom half of the second vector and subtract from this the dot product of the bottom half of the first vector with the top half of the second vector. Another way we could have written this symplectic product is to realise that it is essentially the standard dot product, except that we have interchanged the top and bottom half of the second vector and introduced a negation. The matrix that does this operation is the following:

Here,

0_{n}

and

I_{n}

are respectively the

n \times n

zero matrix and the

n \times n

identity matrix. We can then write the symplectic inner product as

⟨ v, w ⟩ = v^{T} Ω w

. Note that if

𝔽 = 𝔽 2

then

\vec{a} \cdot \vec{d} - \vec{b} \cdot \vec{c} = \vec{a} \cdot \vec{d} + \vec{b} \cdot \vec{c}

(because

- 1 = 1

modulo

2

). So combining what we’ve seen so far we see that we can represent length

n

Pauli strings as elements of the symplectic vector space

𝔽 2^{2 n}

(ignoring global phase), and that Pauli strings commute precisely when their symplectic inner product is zero. Additionally, the multiplication of Paulis corresponds (when we ignore phases) to addition of the vectors in this symplectic vector space. Let’s capture this in the following proposition.

6.4.4 Cliffords as symplectic matrices

We have now seen that we can just treat Pauli strings as vectors in a symplectic vector space, and that, up to a phase, multiplying Pauli strings corresponds to adding their bit strings. If we have a Clifford unitary

U

, then this maps a Pauli string

\vec{P}

to another Pauli string

U \vec{P} U^{†}

, so we should be able to write this as a map on the symplectic vector space as well, right? Let’s write

Û : P n \to P n

for the group homomorphism on the Pauli group given by conjugating by

U

. That is,

Û (\vec{P}) = U \vec{P} U^{†}

(this is indeed a group homomorphism as

U \vec{P} \vec{Q} U^{†} = U \vec{P} U^{†} U \vec{Q} U^{†}

). Note that

Û

is in fact an isomorphism, as it has an inverse

\hat{U^{†}}

. Let

S : P n \to 𝔽 2^{2 n}

be the map from Proposition 6.4.5 that maps a Pauli string to its corresponding bit string in the symplectic vector space. Ignoring the phases in

P n

, this map is an isomorphism of (abelian) groups. We can then make a ‘choice of inverse’

T : 𝔽 2^{2 n} \to P n

by setting

Note that this map produces self-adjoint Pauli strings, but that the map is not a group homomorphism (you can check that

T (1, 1) \neq T (1, 0) T (0, 1)

). We see then that

S \circ T = {id}_{𝔽 2^{2 n}}

, but in the other direction we only have

TS (\vec{P}) \propto \vec{P}

. Now let’s write

Ŝ (U) : 𝔽 2^{2 n} \to 𝔽 2^{2 n}

for the map

Ŝ (U) : = S \circ Û \circ T

. What properties does this map have? Even though

T

is not a group homomorphism, it is the case that

Ŝ (U)

is a group homomorphism of

𝔽 2^{2 n}

, i.e. a linear map:

Ŝ (U) (({\vec{z}}_{1}, {\vec{x}}_{1}) + ({\vec{z}}_{2}, {\vec{x}}_{2})) = Ŝ (U) ({\vec{z}}_{1}, {\vec{x}}_{1}) + Ŝ (U) ({\vec{z}}_{2}, {\vec{x}}_{2})

. This is because

T

is a group homomorphism ‘up to phase’, and both

Û

and

S

don’t care about this phase, so that it doesn’t change the outcome. Additionally,

Ŝ (U)

has an inverse

Ŝ (U^{†})

so that it is in fact a linear isomorphism. But it is not just any isomorphism. If the Pauli strings

\vec{P}

and

\vec{Q}

commute, then

Û (\vec{P})

and

Û (\vec{Q})

also commute, and similarly, if they didn’t commute, then

Û

preserves this property as well. We saw in the previous section that commuting Paulis are mapped by

S

to vectors whose symplectic inner product is zero. So putting these two facts together, we see that

Ŝ (U)

must be mapping vectors in such a way to preserve the symplectic inner product. There is a special name for such maps.

For Hilbert spaces we care a great deal about unitaries, which are maps that preserve the inner product. Similarly, for symplectic vector spaces, we care about the maps that preserve the symplectic inner product. As

Û

preserves commuting Paulis,

Ŝ (U)

must be a symplectic map. Writing

C n

for the

n

-qubit Clifford group,

Ŝ

then gives a group homomorphism

Ŝ : C n \to Sp (𝔽 2^{2 n})

. This map is not injective, and that’s because

𝔽 2^{2 n}

captures the Pauli group only up to phase. A Clifford

U

is in the kernel of this homomorphism, i.e.

Ŝ (U) = I_{𝔽 2^{2 n}}

, when

Û

maps every Pauli to itself up to a phase. This phase can only be

\pm 1

for each Pauli, as a Clifford maps self-adjoint Paulis to self-adjoint Paulis under conjugation. The Pauli strings themselves are examples of Cliffords that are sent to the kernel. When

U = \vec{P}

is a self-adjoint Pauli string, we see that indeed

U \vec{Q} U^{†} = \vec{P} \vec{Q} \vec{P} = \pm \vec{P} \vec{P} \vec{Q} = \pm \vec{Q}

, so that

Ŝ (U) = I_{𝔽 2^{2 n}}

. The converse turns out to also be true.

Proof. Write $Û$ for the conjugation map. We will construct a Pauli string $\vec{Q}$ that acts the same on all Paulis by conjugation as $Û$ , and hence by Proposition 6.4.1, $U$ must be equal to $\vec{Q}$ up to global phase. First we determine $Q_{1}$ . Write $Û (X_{1}) = a X_{1}$ , $Û (Z_{1}) = b Z_{1}$ for $a, b \in {1, - 1}$ . Then if $a = b = 1$ , we set $Q_{1} = I$ . If $a = - 1$ and $b = 1$ , we set $Q_{1} = Z$ . If $a = 1$ and $b = - 1$ we set $Q_{1} = X$ , and finally if $a = b = - 1$ we set $Q_{1} = Y$ . It is then easy to check that $Û (P_{1}) = \hat{\vec{Q}} (P_{1})$ for any Pauli $P \in {I, X, Y, Z}$ . We similarly set $Q_{2}, \dots, Q_{n}$ , so that $Û$ and $\hat{\vec{Q}}$ agree on all Pauli strings $P_{i}$ . As these generate all Pauli strings, we must then have $Û = \hat{\vec{Q}}$ and we are done. □

With this proposition we see that

Ŝ (U) = Ŝ (V)

iff

U = e^{iα} V \vec{Q}

for some global phase

α

and Pauli string

\vec{Q}

. So just like how the symplectic representation of the Pauli strings ignores the global phase, the symplectic representation of the Cliffords ignores Paulis. Okay, so when thinking about the symplectic space, and ignoring Paulis, the Cliffords become symplectic maps. What about the converse? If we are given a symplectic map on

𝔽 2^{2 n}

, can we find a Clifford that is mapped to it? In other words: is

Ŝ

surjective? To answer this questions it will be useful to define a ‘standard basis’ of

𝔽 2^{2 n}

. Write

z_{i} = S (Z_{i})

and

x_{j} = S (X_{j})

for the bit strings corresponding to the Pauli strings

Z_{i}

and

X_{j}

. These

z_{i}

and

x_{j}

of course span the space and are linearly independent so that they are indeed a basis. Note furthermore that the symplectic inner products of these are

⟨ z_{i}, z_{j} ⟩ = ⟨ x_{i}, x_{j} ⟩ = 0

, while

⟨ z_{i}, x_{j} ⟩ = δ_{ij}

, which encodes the fact that the

Z_{i}

all mutually commute (and the same for the

X_{j}

), while

Z_{i}

and

X_{j}

anti-commute when

i = j

Proof. Define $v_{i} : = M z_{i}$ and $w_{j} : = M x_{j}$ , the images of the standard basis after applying $M$ . As $M$ is symplectic and hence invertible, the vectors $v_{i}$ and $w_{j}$ must then also be independent. Furthermore, as $M$ preserves the symplectic inner product we still have $⟨ v_{i}, v_{j} ⟩ = ⟨ w_{i}, w_{j} ⟩ = 0$ and $⟨ v_{i}, w_{j} ⟩ = δ_{ij}$ . Let ${\vec{P}}^{i}$ be a self-adjoint Pauli string for which $S ({\vec{P}}_{i}) = v_{i}$ and similarly let ${\vec{Q}}_{j}$ be such that $S ({\vec{Q}}_{j}) = w_{j}$ (these Pauli strings are unique up to phases of $\pm 1$ ). Then the Paulis ${\vec{P}}_{i}$ are commuting, since $⟨ v_{i}, v_{j} ⟩ = 0$ , and similarly all the ${\vec{Q}}_{j}$ are commuting. The only pairs that don’t commute are ${\vec{P}}_{i}$ and ${\vec{Q}}_{j}$ when $i = j$ . We can ‘fix’ this lack of commutation by considering longer Pauli strings. Consider the following $2 n$ Pauli strings acting on $2 n$ qubits:

Z_{1} \otimes {\vec{P}}_{1}, \dots Z_{n} \otimes {\vec{P}}_{n}, X_{1} \otimes {\vec{Q}}_{1}, \dots, X_{n} \otimes {\vec{Q}}_{n} .

These Pauli strings all commute. Let’s check the only non-trivial commutation: $Z_{i} \otimes {\vec{P}}_{i}$ and $X_{j} \otimes {\vec{Q}}_{j}$ . When $i \neq j$ , we have that $Z_{i}$ and $X_{j}$ commute, and ${\vec{P}}_{i}$ and ${\vec{Q}}_{j}$ commute, so that the full strings obviously commute as well. When $i = j$ , then $Z_{i}$ and $X_{i}$ anti-commute, but so do ${\vec{P}}_{i}$ and ${\vec{Q}}_{i}$ , so that the complete strings still commute. We then have built $2 n$ independent, commuting, self-inverse Pauli strings acting on $2 n$ qubits. These then uniquely define a $2 n$ -qubit stabiliser state $| ψ ⟩$ , which is unique up to scalar. Bending back the top $n$ wires to be inputs, we then get a linear map $A$ going from $n$ qubits to $n$ qubits. We want to show it is unitary. As $Z_{i} \otimes {\vec{P}}_{i}$ is a stabiliser of $| ψ ⟩$ , we then see that $A Z_{i} = {\vec{P}}_{i} A$ :

Similarly, $A X_{j} = {\vec{Q}}_{j} A$ . Lemma 6.4.2 then shows that $A$ is (proportional to a) unitary, and as it comes from a stabiliser diagram it is Clifford. Furthermore $A Z_{i} A^{†} = {\vec{P}}_{i} A A^{†} = {\vec{P}}_{i}$ , so that $Ŝ (A) z_{i} = v_{i}$ . We defined $v_{i}$ to be such that $M z_{i} = v_{i}$ , and hence $Ŝ (A) z_{i} = M z_{i}$ . Completely analogously we have $Ŝ (A) x_{j} = M x_{j}$ , so that $Ŝ (A)$ and $M$ agree on a basis of $𝔽 2^{2 n}$ , so that indeed $Ŝ (A) = M$ . □

6.4.5 Adding back in the phases

So far we have ignored the phases in the symplectic representation. What happens when we try to add them back in? We get stabiliser tableaux! Let’s look again at the stabiliser tableau for the CNOT gate:

Now for each of the elements in the table we make the substitutions, corresponding to how we were encoding the Paulis as bitstrings:

If we squint a bit we can see that this is in fact a symplectic matrix, but with some additional information to record the phases. If we remove those phases and the label for the columns and rows we in fact get the symplectic matrix representation for the CNOT:

Then if we want to know for instance what happens when we conjugate

Y \otimes X

by CNOTs, we first write

Y \otimes X

as the vector

S (Y \otimes X) = {(1, 0, 1, 1)}^{T}

, and then we just multiply them:

This symplectic representation doesn’t contain the phase information though. We can fix this by just keeping the top row of the tableau 6.23 containing the phases, and also adding another top row to the Paulis to represent their global phase. If we do this, we however also have to modify how we multiply together tableaux and vectors, as the phase gets updated in quite a complicated way. This is not really relevant for us, so we leave it as an exercise.

6.4.6 Putting it all together

Let’s summarise what we have learned. We have seen that we can write a Pauli string as a bit string, where the first half of the bits tells you where the

Z

’s are, and the second half tells you where the

X

’s are (and so the overlap tells you where the

Y

’s are). We can then consider the Pauli group as a vector space of bit strings

𝔽 2^{2 n}

. Paulis either commute or anti-commute. This information is captured in

𝔽 2^{2 n}

by whether the associated vectors have a symplectic inner product of zero (for commuting) or one (for anti-commuting). As Cliffords map Paulis to Paulis under conjugation, and are completely determined by this action, we can represent Cliffords as matrices on the symplectic vector space

𝔽 2^{2 n}

. Conjugating by a Clifford preserves commutation, so that it preserves the symplectic inner product on this space. This means that the Cliffords correspond to symplectic maps. Conversely, any symplectic map on

𝔽 2^{2 n}

comes from a Clifford unitary. These constructions with the symplectic phases ignore the phases of the Paulis, and hence capture the Cliffords only up to local Paulis. We can fix this by adding some additional phase information to our symplectic space. This representation is then equivalent to the stabiliser tableau of the Clifford.

6.5 The Clifford hierarchy

In Chapter 5 we introduced Clifford unitaries in a somewhat ad-hoc way as those unitaries built from CNOT, Hadamard and

S

gates. In this chapter we have seen that we can define them in a mathematically nicer way as precisely those unitaries that send Pauli strings to Pauli strings under conjugation. It turns out we can extend this idea to a whole hierarchy of gates. First, let’s denote the set of Pauli gates by

C_{1}

The first level of the hierarchy consists of the Paulis by definition, and the second

C_{2}

contains unitaries that map Pauli strings to unitaries in

C_{1}

, i.e. the Paulis. Hence,

C_{2}

consists precisely of the Cliffords. The third level

C_{3}

then contains unitaries that map Pauli strings to Clifford unitaries. An example of a third-level unitary is the

T

gate

Similarly, the

Z (\frac{π}{8})

gate is in the 4th level, and more generally

Z (\frac{2 π}{2^{k}})

is in the

k

th level. The Clifford hierarchy is useful for thinking about gate teleportation protocols. As the name implies, gate teleportation generalises the idea behind quantum teleportation of Section 3.3.2. In quantum teleportation we move information from one qubit to another without changing the state. In gate teleportation we instead try to apply some specific unitary

U

to the state, without directly applying

U

to that qubit:

In this protocol we entangle our state with a specific maximally entangled state

| ψ ⟩

with the goal of executing

U

. However, we see that instead we end up with

U Z^{b} X^{a}

. In order to actually end up with

U

, we hence need to apply a correction of

U X^{a} Z^{b} U^{†}

. For a general

U

this doesn’t help us, since this requires us to execute

U

on the qubit after all. However, if

U \in C_{k}

, then

U X^{a} Z^{b} U^{†} \in C_{k - 1}

, so that instead of applying a

C_{k}

unitary, we can execute a

C_{k - 1}

unitary. In Eq. (6.24)

U

is a single-qubit unitary, but the same idea works for an

n

-qubit unitary, in which case we essentially do the same operations on each of the

n

qubits in parallel, with the correction depending on a Pauli string of possible measurement outcomes. These gate teleportation protocols are especially useful when it is hard to correctly implement

U

. We can then first try to build the correct

| ψ ⟩

“offline”, until we get the result we require, and then apply it to the state we want by gate teleportation. If the correction operation is then easy, we can just apply that and we are done. For instance, we will see in Chapter 11 that in many fault-tolerant architectures it is difficult to execute a

T

gate, while it is easy to implement Clifford gates. As a

T

gate is in the third level of the Clifford hierarchy, we can implement it with gate teleportation, and its correction will be a Clifford. If instead we want to implement a 4th-level unitary, like

\sqrt{T} = Z (\frac{π}{8})

, its correction will be third-level, which we then also implement with gate teleportation, so that the final correction is a Clifford. Note that we in fact have already encountered a version of

T

gate teleportation in the form of state injection in Section 3.3.1:

Note though that while gate teleportation requires a two-qubit state, magic state injection requires just a single-qubit state, and hence is more efficient. In general, we can do the more efficient ‘magic state’ protocol for a unitary

U

when

U

semi-Clifford, which means that

U = C_{1} D C_{2}

where

C_{1}

and

C_{2}

are Clifford and

D

is diagonal. While there is a nice connection between the Clifford hierarchy and how hard it is to implement a unitary through gate teleportation, in pretty much any other regard the Clifford hierarchy is not very nice at all. In particular, for

k > 2

C_{k}

is not even closed under composition. It is hence not possible to describe the elements of

C_{k}

just by enumerating some small number of generators. In fact, a full characterisation of

C_{k}

for arbitrary number of qubits and

k

is not known.

When we restrict to the diagonal unitaries in

C_{k}

the structure is a lot clearer. In particular, let

D_{k} \subset C_{k}

denote the diagonal unitaries in the

k

th level. Then

D_{k}

is in fact closed under composition and forms a group, and is generated by unitaries of the form:

up to permutations of the qubits. These diagrams implement the unitary

| x_{1}, \dots, x_{n} ⟩ \mapsto e^{2 i \frac{π}{2^{k}} (x_{1} \oplus \dots \oplus x_{n})} | x_{1}, \dots, x_{n} ⟩

and are the focal point of a lot of discussion in the next chapter.

6.6 Summary: What to remember

6.7 References and further reading

Cliffords as normalising the Pauli group The stabiliser formalism was introduced by [111] and further developed, with the help of some amusing examples, in [113]. In the former paper, it was treated mainly as a tool for defining quantum error correcting codes, whereas in the latter as a more general-purpose set of tools for dealing with quantum operations. In Chapter 5 we introduced Clifford unitaries as those built out of Hadamard,

S

and CNOT gates, and now in this chapter we see that they can also be understood to be those unitaries that send Paulis to Paulis under conjugation. Originally, the latter representation came first. That stabiliser unitaries (those that map Paulis to Paulis) can be implemented just using Hadamard, S and CNOT gates was noted in the context of error correcting codes in [27], and a proof was given using symplectic matrices in [44]. A more concrete proof by induction was presented in [112]. The modern form of using a stabiliser tableau to simulate a computation or to produce a normal form for the circuit was presented in [1]. Note that in different papers on this subject the rows and columns of a tableau might be interchanged.

The Clifford hierarchy The notion of a Clifford hierarchy is from [115] where they also introduce the technique of gate teleportation with these gates. A characterisation of diagonal gates in the Clifford hierarchy is given in [67]. That you can do gate teleportation with a smaller ancilla state is the unitary is semi-Clifford is from [238], though the term ‘semi-Clifford’ was only introduced in [119].

Chapter 6Stabiliser theory

6.1 Paulis and stabilisers

6.1.1 Clifford conjugation, a.k.a. pushin’ Paulis

6.1.2 Stabiliser subspaces

6.2 Stabiliser measurements

6.2.1 The Fundamental Theorem of Stabiliser Theory

6.3 Stabiliser states and the Clifford group

6.3.1 Maximal stabiliser groups

6.3.2 Stabiliser states

6.3.3 The Clifford group

6.3.4 Putting it all together

6.4 Stabiliser tableaux

6.4.1 Cliffords are determined by Pauli conjugations

6.4.2 Stabiliser tableaux

6.4.3 Paulis as bit strings

6.4.4 Cliffords as symplectic matrices

6.4.5 Adding back in the phases

6.4.6 Putting it all together

6.5 The Clifford hierarchy

6.6 Summary: What to remember

6.7 References and further reading

Chapter 6
Stabiliser theory