An interpretation of the non-Cliffordness with Pauli channels and rings

This small note take root from a simple question: given a unitary $U$ , how much non-Cliffordness does it actually contain ? The unitary itself is of little help here, as its coefficients mix the Clifford and the non-Clifford parts. This small blog post highlight that switching to the Pauli channel representation, i.e. looking at how an evolution acts on the Pauli matrices rather than on the state, makes this structure explicit. Specifically, Pauli representation shows the number of $1/\sqrt{2}$ in the coefficients is closely related to the non-Cliffordness of the evolution. In this note, each section comes with an animation, this kind of intuition is much easier to build by playing with the Bloch sphere than by reading equations.

Pauli channel representation Link to heading

Unitaries seen from the Pauli basis Link to heading

To begin with, let’s consider a quantum evolution under the Hamiltonian $H$ . Usually, such a quantum evolution is described via its unitary $U = \exp\left(-i \frac{t}{\hbar} H\right)$ , such that $\rho^\prime = U \rho U^\dagger$ . In the FTQC framework, this unitary has to be implemented on logical qubits from a discrete gate-set $G$ , usually Clifford+T. The compilation task is thus to write $U$ as an ordered sequence of gates, $U = g_N \cdots g_2 g_1$ with $g_i \in G$ . What matters here is the Clifford and non-Clifford structure of this sequence: with CSS codes, Clifford gates are cheap while $T$ gates are not. And this is exactly what the unitary hides, its coefficients mix both parts, and reading the structure off $U$ is not trivial.

The community rather uses the Pauli channel representation: instead of describing the evolution as an action of $U$ on the quantum state $\rho$ , we study how such an evolution acts on the Pauli matrices. This intuition has a direct link with Gottesman’s work on stabilizers, where commutation relations are used to describe a state in terms of its stabilizers instead of in terms of kets^[1]. But we will put the stabilizer formalism aside in this small note.

The idea of the Pauli channel representation can actually be understood as a basis switching. By noticing that the Pauli set $\mathcal{P}_n = \{I, X, Y, Z\}^{\otimes n} = \{P_i\}_{i=1}^{4^n}$ is a basis of the $2^n \times 2^n$ matrices (with $n$ the number of qubits), we are able to decompose the state on the Pauli basis instead of on the canonical matrix basis. Concretely, considering a state $\rho$ , the state is described by the coordinates $\alpha_i$ such that

\rho = \sum_i \langle P_i, \rho \rangle \; P_i = \sum_i \alpha_i \; P_i,

with $\langle A, B \rangle = \frac{1}{2^n} \Tr{A^\dagger B}$ the normalised canonical scalar product. Thus, the unitary $U$ acts on the state such that

\rho^\prime = U \rho U^\dagger = \sum_i \alpha_i \; U P_i U^\dagger = \sum_i \alpha^\prime_i \; P_i,

the resulting state $\rho^\prime$ is thus defined with a new set of coordinates $\alpha_i^\prime$ .

From this perspective, we understand the unitary evolution is defined by how the Pauli basis $\mathcal{P}_n$ is affected by $U$ , instead of focusing on the state $\rho$ itself. Concretely, we study how the unitary $U$ transforms the Pauli coordinates

\{ \alpha_i \} \xrightarrow{U} \{ \alpha_i^\prime \},

and the unitary is thus defined via the linear transformation

\forall P_j \in \mathcal{P}_n: \quad U \; P_j \; U^\dagger = \sum_i \beta_{ij} \, P_i.

Or, more conveniently, we use the linear map $\hat{U}$ , called Pauli channel, as the $4^{n} \times 4^{n}$ matrix such that

\hat{U}_{ij} = \langle P_i, U P_j U^\dagger \rangle = \frac{1}{2^n} \Tr{P_i U P_j U^\dagger} = \beta_{ij},

where the $P_i$ are the elements of $\mathcal{P}_n$ , and $\langle \cdot, \cdot \rangle$ is the scalar product defined above.

To get a geometric intuition of such a map, let’s focus on a one-qubit state. Consider a state $\rho$ such that

\rho = \frac{1}{2} \left( I + \alpha_X \; X + \alpha_Y \; Y + \alpha_Z \; Z \right),

where the condition $\Tr{\rho}=1$ imposes the coefficient $1/2$ in front of the identity $I$ . The state can thus be described by a vector $\vec{v} = (\alpha_X, \alpha_Y, \alpha_Z)$ . This description unlocks a 3D representation of the state via the vector $\vec{v}$ , where the basis is given by the Pauli matrices $X$ , $Y$ and $Z$ , and having a pure state imposes $\abs{\vec{v}}=1$ . This description is obviously the well known Bloch sphere description, for instance the state $\ket{0}$ can be written $\ketbra{0} = \frac{1}{2}\left(I + Z\right)$ , thus $\vec{v} = (0, 0, 1)$ .

DefinitionPauli channel

Let $\mathcal{E}$ be a linear map acting on the $n$ -qubit operators. Its Pauli channel representation is the $4^n \times 4^n$ real matrix $\hat{\mathcal{E}}$ of entries

\hat{\mathcal{E}}_{ij} = \frac{1}{2^n} \Tr{P_i \, \mathcal{E}(P_j)}, \qquad P_i, P_j \in \mathcal{P}_n.

Coordinates transform as $\alpha^\prime = \hat{\mathcal{E}} \, \alpha$ , and the composition of two maps becomes a matrix product, $\widehat{\mathcal{E}_2 \circ \mathcal{E}_1} = \hat{\mathcal{E}_2} \, \hat{\mathcal{E}_1}$ . For a unitary evolution $\mathcal{E}(\cdot) = U \cdot U^\dagger$ , the matrix $\hat{U}$ is orthogonal, and the first row and column are fixed by trace preservation.

Clifford operations: inside the octahedron Link to heading

Ok, now we have set the formal description of the Pauli channel formalism, from which the Bloch sphere naturally follows, let’s play a bit with such a formalism in a simple case: the Clifford evolutions. To begin with, we quickly remind the definition of the Clifford set $\mathcal{C}_n$ :

\mathcal{C}_n = \left\{ U \in \SU{2^n} ~ \text{s.t.} ~ \forall P \in \mathcal{P}_n, \; U P U^\dagger \in \mathcal{P}_n \right\},

concretely, a Clifford operation maps a Pauli to another Pauli.

Here we see a direct link with the Pauli channel representation, where the unitary is defined by how it maps the Paulis. Concretely, for any Clifford evolution $U\in\mathcal{C}_n$ , an arbitrary state evolves as

\rho = \sum_i \alpha_i P_i \xrightarrow{U} \sum_i \alpha_i \, U P_i U^\dagger = \sum_i \alpha_i P_i^\prime.

In other words, $U$ permutes the coefficients of the Pauli representation of the state $\rho$ , thus $\hat{U}$ is a permutation matrix. This is what makes Clifford circuits classically efficiently simulable: instead of having a $4^n \times 4^n$ description of $\hat{U}$ , we just have to keep track of the $2n$ permutation across the Clifford evolution.

To develop intuition, let’s move on to a more geometric interpretation with the Bloch sphere (one-qubit scenario). To do so, let’s play a bit with the animation below. Beginning with a state along a Pauli axis, the Bloch vector $\vec{v}$ jumps from one basis vector to another¹ Here the interpretation is straightforward: the Pauli channel representation of a Clifford unitary $U\in \mathcal{C}_1$ is just a permutation, so the evolution will only map the Bloch vector $\vec{v}$ from one Bloch basis vector to another one. Concretely, the vector $\vec{v}$ is thus stuck between six possible vectors: $\pm X$ , $\pm Y$ , and $\pm Z$ , this is the well known octahedron exposed in^[1,2].

TheoremGottesman-Knill theorem

A circuit made of Clifford gates only, applied to a computational basis state and followed by measurements in the computational basis, can be simulated in polynomial time on a classical computer^[2]. Concretely, it can be implemented with a $2n \times 2n$ binary table, completed by $2n$ sign bits, storing the images $U X_k U^\dagger$ and $U Z_k U^\dagger$ of the $2n$ generators of the Pauli group. Since $\hat{U}$ is a signed permutation, these $2n$ images determine the whole map, and each Clifford gate of the circuit updates the table in $\OO{n}$ operations.

Non-Clifford operations: reaching state out of the octahedron Link to heading

As just seen, by only performing permutations on the Pauli operators, Clifford operations make accessible only a few discrete spots in the Bloch sphere, and we understand that we need an extra operation to go out of the octahedron and make reachable the other points of the Bloch sphere. This is actually the role of the non-Clifford operations. Let’s consider the most standard element being the $T$ gate, defined as a $\pi/4$ rotation about the $Z$ axis²

T = R_Z(\pi/4) = e^{-i\frac{\pi}{8}Z}.

Again, the Pauli channel representation highlights the capability of the $T$ gate to get out of the octahedron. For geometrical intuition through the Bloch sphere, we here consider the simple one-qubit scenario. Considering the Pauli $X$ , the $T$ gate maps it to a new direction:

X \xrightarrow{T} \frac{X+Y}{\sqrt{2}},

thus, in the one-qubit scenario, a $\ketbra{+} = \frac{1}{2}\left(I + X\right)$ state becomes $\rho = \frac{1}{2}\left(I + \frac{1}{\sqrt{2}}X + \frac{1}{\sqrt{2}}Y\right)$ , meaning the associated Bloch vector is $\vec{v}=\left(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0\right)$ , which is in fact out of the octahedron. Here we also understand why the $T$ -count makes the classical simulation of a quantum circuit difficult. Each $T$ gate may split one Pauli into two, so that the evolution requires to follow $\OO{2^k}$ Pauli terms, with $k$ the $T$ -count, instead of the $\OO{n}$ Pauli with Clifford circuit.

Clifford+T on the Bloch sphere. The clifford gates permute the Bloch vector

\hat{v}

which is tuck in an octahedron, and applying

T

moves the bloch vector out of it. open full screen ↗

The Matsumoto-Amano normal form Link to heading

Filling the Bloch sphere Link to heading

Great, we now have an operation allowing us to go out of the octahedron, but how to reach an arbitrary point of the Bloch sphere now ? Actually, the $T$ gate alone does not allow such a performance: two consecutive $T$ gates kill the non-Cliffordness by producing a Phase gate one, $T^2=S$ . This was actually expected, as two $\pi/4$ rotations around the $Z$ axis give a global rotation of $\pi/2$ , which is Clifford:

X \xrightarrow{T} \frac{X+Y}{\sqrt{2}} \xrightarrow{T} \frac{1}{\sqrt{2}} \left( \frac{X+Y}{\sqrt{2}} + \frac{Y-X}{\sqrt{2}} \right) = Y.

We thus need an extra rotation to reach any point on the Bloch sphere.

By playing with the Bloch sphere animation, we observe that a succession of $HT$ operations gives an interesting behavior: the trajectory of $\vec{v}$ never comes back on its own steps and looks unpredictable. Thus, non-trivial points of the Bloch sphere become accessible. This can actually be understood by noticing that the $HT$ operation gives a rotation by an irrational multiple of $\pi$ , which unlocks density in the Bloch sphere. More precisely, the word $HT$ unlocks density on a circle of the Bloch sphere, while $SHT$ and $T$ alone allow us to change the axis $\hat{n}$ on which the circle is defined. We thus understand that the words $T$ , $HT$ and $SHT$ unlock density in the Bloch sphere: any point can be reached with an arbitrary error $\epsilon$ by picking a suitable circle-axis $\hat{n}$ (from $T$ and $SHT$ ), and a series of irrational angles (from $HT$ ). This result has actually been noticed by Matsumoto and Amano in 2008, the decomposition on the code-words $\{T, HT, SHT\}$ is now called the Matsumoto-Amano normal form^[3].

T, HT, SHT: the Matsumoto-Amano normal form Link to heading

In 2008, Matsumoto and Amano focused on the representation in the Bloch sphere They show two things:

The $\{T, HT, SHT\}$ decomposition is universal: every single-qubit unitary can be approximated with an arbitrary precision $\epsilon$ within these code-words.
The $\{T, HT, SHT\}$ decomposition is unique: two single-qubit unitaries are equal iff they have the same decomposition. This decomposition is quite important, as the uniqueness tells us that the code-word can be seen as an ID of the operator: each single-qubit unitary has its own decomposition. More importantly, Giles and Selinger developed an algorithm with linear complexity to construct such a decomposition^[4]. They also showed that the decomposition is $T$ -optimal, meaning this code-word decomposition gives a unique way of describing a single-qubit unitary with the minimal number of $T$ gates.

To develop intuition, the animation below allows you to play with such an algorithm. The animation allows you to create a code-word (a combination of $\{T, HT, SHT\}$ ) and simulate the evolution of the qubit through this code-word. To begin with, create a random code-word and play the animation, which shows the evolution-path of the qubit state one word after the other. We directly remark that the trajectory-path seems unpredictable, which is consistent with the intuition of non-simulability: a predictable and orderly trajectory would unlock its simulability with a classical computer. Here it is not the case, adding a code-word leads to a succession of non-trivial rotations, which may be hard to forecast.

Demonstration

HT

is a rotation by an irrational multiple of

\pi

A rotation of angle $\theta$ has trace $1 + 2\cos\theta$ on the Bloch block of the Pauli channel. Here $\Tr{\hat{H}\hat{T}} = -\frac{1}{\sqrt{2}}$ , hence $2\cos\theta = -\frac{2+\sqrt{2}}{2}$ . Assume now $\theta = \pi \frac{p}{q}$ with $p, q \in \Z$ . Then $e^{i\theta}$ is a root of unity, so $2\cos\theta = e^{i\theta} + e^{-i\theta}$ is an algebraic integer. But $2\cos\theta$ is a root of $2x^2 + 4x + 1$ , irreducible over $\Q$ , so its minimal polynomial $x^2 + 2x + \frac{1}{2}$ is not integer-valued. Contradiction: $\theta$ is an irrational multiple of $\pi$ .

Representing orbits of $HT$ in the Bloch sphere. A succession of

HT

gates stays on one circle defined with

\hat{n}

, the orbit never closes and fills that circle. Adding T or SHT at the head tilts

\hat{n}

and moves the circle. open full screen ↗

Counting the $\sqrt{2}$ Link to heading

Non-Cliffordness interpretation via ring theory Link to heading

Here is where things get interesting, we now use arguments on the ring representation of the Pauli channel to see what the $T$ -count of a circuit brings. We quickly recall that a ring is defined with an internal product and an internal addition. More formally, calling $\mathcal{R}$ the ring, we have

+: \mathcal{R} \times \mathcal{R} \mapsto \mathcal{R}, \\ \quad \text{and} \quad \\ \cdot: \mathcal{R} \times \mathcal{R} \mapsto \mathcal{R}.

We use ring representation as we will be focus on the coefficients instead of the matrix itself: for two matrices $A$ and $B$ , $A \cdot B$ is built with sums and products of the coefficients of $A$ and $B$ , thus

\left( A_{ij} \in \mathcal{R} ~\text{and}~ B_{ij} \in \mathcal{R} \right) \implies \left( A \cdot B \right)_{ij} \in \mathcal{R},

and the property of $A$ and $B$ of having their coefficients in $\mathcal{R}$ is conserved through matrix multiplication.

Let’s illustrate with the Clifford evolution. As seen in the previous section, a Clifford $\hat{U}$ is just a signed permutation matrix: its coefficients are $0$ , $-1$ or $+1$ , which all live in the ring $\Z$ . The ring $\Z$ obviously carries way more elements than needed to describe a Clifford, but we keep this representation: what matters here is not how tight the ring is, but where the non-Clifford gates force us to leave it.

Let’s now move to a non-Clifford evolution. We saw that the $T$ gate is precisely what allows us to go out of the octahedron, with

X \xrightarrow{T} \frac{X+Y}{\sqrt{2}},

meaning that in the Pauli channel representation, $\hat{T}$ carries $1/\sqrt{2}$ coefficients, and has therefore left the ring $\Z$ . Concretely, by performing $\pi/4$ rotation on $\ketbra{+}$ , the vector $\hat{v}$ is now pointing in the diagonal between the $X$ axis and $Z$ axis, thus its coordinate is $\hat{v} = (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0)$ , out of the ring $\Z$ , and its associated Pauli channel $\hat{T}$ has its coefficients in

\hat{T}_{ij} \in \Z[1/\sqrt{2}] = \left\{ \frac{a + b\sqrt{2}}{2^k}, ~ a,b \in \Z, ~ k \in \N \right\}.

This is at the heart of non-Cliffordness: $T$ gate makes the Pauli channel out of the ring $\Z$ to reach $\Z[1/\sqrt{2}]$ , and produce arbitrary coefficients $\frac{a + b\sqrt{2}}{2^k}$ , which are dense in the real line

\hat{U}_{ij} = \frac{a+b\sqrt{2}}{2^k} \xrightarrow{k \to \infty} u_{ij} \in \R.

The smallest denominator exponent Link to heading

From the last section, we understand that $T$ gates allow us to get arbitrarily close to any coefficient: as each $T$ gate brings an order $1/\sqrt{2}$ factor in the coefficients $\hat{U}_{ij} = \frac{a + b\sqrt{2}}{2^k}$ of the Pauli channel, we just need to increase $k$ to get higher precision by adding $T$ gates. However, this has to be done wisely, as $T$ gates may cancel each other. For instance, as seen previously, two consecutive $T$ gates kills the non-Cliffordness and bring us back to the boring $\Z$ ring:

X \xrightarrow{T} \frac{X+Y}{\sqrt{2}} \xrightarrow{T} \frac{1}{\sqrt{2}} \left( \frac{X+Y}{\sqrt{2}} + \frac{Y-X}{\sqrt{2}} \right) = Y, \qquad k = 0 \xrightarrow{T} 1 \xrightarrow{T} 0.

Roughly, a $T$ gate replaces two coefficients by their sum and their difference, divided by $\sqrt{2}$ . If the two coefficients carry a different number of $\sqrt{2}$ , the largest one wins and $k$ increases by one: If they carry the same number, their leading parts may cancel out, and $k$ drops instead. Two $T$ gates on the same axis are exactly this second case: the second $T$ recombines the two branches opened by the first one, the $X$ components cancel and the $Y$ components add up to an integer coefficient. Thus, we can have a circuit with a high number of $T$ gates but a small number of $1/\sqrt{2}$ factors, i.e. many $T$ gates are not necessary and may be improved.

This is where we bridge the gap with the Matsumoto-Amano normal form studied before in the one-qubit scenario. Two consecutive $T$ gates kill the $1/\sqrt{2}$ coefficients, but two consecutive $HT$ actually increase their number:

X \xrightarrow{T} \frac{X+Y}{\sqrt{2}} \xrightarrow{H} \frac{Z-Y}{\sqrt{2}} \xrightarrow{T} \frac{Z}{\sqrt{2}} + \frac{X-Y}{2}, \\ \qquad k = 0 \xrightarrow{T} 1 \xrightarrow{H} 1 \xrightarrow{T} 2,

Here the $H$ gate is what prevents the recombination by it sends part of the state on the $Z$ axis, and the denominators no longer cancel, they accumulate. One can show that each $HT$ raises $k$ by exactly one^[3], which is precisely what makes the normal form efficient: the reachable states is refined at each word, and the accuracy on the Pauli channel improves as $1/\sqrt{2}^{k}$ . This also gives an intuition for the unpredictable path noticed on the Bloch sphere: the coefficients of $\vec{v}$ have a strictly growing denominator, so the vector can never land back on a point it has already visited as they carry smaller $k$ . The trajectory cannot close and we recover the point made before, this time by counting $\sqrt{2}$ instead of computing an angle.

Such a number $k$ actually has a name, it is called the smallest denominator exponent (sde). For a nonzero $x \in \Z[1/\sqrt{2}]$ , the smallest denominator exponent $\mathrm{sde}(x)$ is the smallest $k \in \N$ such that

x = \frac{a + b\sqrt{2}}{\sqrt{2}^k}, \qquad a, b \in \Z.

We set $\mathrm{sde}(0) = 0$ , and for a matrix $M$ with coefficients in $\Z[1/\sqrt{2}]$ , $\mathrm{sde}(M) = \max_{ij} \mathrm{sde}(M_{ij})$ .

Given a Pauli channel $\hat{U}$ , this number quantifies how many $1/\sqrt{2}$ factors are needed to implement the unitary, and thus gives a lower bound on its $T$ -count. The argument is direct: a Clifford gate has an integer Pauli channel, so it cannot raise the sde, while a $T$ gate raises it by at most one. A circuit with $t$ gates $T$ therefore has $\mathrm{sde}(\hat{U}) \leq t$ , and $\hat{T}$ is the only way to bring a $1/\sqrt{2}$ in the coefficients of $\hat{U}$ . In the general case, this bound is only lower^[5]. Nevertheless, in the same reference, Gosset et al. showed that the sde coincides with the optimal $T$ -count for the one-qubit scenario.

From this paragraph, we understand how the Pauli channel, together with the ring representation of its coefficients, stores the information on Cliffordness and non-Cliffordness, while the unitary representation does not. Describing the Pauli channel as two integer matrices and one sde $k$ ,

\hat{U} = \frac{A + B \; \sqrt{2}}{\sqrt{2}^k}, \qquad A, B ~ \text{integer matrices},

we get an explicit handle on the non-Cliffordness: it is entirely carried by $k$ .

Reading the $T$ -count on a grid Link to heading

At this point we have set up a great framework showing what the non-Clifford part of an evolution $U$ brings. Let’s now go a bit further in the geometric intuition. Let’s consider a Pauli channel $\hat{U}$ in the one-qubit scenario:

\hat{U} = \frac{A + B \; \sqrt{2}}{\sqrt{2}^k}, \qquad A, B ~ \text{integer matrices}.

As the Pauli channel represents how the Bloch vector $\vec{v}$ evolves under the unitary $U$ , we understand that $k$ controls the precision step accessible in the Bloch sphere.

More precisely, each coefficient is fixed by a pair of integers $(a, b)$ and by the sde $k$ . This pair is the grid: the accessible coefficients are the points of the two-dimensional integer lattice $(a, b)$ , rescaled by $1/\sqrt{2}^k$ , which can be actually transpose to the Bloch Sphere. This is where we understand the role of $T$ , and more specifically of the sde $k$ : raising the sde widens the bounds, adds lattice points, and makes the reachable $\vec{v}$ finer. The number of admissible pairs grows as $2^k$ , so each $T$ gate roughly doubles the set of reachable points. In other words, the precision with which we want to implement an arbitrary evolution is paid in non-Clifford $T$ gates.

The animation below exposes this idea. It shows the grid and the accessible points for a given sde. We see that for a high value of the sde $k$ , more points become accessible and the grid becomes sharper.

Bloch sphere and sde lattice Raising the sde

k

adds lattice points and refines the reachable directions, each T gate roughly doubles them, a precision paid in non-Clifford gates. open full screen ↗

As we focus on the evolution, we are only interested in the difference between the initial state and the final state, thus we can arbitrarily define the reference state in the Bloch sphere, for instance a Pauli axis. ↩
For QEC reasons, especially $T$ gate teleportation, we use the $T$ gate as the standard non-Clifford gate. ↩

References Link to heading

D. Gottesman Theory of Fault-Tolerant Quantum Computation Phys. Rev. A 57, 127-137 (1998) DOI
D. Gottesman The Heisenberg Representation of Quantum Computers arXiv:quant-ph/9807006 (1998) DOI arXiv
K. Matsumoto, K. Amano Representation of Quantum Circuits with Clifford and π/8 Gates arXiv:0806.3834 (2008) DOI arXiv
B. Giles, P. Selinger Remarks on Matsumoto and Amano's Normal Form for Single-Qubit Clifford+T Operators arXiv:1312.6584 (2019) DOI arXiv
D. Gosset, V. Kliuchnikov, M. Mosca, V. Russo An Algorithm for the T-count arXiv:1308.4134 (2013) DOI arXiv