How finely can you divide a depolarizing channel?
Draft under review. Corrections and comments welcome.
This post grew out of my diploma thesis in Quantum Information, which I wrote in Hannover in 2010. The thesis was about quantum memory channels, and in particular about how deep their memory runs. Somewhere inside that work a smaller, self-contained question fell out: how finely can you divide the most destructive process there is?
The original was written for examiners, not for curious readers. I had long meant to rewrite it, and the advent of LLMs finally removed my last excuse. I used them as editorial tools while reorganizing the material, developing examples, and trying out clearer explanations; the mathematical argument comes from the original work, and I checked every derivation myself. The result trades the terse notation of a thesis for pictures, worked examples, and a slower pace intended for motivated undergraduates.
The route, roughly: devices with memory give the problem its physical face, the classical world gives a first answer, and the quantum world a quadratically bigger one. Finally, we settle into a small subclass of all possible channels, simple enough to parameterize by hand, yet powerful enough that in prime dimensions it comes within a factor of two of the full quantum answer: the Clifford channels.
This is a draft under review. If you find an error, a gap, or a passage that does not land, please tell me: in the comments at the end of the post, by highlighting the passage itself with the annotation sidebar at the right edge of the page, or by email through the envelope in the navigation bar.
Enjoy the read.
Take a photograph and make a photocopy. Then a photocopy of the photocopy. Do it again. And again.
If you keep going long enough, the picture is gone. What’s on the page is grey noise that could plausibly have started as almost anything. The information about the original has been erased.
This is a familiar form of loss. Each pass through the copier loses a little, the losses pile up, and eventually nothing remains. Heat works this way too. So does mixing dye into water, or rain working on a pavement chalk drawing. Everywhere you look, processes that destroy information are processes that destroy it in steps: many small irreversible nudges that add up.
Now think about how you’d design such a process. You have full control of the photocopier. The cheap thing you can do is make it violently destructive: a single pass turns any input into grey noise. Erasure in one step. Done.
You can also build copiers that never quite finish in any finite number of passes, and only erase everything in the infinite limit of repeated copying. This is a genuinely interesting region of design space. Characterizing which copiers really do erase everything in the limit (as opposed to settling onto some non-trivial steady image, or oscillating, or simply slowing to a crawl) is the subject of a substantial literature on ergodic and mixing channels.1 It is not, however, the question of this post.
This post’s question sits between those two. How slowly can you erase, while still finishing in finitely many steps?
Concretely: among all copy-of-a-copy operations that erase the original after some exact number k of identical applications, how large can k be?
If you build things for a living, this question may sound backwards. Surely the practical art is protecting information from noise, not erasing it slowly on purpose? But the two are one question wearing opposite uniforms. A bound on how slowly erasure can finish is exactly a bound on how long information can survive inside a process that is guaranteed to kill it: the eraser’s patience and the survivor’s endurance are the same number. Beyond that, I will not pretend this post is engineering. It chases that number for the beauty of where the chase leads; stay to the end and you will watch the question turn into the arithmetic of finite groups and finite fields, applied to a single-particle quantum system.
There’s a second way to picture the same question, and it’s the one that makes the problem feel physical. A quantum device you use over and over (a logic gate, a link down a fibre) need not treat each use independently: it can carry a private memory from one use to the next, a lingering excitation or stray correlation that makes what it does now lean on its history. Such a device is forgetful when the influence of how that memory started eventually washes out (the asymptotic case from a moment ago), and strictly forgetful when the washout is exact, every trace of the initial memory provably gone after some finite number of uses. Not small, gone.
And with no separate input to track, a device that becomes strictly forgetful after exactly k uses is nothing but a k-th root of complete erasure.2 To ask how finely we can divide erasure is to ask how long a finite quantum memory can survive before it is forced to forget exactly, and the largest k is the deepest such memory a device of this kind can hold.
That largest k is where this post lives, and it has different answers in different settings. If the copier has to behave like a classical probabilistic process, you get one bound. Upgrade to quantum mechanics, and the bound becomes quadratically larger. Then restrict the quantum copier to a tightly constrained, low-parameter family of operations, a family with vastly less freedom than the general quantum case, and you might expect the bound to drop most of the way back down.
It almost doesn’t. The constrained family gives up a factor of two, and nothing more. Why so little freedom costs so little is the most instructive part of the whole story, and the answer sits in the structure of finite fields and how they are represented by matrices.
The classical setup
Let’s make the photocopier mathematically precise. We start with the classical case, where everything is ordinary probability theory.
Pick a small number of distinct states your image can be in. Say three, and to keep them vivid, call them red, green, and blue. At any moment a pixel of the image need not be one definite colour. Noise has crept in, and the honest description is a list of how likely each colour is. Right now it might be definitely red. After a few passes through the copier, it might be 40% red, 50% green, 10% blue.
We write that list as a vector. Definitely red is (1, 0, 0); the blurred state is (0.4, 0.5, 0.1), read in the order red, green, blue. Two rules turn a list of numbers into a probability distribution, and we lean on both later. The entries cannot be negative, since a probability below zero is meaningless. And they must sum to one, since the pixel is certainly some colour. Every classical state we write obeys these two rules, and nothing else counts.
Now picture all the lawful states at once. With three colours a state is three numbers summing to one, so fixing any two pins the third: only two are free. Two free numbers trace out a flat, two-dimensional shape, and that shape is a triangle. Its three corners are the sure things, one per colour: (1,0,0) is definitely red, (0,1,0) definitely green, (0,0,1) definitely blue. Walk along an edge joining two corners and the third colour stays impossible while the other two trade off. Drift inward and the three probabilities become more balanced, until at the dead centre you reach (\tfrac13, \tfrac13, \tfrac13): an even wash of red, green, and blue with no colour favoured, the state that could have come from anything. That even wash is exactly the grey noise from the start of this post, the worn-out photocopy written as a vector, and pushing every corner toward it is the whole job of an erasing copier. The triangle has a name, the simplex, and for d states it becomes the (d-1)-dimensional version of the same idea (Figure 1).
Probability simplex over three outcomes, coloured by purity (blue-teal at the pure corners, fading to a soft blue-grey centre at the maximally mixed distribution p0, which is marked and labelled at the centroid).
A copy operation takes one probability distribution as input and returns another. Before we write down what kind of object such an operation is, it is worth asking what we want to insist on.
The first thing is linearity. The copier S has to be a linear map: if you feed it a coin-flip mixture of two inputs, the output has to be the same coin-flip mixture of the two separate outputs. Anything else would let the copier react to information beyond what the input distribution actually contains, which is a contradiction in terms.
Why must mixtures behave this way?
Suppose you decide your input on the flip of a coin: with probability \alpha you start from distribution p, and with probability 1 - \alpha you start from q. The total input, before you flip the coin, is the mixture \alpha p + (1 - \alpha) q.
Apply the copier S. You can describe what comes out in two ways. From inside the experiment, the output is “S(p) with probability \alpha, S(q) otherwise,” which is the distribution \alpha S(p) + (1 - \alpha) S(q). From outside, ignoring the coin flip, you simply fed the copier a single mixture, so the output is S(\alpha p + (1 - \alpha) q).
These two descriptions had better agree: S\bigl(\alpha p + (1 - \alpha) q\bigr) \;=\; \alpha S(p) + (1 - \alpha) S(q). If they disagreed, “the input is a probability distribution” would stop meaning what we want it to mean. So S is linear.
A linear map of vectors is exactly a matrix, so from here on our copier is a matrix, which we will call S, and applying it to a distribution is ordinary matrix-times-vector multiplication.
It is worth seeing what that does to our three corners, because it pins down the whole matrix. Feed in pure red, the vector (1, 0, 0). Multiplying S by a vector that is all zeros except for a single one just reads off the matching column, so the output is the first column of S: whatever S does to red lives there. Pure green (0, 1, 0) picks out the second column, pure blue (0, 0, 1) the third. The three columns of S are therefore nothing but the images of the three pure states, the three places the corners are sent, and once those are fixed linearity supplies every blend in between.
That already constrains the entries. Each column is the image of a pure state, and that image has to be a legal state in its own right: its entries non-negative and summing to one, S_{ij} \geq 0, \qquad \sum_i S_{ij} = 1. The same holds for every column, and linearity then takes care of every mixture in between. A matrix of this kind, non-negative entries with every column summing to one, is called a stochastic matrix: exactly the linear maps that send probability distributions to probability distributions.
There is one more restriction we will impose, and in retrospect it is the most interesting one. We will only consider copiers that leave the uniform distribution untouched, the grey centre of the triangle from a moment ago: the flat distribution that puts equal weight on every state has to come back out exactly as it went in.
Why? The uniform distribution is the symmetric point of the simplex, the one distribution that treats every colour exactly alike. It is also the destination. The grey centre is exactly where an erasing copier is trying to send everything, so a process whose job is to forget should come to rest there once it arrives, not stir the grey back into a sharper image. A copier that moved the centre would be privileging some outcomes over others, a bias built into the dynamics rather than read from the input, and leaving the grey centre fixed is the natural way to rule that out. (In the quantum upgrade later in the post, the analogous restriction is more than just natural, it is the standard convention. For now, take it as a sensible thing to ask for; in a moment it will reveal itself as no restriction at all.)
This small demand has a tidy consequence. We already know the columns of S sum to one. Insisting that the uniform distribution survives forces the rows to sum to one as well. A stochastic matrix with that extra symmetry is called bistochastic, and from here on “copier” will mean “bistochastic matrix.”
The one-line computation
Write u = (1/d, \ldots, 1/d) for the uniform distribution and ask for Su = u. Reading off entry i of the output, (Su)_i \;=\; \sum_j S_{ij} \cdot \frac{1}{d} \;=\; \frac{1}{d} \sum_j S_{ij} \;\overset{!}{=}\; \frac{1}{d}, which is exactly \sum_j S_{ij} = 1 for every row i.
One small fact worth pinning down before we go further: the product of two bistochastic matrices is bistochastic, which you can verify directly from the row and column sum conditions. So S^k stays bistochastic for any k, and the question of finite roots is going to be a question about powers of matrices that stay safely inside our chosen class.
Now we can say precisely what “total erasure” means. The most depolarizing copier you can write down is the one whose every column is the uniform distribution. Every input state, no matter which one, produces the same uniform output: P = \frac{1}{d}\begin{pmatrix} 1 & 1 & \cdots & 1 \\ 1 & 1 & \cdots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \cdots & 1 \end{pmatrix}.
Apply P to anything and you get the uniform distribution back. All information about the input has been thrown away in a single step. Apply P again and nothing changes: the simplex has contracted to a single point, the centre, and P just keeps mapping it there. This P is bistochastic by inspection (every row sums to one as well), and it is the completely depolarizing channel in dimension d, or CDC for short.
With P pinned down, the question we opened with stops being a story about photocopiers and becomes one line of mathematics. The copier that erases in steps, the demand that it finish after exactly k identical passes: all of it is now this. Here k is a positive integer, the number of passes. A k-th root of P is a bistochastic matrix S for which \boxed{\; S^k = P, \qquad S^j \neq P \ \text{ for every integer } 1 \le j < k. \;} Spelled out: apply the copier S exactly k times and you get P, total erasure; apply it any smaller number of times and the erasure has not happened yet. The first equation is the whole post in miniature, a single copier that erases totally in k identical steps; the second pins k down as the exact number, and that exact k is called the order of the root. Everything from here on is the hunt for such an S with k as large as possible, and the difficulty (and the beauty) is finding a non-trivial one, an S that is not simply P itself.
And here the restriction we imposed by hand grants itself. Suppose S were merely stochastic, columns summing to one, rows unconstrained, and satisfied S^k = P. Multiply one more copy of S onto that equation, once on each side: both products are S^{k+1}, so SP = PS. Now feed any distribution p through both sides. The right side copies first and then erases, P(Sp) = u, the uniform distribution, no matter what Sp was. The left side erases first and then copies once more, S(Pp) = Su. So Su = u: every stochastic root of P fixes the uniform distribution of its own accord, rows summing to one and all. Bistochasticity is not a fence we built around the hunt. It is a property every candidate already has, and demanding it up front just names the terrain honestly.
Before hunting, notice where the teeth of the problem are. Finding some matrix with S^k = P is a linear-algebra exercise. The demand with teeth is that S must be a lawful copier: entries non-negative, every column summing to one, and, by our standing rule, every row as well. The hunt is always for the largest order inside the set of lawful matrices, and it is worth marking the non-negativity half of that checklist now. It looks like the tamest of the conditions. It returns in every setting of this post, wearing a different name each time, and in the quantum world it will grow into the main obstacle of the whole story. How large can k be?
The smallest case settles itself. A two-state bistochastic matrix has a single free number, S = \begin{pmatrix} 1-a & a \\ a & 1-a \end{pmatrix}, and P is the case a = \tfrac12. Its one direction away from the grey centre, v = (1,-1), is merely rescaled, Sv = (1-2a)\,v, so S^k scales it by (1-2a)^k. Asking S^k = P forces (1-2a)^k = 0, and a number powers to zero only if it was already zero. So a = \tfrac12 and S = P from the start: one classical bit has no genuine root, k = 1, erasure in a single shot.
Three states are the first with room to spare, and the clean way to find that room is to stop guessing whole matrices and split off the part that does the forgetting. Every copier in our class fixes the grey centre, so write S = P + N, with P the completely depolarizing channel and N whatever is left over. Two facts about P make this split pay off. It is idempotent, P^2 = P, and it absorbs N from both sides, PN = NP = 0 (the columns of N sum to zero because those of S and P both sum to one, and its rows sum to zero because S fixes the uniform state). Square S and the cross terms vanish: S^2 = (P + N)^2 = P^2 + PN + NP + N^2 = P + N^2. The question has collapsed. S^2 = P holds exactly when N^2 = 0. We no longer need a square root of P; we need a single nonzero N that squares to zero and keeps P + N a legal copier.
So solve N^2 = 0 directly. The condition is stricter than it looks. If N squares to zero it can have rank at most one, which means it is a single outer product, N = u\,v^{\mathsf T}, and then all three demands become conditions on the two vectors alone: N^2 = 0 \iff v^{\mathsf T} u = 0, \qquad \textstyle\sum_i u_i = 0, \qquad \textstyle\sum_j v_j = 0, the last two being the vanishing column and row sums. In words: take any two vectors that are orthogonal and that each sum to zero. That is the whole recipe.
Why $N^2 = 0$ forces rank one
If N^2 = 0 then N sends everything into its own kernel: for any x, N(Nx) = 0, so \operatorname{im} N \subseteq \ker N. Their dimensions add to the full size, \operatorname{rank} N + \dim \ker N = d, so \operatorname{rank} N \le \dim \ker N = d - \operatorname{rank} N, which gives 2\operatorname{rank} N \le d. For d = 3 that forces \operatorname{rank} N \le 1, a single outer product u\,v^{\mathsf T}.
The simplest such pair is small and concrete: u = (1, -1, 0), \qquad v = (1, 1, -2), orthogonal, each summing to zero. Their outer product, scaled by \tfrac16 so that P + N stays non-negative, is N = \frac{1}{6}\begin{pmatrix} 1 & 1 & -2 \\ -1 & -1 & 2 \\ 0 & 0 & 0 \end{pmatrix}, and adding it to P gives an honest copier, S = P + N = \begin{pmatrix} 1/2 & 1/2 & 0 \\ 1/6 & 1/6 & 2/3 \\ 1/3 & 1/3 & 1/3 \end{pmatrix}, non-negative, with every row and column summing to one. By construction S^2 = P + N^2 = P while S \ne P, so this S is a genuine square root of total erasure: a copier that erases a three-state image in two equal steps rather than one, funnelling every point along a two-step path to the grey centre (Figure 2). It is one especially simple member of a continuous family of such roots (any orthogonal pair of zero-sum vectors, scaled gently enough, gives another), and it is the member drawn in the figure.
That same split hands us the general bound for free. For any S = P + N in our class the cross terms always die, so S^k = P + N^k, and S^k = P exactly when N^k = 0. Erasing in exactly k steps is nothing more than N being nilpotent of order k, and a nilpotent map on the (d-1)-dimensional space of deviations from the grey centre runs out of room after at most d - 1 steps. So the bound is k \le d - 1, already reached at d = 3 by the matrix above. (In the quantum upgrade these deviations become the traceless operators, the same idea in matrix language.)
Why the bound is reached in every dimension
A nilpotent N is governed by its Jordan form, a stack of blocks each of which powers to zero in exactly its own size. The largest block that fits on the (d-1)-dimensional space of deviations is a single (d-1) \times (d-1) block with ones on the superdiagonal, N \;\cong\; \begin{pmatrix} 0 & 1 & & & \\ & 0 & 1 & & \\ & & \ddots & \ddots & \\ & & & 0 & 1 \\ & & & & 0 \end{pmatrix}. That matrix is a representation of N, and the basis is ours to pick. The deviations are exactly the orthogonal complement of the maximally mixed state, so any orthonormal basis of that complement will do, and nothing in the argument depends on which one we take.
Each power pushes that diagonal of ones one step toward the corner, so N^{d-1} = 0 while N^{d-2} \neq 0.
The row and column sums of P + \varepsilon N are right by construction, so only non-negativity can fail. Since every entry of P is 1/d, the explicit sufficient condition |\varepsilon| \;\leq\; \frac{1}{d \, \max_{i,j} |N_{ij}|} keeps every entry 1/d + \varepsilon N_{ij} non-negative. For an orthonormally represented Jordan shift, \|N\|_2 = 1, hence |N_{ij}| \leq 1, and the simpler dimension-only choice |\varepsilon| \leq 1/d suffices. Scaling leaves the nilpotency order untouched because (\varepsilon N)^k = \varepsilon^k N^k. In the d = 3 example, the unscaled outer product has largest entry 2, giving exactly |\varepsilon| \leq 1/6. Thus the block yields a root of order d - 1 in every dimension.
Animation of the square-root channel S on the probability simplex. A cloud of states, coloured by its red-green-blue mixture, is mapped by S onto a line segment (the 2D simplex collapses to 1D), then by a second S onto the single grey maximally mixed point (1D collapses to 0D). The three pure corners e1, e2, e3 trace highlighted paths; e1 and e2 merge onto the same intermediate point. Tap the figure to play the animation.
Tap to play.
And that is the classical story. A clean bound, a clean construction, and not much more to say about it.
The interesting thing is what happens to that bound when we let ourselves leave classical probability behind.
The quantum upgrade
Everything so far was a rehearsal. The real question is about quantum information, and a quantum state carries more than a classical probability distribution does. More in a way we can count, and the count turns out to be the whole plot of this section.
Go back to the smallest example. A classical bit is one number: how a coin is weighted between its two outcomes, 0 and 1. Picture that number as a position on a line segment. The two ends are the only certain states, “definitely 0” and “definitely 1”; every point between is a blend, more or less uncertain, with the fair coin sitting at the dead centre. One number, one dimension of freedom.
A quantum bit, a qubit, has more room, and the cleanest way to see how much more is to ask what its certain states are. (Quantum mechanics also allows genuine superpositions, the \alpha\,|0\rangle + \beta\,|1\rangle of the amplitude picture,3 but for a story about forgetting we want the geometry of states, not the algebra of amplitudes.) Classically there were exactly two certain states, the two ends of the line. A qubit has infinitely many. That is one of the genuine surprises of quantum mechanics, and not one this post can derive; we take it as given and simply draw it. The certain states no longer sit at two points. They fill the entire surface of a ball.
This is not a mathematical fiction. Two everyday incarnations make it concrete. The polarization of a photon is a qubit: a filter aligned with it passes the photon every time, a filter at right angles blocks it, and one at 45^\circ lets it through half the time. So is the spin of an electron: point a detector along the spin and you always read the same way, turn the detector sideways and the outcome goes random. In each, the certain states are not two but a whole continuum, one for every direction on the Bloch sphere.
That continuum is the surface of the qubit’s state space, the Bloch ball (Figure 3). Picture a state as an arrow inside the ball, with a direction and a length. The length says how certain the state is: arrows reaching the surface are the certain, pure states, shorter arrows are blurrier mixtures, and the zero-length arrow at the dead centre is total ignorance, the quantum coin flip. The direction says which question the state answers with certainty. Every direction names a measurement you could make, and the state pointing that way is the one whose outcome you can predict. The poles are the ordinary question, “are you 0 or 1?”, and the classical bit’s two states sit there. A state out on the equator answers that question with a perfect coin flip, yet is itself perfectly definite, just for a different question. Ask a qubit the wrong question and the answer turns random; that, and not fuzziness, is what the surface is encoding.
The object that bookkeeps this arrow is a small matrix, the density matrix, and for a qubit it is small enough that we will shortly write it out whole and watch the ball fall out of it.
Interactive Bloch ball, the qubit state space. Click the front of the ball to pick a direction; the Purity slider moves the state from the pure surface inward toward the maximally mixed centre. A readout names the one yes/no measurement the state answers with certainty, and how that certainty fades as the state becomes mixed.
Pick a direction on the ball to read off the one measurement it answers with certainty.
Notice what happened to the dimension. The classical bit lived on a line, one dimension; the qubit fills a ball, three. Where does three come from? For a qubit, nothing has to be taken on faith, because the promised bookkeeping matrix is small enough to write out entry by entry, with the arrow (x, y, z) filed inside it: \rho \;=\; \begin{pmatrix} \dfrac{1 + z}{2} & \dfrac{x - iy}{2} \\[6pt] \dfrac{x + iy}{2} & \dfrac{1 - z}{2} \end{pmatrix}. Look at how little freedom the grid has. The two diagonal entries are real and sum to one, so a single number, z, fixes both. The two off-diagonal entries are mirror images of each other across the diagonal (complex conjugates), so a single complex number, worth two real ones, fixes that pair. Three free real numbers in all, and they are exactly the coordinates of the arrow. The ball’s three dimensions are not a metaphor. They are the room this matrix has.
The matrix even knows the ball is round. Its two eigenvalues work out to \tfrac12(1 \pm \ell), with \ell = \sqrt{x^2 + y^2 + z^2} the length of the arrow (a two-line computation, done in the aside below), and the eigenvalues of a density matrix are the probabilities it carries, a point made precise in a moment. Probabilities cannot go negative, so \ell \le 1: one inequality, and it carves the solid ball out of space. The surface is \ell = 1, eigenvalues 1 and 0, some question answered with certainty, which is why the certain states live exactly there; the zero-length arrow at the centre has eigenvalues \tfrac12 and \tfrac12, the fair coin. And file one promise away as you look at the grid: in the next section each of the three directions will get a matrix of its own, and the way those matrices multiply carries the rest of the post.
The two eigenvalues, computed
Two numbers pin down two eigenvalues: their sum and their product. The sum is the trace, 1 by inspection of the diagonal. The product is the determinant, \det \rho \;=\; \frac{(1 + z)(1 - z)}{4} - \frac{(x - iy)(x + iy)}{4} \;=\; \frac{1 - (x^2 + y^2 + z^2)}{4} \;=\; \frac{1 - \ell^2}{4}. The matrix is Hermitian, so both eigenvalues are real, and the pair with sum 1 and product \tfrac14(1 - \ell^2) is \lambda_\pm \;=\; \frac{1 \pm \ell}{2}, as multiplying them back out confirms. Demanding \lambda_- \ge 0 is exactly demanding \ell \le 1: the ball.
That jump, one dimension to three, is the pattern worth chasing, but to count it for any number of levels we first have to say what a quantum state even is beyond the qubit.
For d levels the bookkeeping object is the same kind of thing as the grid we just unpacked: a d \times d matrix, the density matrix at full size, and its rules are not arbitrary. They are exactly what it takes to still be describing probabilities. The matrix is Hermitian, mirror-conjugate across the diagonal just like the qubit’s, so its eigenvalues are real; those eigenvalues are non-negative and sum to one. That last clause is the point, because non-negative numbers summing to one are a probability distribution. So each density matrix carries a classical probability distribution inside it: the eigenvalues are the probabilities, and the eigenvectors say which mutually exclusive pure states they are spread across. But the basis belongs to the state, and that is where the quantum content lives: two density matrices need not agree about which alternatives they are distributions over, and when they disagree they do not commute. The classical simplex from the first half of this post is the special case where one common set of axes has been fixed once and for all.
Now we can count. A quantum state in dimension d is pinned down by d^2 - 1 real numbers, the qubit’s three being the case d = 2.
Where $d^2 - 1$ comes from
A d \times d Hermitian matrix is fixed by d^2 real numbers: d real numbers on the diagonal, plus the entries above the diagonal, each complex and so worth two reals, with everything below the diagonal forced by Hermiticity. The off-diagonal count is 2 \cdot \tfrac{d(d-1)}{2} = d(d-1), and d + d(d-1) = d^2. Fixing the trace to one removes a single degree of freedom, leaving d^2 - 1.
So the quantum state space is (d^2 - 1)-dimensional, against the classical simplex’s d - 1. For a single bit, three against one. The freedom grew quadratically, and every result in this post is a shadow of that one fact.
The rest of the cast carries over almost unchanged. A quantum copier is a channel: a linear map that turns density matrices into density matrices. It has to be linear for exactly the reason it was classically, that a coin-flip mixture of inputs must come out as the same coin-flip mixture of outputs. And the classical lawfulness checklist survives the upgrade, renamed. Non-negative entries grow into positivity: a channel must keep the density matrix’s eigenvalues non-negative, so that they can stay probabilities. Columns summing to one grow into trace preservation, the matrix version of “the outcomes still add up to one”. (Row sums, our standing fixed-centre rule, return in a moment.) Only one word of the checklist is genuinely new. The positivity demand sharpens to complete positivity: the map must keep sending valid states to valid states even when it acts on only part of a larger entangled system, a failure mode classical probability simply does not have. Channels are well-understood objects with a clean structure theory.4 For us they are simply the right notion of “physically allowed operation,” and we will not pry them open.
We make the same restriction we made classically. Out of all channels we keep the ones that leave the state of total ignorance untouched. Classically that was the uniform distribution. Here it is the maximally mixed state, the centre of the Bloch ball, written I/d with I the identity matrix. A channel that fixes it prefers no state to any other, which is the least we should ask of a process whose only job is to forget. (Such channels have a name, unital, but the name matters less than the picture.)
Total erasure is the same idea as before, too. The completely depolarizing channel sends every input, no exceptions, to the maximally mixed state. The whole Bloch ball collapses to its centre point in a single step. This is the quantum CDC, and it is the operator we now want to take roots of.
The classical bonus survives the upgrade word for word. The argument that any stochastic root of the classical P fixes the uniform distribution used nothing but SP = PS and the fact that P erases everything, and both survive here. So any trace-preserving channel root of the quantum CDC fixes the maximally mixed state of its own accord: unitality, like bistochasticity before it, is not a restriction on the hunt but a property every candidate brings along.
Here is where that quadratic shows up where it counts. Ask the same question as in the classical case: how large can k be, if a channel S satisfies S^k = P but no smaller power does? The argument has the same skeleton. The quantum CDC is again a rank-one map, rank one as a linear map on the d^2-dimensional space of operators: it sends the entire space of traceless operators, the directions away from the maximally mixed state, to zero. Any S powering to it must carry a nilpotent part on that space, and a single nilpotent block on a space of dimension D takes at most D steps to wind down. Only now D = d^2 - 1 rather than d - 1, so k \;\leq\; d^2 - 1.
Why the bound is reached in every dimension
Work with operators instead of probability vectors. Let D = d^2 - 1 and pick a basis of Hermitian matrices I/\sqrt{d},\, F_1, \ldots, F_D with every F_j traceless, orthonormal in the trace inner product \langle A, B \rangle = \operatorname{tr}(A^\dagger B). Let N shift the list: N(I) = N(F_1) = 0, \qquad N(F_j) = F_{j-1} \quad (2 \le j \le D), so N^D = 0 while N^{D-1} \neq 0: the operator F_D survives D - 1 steps. Set S_\varepsilon = P + \varepsilon N. Trace preservation and unitality hold by construction, since N kills the identity and outputs only traceless operators, and the same two facts give PN = NP = 0. The cross terms die exactly as they did classically, S_\varepsilon^k \;=\; P + \varepsilon^k N^k, so every nonzero admissible \varepsilon keeps the maximal order D.
Only complete positivity can still fail, and the check mirrors the classical non-negativity argument. Complete positivity of a map is the positive semidefiniteness of a single matrix assembled from it, its Choi matrix J (part of the structure theory in the footnote above), and J depends linearly on the map: J(S_\varepsilon) \;=\; J(P) + \varepsilon\, J(N). In the convention J(T) = \sum_{ij} T(|i\rangle\langle j|) \otimes |i\rangle\langle j|, the completely depolarizing channel has J(P) = I_{d^2}/d, with I_{d^2} the identity on the doubled, d^2-dimensional space: strictly positive definite, the quantum counterpart of “every entry of P is 1/d”. A Hermitian perturbation cannot drag an eigenvalue below zero while |\varepsilon| \;\le\; \frac{\lambda_{\min}(J(P))}{\|J(N)\|_{\mathrm{op}}} . With the basis above, \|J(N)\|_{\mathrm{op}} \le d^2 - 2: the Choi matrix of the shift is a sum of d^2 - 2 terms F_{j-1} \otimes \overline{F_j}, each of operator norm at most one, because a Hermitian matrix of unit Hilbert-Schmidt norm has operator norm at most one. So the dimension-only choice |\varepsilon| \;\le\; \frac{1}{d\,(d^2 - 2)} suffices, and the shifted block, shrunk gently, is a lawful channel of order exactly d^2 - 1 in every dimension. The polished version of this construction is Theorem 3.4 of the paper.5
Set d = 2. The classical bound was k \leq 1: a single bit could not be erased in more than one step. The quantum bound is k \leq 3. Three gentle steps to forget one qubit (Figure 4), where one classical bit allowed only the abrupt single step. The room to subdivide erasure grew, and it grew quadratically.
Animation of the maximal qubit root S on the Bloch ball. A cloud of Bloch vectors is driven by S to the maximally mixed centre I/2 in stages, each step shrinking and rotating it onto the next axis (z to y to x to 0). Three pure axis states are highlighted: the z-pole takes three steps (the hero, realizing the order-3 bound), the y-axis two, the x-axis one. Tap the figure to play the animation.
Tap to play.
The unrestricted answer is therefore d^2 - 1, ceiling and construction both: the aside above delivers a channel of exactly that order in every dimension. How much of that quadratic scaling survives inside a far more rigid family? That is the question with life left in it, and the rest of the post lives in a smaller room: a family of channels with a handful of parameters in place of the full continuum, one that has proved fruitful before across quantum information, and simple enough that the question yields to direct computation. Building the room takes a little construction work, and the construction starts further back than you might expect.
Rebuilding the qubit from the bit
Two settings are closed, and it is worth reading the scoreboard before opening a third. Both times the same skeleton carried the argument: split the copier as P + N, watch the cross terms die, and read the largest order off the size of the space N has to wander in. Classically that space was the set of deviations from the grey centre, of dimension d - 1. Quantum mechanically it was the traceless operators, of dimension d^2 - 1. Both bounds were reached, and both times the part of the argument with teeth was not the order but the lawfulness check, non-negative entries in one world and complete positivity in the other, paid off by shrinking the nilpotent part until the check went through.
| Classical | Quantum | Clifford | |
|---|---|---|---|
| Copiers considered | bistochastic matrices | channels fixing the centre I/d | a rigid subfamily, built below |
| Free parameters | (d-1)^2 | (d^2-1)^2 | a finite choice, plus d^2 - 1 scale factors |
| The condition with teeth | non-negative entries | complete positivity | complete positivity, as one explicit matrix |
| Largest order k | d - 1 | d^2 - 1 | ? |
| Reached by | a nilpotent N on the deviations, scaled gently | a nilpotent N on the traceless operators, shrunk until the Choi matrix stays positive | ? |
| Seen in action | d = 3, two steps (Figure 2) | d = 2, three steps (Figure 4) | ? |
So why open a third column when the second is closed? Because the quantum construction settles the number and shows no structure. A Jordan block on the traceless operators, in any orthonormal basis you care to pick, shrunk until the Choi matrix stays positive, is an existence proof. It certifies that d^2 - 1 steps of room are there and is indifferent to everything else: the axes are arbitrary, and lawfulness is settled by an inequality rather than seen. The family this section builds, the Clifford channels, is a room small enough for the mechanism to sit in plain view. Inside it the non-commutativity of quantum mechanics is packaged as bookkeeping on a finite grid of labels, the root problem turns into a board game on that grid, and complete positivity, the condition that separates channels from mere linear maps, becomes the positivity of one matrix whose entries are the channel’s own parameters.
Nor is the family a toy invented for the occasion. The bit-flip, dephasing and depolarizing noise models that quantum error correction is built to fight are all members, so the question of how slowly such noise can erase has standing of its own. And the payoff is the surprise promised in the hook. Rigidity turns out to cost almost nothing: in prime dimensions the family gives up a factor of two against the full quantum bound, and nothing more. Where that factor comes from, and why the drop is not most of the way back to the classical d - 1, is the rest of the post.
Where should the building start? Look once more at the Bloch ball of Figure 3, because something classical is hiding in plain sight. The two states of an ordinary bit sit at the poles. The straight line between them, running through the centre, is the entire state space of the classical bit: the segment from the very start of this post, with its two certain ends and its ignorant middle. The quantum ball did not replace the classical picture. It grew around it.
That is worth taking seriously, because it says which way round to build. The previous section went at the space of all quantum channels from the top and got its number by shrinking a block until an inequality held. This time we go the other way around. Start from the classical bit, the smallest state space we own, and take the smallest step that turns it quantum, keeping both hands on the algebra the whole way. By the end of the section that small step will have produced a coordinate system for the qubit, a family of channels that respects those coordinates, and a rederivation of the three-step eraser of Figure 4: not pulled from a hat this time, but designed, with every choice visible.
Begin with the bit, dressed in matrix clothes. A classical bit is a probability p of reading 0 and 1 - p of reading 1, and its density matrix is diagonal: \rho \;=\; \begin{pmatrix} p & 0 \\ 0 & 1-p \end{pmatrix} \;=\; \tfrac12\bigl(I + r\,Z\bigr), \qquad r = 2p - 1 . Two matrices carry the whole classical story: the identity I, and Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}. As p sweeps from one to zero, r slides from +1 down to -1, and \tfrac12(I + rZ) traces out exactly the vertical diameter of the Bloch ball. So I and Z are a basis for the classical states: every state of a bit is a combination of these two matrices, and nothing else is needed.
That is the first role the two matrices play. Here is the second, and it looks almost too small to mention. Give them labels: attach 0 to I and 1 to Z, writing \sigma(0) = I and \sigma(1) = Z. The labels add modulo 2, the arithmetic of even and odd; as a group this label set is called \mathbb{Z}_2. Now multiply the matrices and watch the labels. Z \cdot Z = I, which is 1 + 1 = 0. I \cdot Z = Z, which is 0 + 1 = 1. Multiplication upstairs is addition downstairs, exactly, with nothing left over. An assignment with this property is called a representation of the group. Nor is the label on Z a choice we made. Read down its diagonal: +1 at the outcome 0, -1 at the outcome 1, the parity (-1)^x of the outcome x, while the diagonal of I is the constant (-1)^{0 \cdot x}. The label is the exponent b in (-1)^{bx}, and multiplying the matrices multiplies these entries, which adds the exponents. The representation was handed to us by the bit. For the moment this is idle bookkeeping. It is also the seed of everything below.
To watch the bookkeeping earn its keep, take the one copier family we have already solved and translate it. The two-state copier from the classical section was S = \begin{pmatrix} 1-a & a \\ a & 1-a \end{pmatrix}, copying faithfully with probability 1 - a and flipping with probability a. In matrix clothes its entire action collapses to two statements: T[I] = I, \qquad T[Z] = (1 - 2a)\, Z . The identity is left alone, and Z is multiplied by a number. That is the whole copier. (The vector v = (1, -1) that carried the classical computation back then is nothing but the diagonal of Z.) And the classical no-root theorem, the fact that a bit cannot be erased gently, becomes a single sentence: applying T repeatedly multiplies Z by (1-2a)^k, and a product of copies of one number vanishes only if that number was zero from the start. One label beyond the identity, one number attached to it, no room to manoeuvre. Keep this template in view: a copier in these coordinates is a rule for the labels plus a number per label. The rest of the section is that sentence, rerun with better ingredients.
Is this the only way \mathbb{Z}_2 can sit inside the 2 \times 2 matrices? It is not, and the second way needs no new ingredient. So far the addition table of \mathbb{Z}_2 has been applied to the labels. Apply it to the outcomes instead: adding 1 sends the outcome 0 to 1 and the outcome 1 to 0. That is the flip. On a probability vector it moves the weight of each outcome onto the other, (p_0, p_1) \mapsto (p_1, p_0), and the matrix that does this is X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, a plain permutation matrix. It is Hermitian, and X^2 = I: flipping twice is doing nothing, which is 1 + 1 = 0 once more. So a \mapsto X^a is a second representation of the very same group, and it was there from the start, in the group law itself. In the classical family above it sits at the corner a = 1, the copier that flips every bit with certainty.
Notice how the two representations kept apart in the classical world. The states of the bit live in the span of I and Z. The copiers live in the span of I and X: the two-state copier S is the matrix (1 - a)\, I + a\, X, a mixture of doing nothing and flipping. One representation spans what the bit is, the other what can be done to it, and the classical world never puts the two side by side. The qubit is where they meet as equals: both become operators on the same two-dimensional space, and both are Hermitian, so both become observables too. Put them together and the labels pair up, \mathbb{Z}_2 \;\longrightarrow\; \mathbb{Z}_2 \times \mathbb{Z}_2 , a label (a, b) that says whether to flip and whether to read the parity, each coordinate adding modulo 2 on its own. (Physicists call this product the phase space of the bit, by analogy with the position-and-momentum pairs of mechanics, and the symplectic form that a phase space carries is about to show up as a sign. The doubled group also has a name of its own, the Klein four-group; we will simply keep writing \mathbb{Z}_2 \times \mathbb{Z}_2.) The four labels get their candidate matrices in the obvious way, \sigma(a, b) = X^a Z^b : \qquad \sigma(0,0) = I, \quad \sigma(1,0) = X, \quad \sigma(0,1) = Z, \quad \sigma(1,1) = XZ , and only one of the four, the product XZ, is genuinely new. Now count. The previous section counted d^2 - 1 = 3 real numbers for a qubit state, and the count came from the d^2 = 4 real dimensions of Hermitian 2 \times 2 matrices, with one dimension spent on fixing the trace. A basis for everything needs four matrices, and four is exactly what the two representations produced between them. Nothing had to be added, and nothing is left over. Before writing the new matrix out, though, there is a question that sounds pedantic until you take it seriously.
Each representation on its own was exact: multiplication matched addition with nothing left over. Can the pair stay exact together? Could four matrices be chosen, these or any others, so that the match stays perfect and the four still span everything? The answer is no, and the reason is a counting argument, not an accident of X and Z. Labels commute: (a,b) + (a',b') = (a',b') + (a,b). If multiplication upstairs copied addition downstairs exactly, the four matrices would have to commute with one another too. But commuting is contagious: a matrix that commutes with all four basis matrices commutes with everything they span, and their span was supposed to be all 2 \times 2 matrices. A matrix that commutes with every matrix can only be a multiple of the identity. So all four would be stretched copies of I, spanning a single dimension rather than four. Phase-free multiplication and a full basis cannot coexist. Something has to give, and in quantum mechanics exactly one thing is allowed to give: a number out front. The matrices may multiply like the labels up to a scalar factor. That factor is not a blemish on an otherwise clean story. It is the mechanism by which four commuting labels manage to span a non-commuting world, and by the end of the post it will be carrying the answer.
Why no choice of matrices can dodge the phase
Suppose \sigma assigns a matrix to each element of some abelian group of four labels, with multiplication matching addition exactly: \sigma(g)\,\sigma(g') = \sigma(g + g'). Because g + g' = g' + g, the four matrices commute pairwise.
Now suppose they also span the whole space of 2 \times 2 matrices. The commutator is linear in each slot, so a matrix that commutes with all four basis matrices commutes with every linear combination of them, which by assumption is every matrix. In particular each \sigma(g) commutes with every 2 \times 2 matrix.
That is an extremely restrictive property. Let M commute with everything. Comparing off-diagonal entries of MZ and ZM gives -M_{12} = M_{12} and -M_{21} = M_{21}, so both vanish and M is diagonal. Commuting with X then forces the two diagonal entries to be equal. So M is a multiple of the identity.
Each \sigma(g) is therefore a multiple of I, and the span of all four is the one-dimensional line of multiples of I, not the four-dimensional space we demanded. Contradiction.
Notice what the argument never used: which four-element abelian group the labels form. The cyclic group \mathbb{Z}_4 fails for the same reason (powers of a single matrix always commute with each other). Nothing was special about 2 \times 2 either: in any dimension, a phase-free representation of an abelian label set can never supply a full operator basis. The phase is compulsory, everywhere. In the language of the two representations: had X and Z commuted, the four products X^a Z^b would span a commutative algebra, and no commutative algebra is all of the 2 \times 2 matrices.
Now watch the compulsory phase show up in the flesh. Multiply the two generators in both orders: XZ = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}, \qquad ZX = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}. The same matrix, with opposite signs: XZ = -ZX. The labels added the same way both times, (1,0) + (0,1) = (1,1), but the matrices remember the order, and they file that memory in a sign. (That sign is the symplectic form the phase space was promised. For a bit it is the whole of it: two labels either commute or they do not.)
One cosmetic decision before the full table. The fourth matrix XZ is the odd sibling: X and Z are Hermitian, but transposing and conjugating XZ flips its sign. A phase out front is ours to spend, it never touches the label bookkeeping, so spend it on restoring the family resemblance: define Y \;=\; i\,XZ \;=\; \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, Hermitian, and squaring to I like its siblings. The label of Y is (1,1), and the quartet I, X, Y, Z is complete. These are the Pauli matrices, the standard cast of single-qubit quantum mechanics, rebuilt here from the bit upward rather than handed down from above.
Here are all sixteen products.
| \cdot | I | X | Y | Z |
|---|---|---|---|---|
| I | I | X | Y | Z |
| X | X | I | iZ | -iY |
| Y | Y | -iZ | I | iX |
| Z | Z | iY | -iX | I |
Now do the exercise this table is begging for: put a thumb over the phases and read only the letters. X \cdot Y lands on Z, and the labels agree: (1,0) + (1,1) = (0,1). Y \cdot Z lands on X: (1,1) + (0,1) = (1,0). Every diagonal entry is I: any label added to itself is (0,0). Sixteen products, and the letters add coordinate-wise every single time, without exception. The scattered i’s and signs are trailing decoration that the labels never see.
This situation has a name. A rule \sigma satisfying \sigma(g)\,\sigma(g') \;=\; c(g, g')\,\sigma(g + g'), \qquad |c(g, g')| = 1, multiplication matching addition up to a phase factor, is called a projective representation of the group. The name should not suggest something second-rate. Quantum mechanics never cared about overall phases in the first place: a state and its phase-rotated copy answer every measurement identically, so representation up to phase is the native quantum notion of realizing a symmetry, not a defect of our particular matrices. And the aside above says the projective escape hatch is not merely permitted here. It is the one door that counting left open.
Coordinates in hand, we can finally say which copiers deserve them. A channel is linear, so it is pinned down by what it does to a basis; this is the move we used on the corners of the simplex, and we now use it on the quartet. A generic qubit channel that fixes the centre sprays each Pauli across all three Pauli directions, a 3 \times 3 grid of numbers, nine parameters with no structure to hold on to, and the coordinates we just built play no role in it whatsoever. The channels worth keeping are the ones that respect the labels, sending each Pauli to a multiple of a single Pauli: T[I] = I, \qquad T[X] = \lambda_X\, h(X), \qquad T[Y] = \lambda_Y\, h(Y), \qquad T[Z] = \lambda_Z\, h(Z), where h shuffles the three letters and each \lambda is a plain number. In group language: the channel leaves the structure we built invariant, mapping the representation onto itself instead of dissolving it. Geometrically: axes go to axes, possibly shrunk, never smeared. These are the Clifford channels.6
So a Clifford channel is two pieces of data. The skeleton h: one of the six ways to shuffle three letters, a finite list. And three numbers \lambda_X, \lambda_Y, \lambda_Z: one scale factor per axis. The requirement T[I] = I is our standing rule that the centre stays fixed, nothing new. The scale factors, though, are less free than they look. A channel maps states to states, and since every Hermitian matrix is a real combination of states, it maps Hermitian to Hermitian; with all four basis matrices Hermitian, each \lambda must be real. Feeding in the pure state \tfrac12(I + X) produces \tfrac12(I + \lambda_X\, h(X)), which is a legal state only if |\lambda_X| \leq 1: scale factors live between -1 and 1. Hold on to the reality of the scale factors, by the way. It looks like a convenience. At the end of the section it will reveal itself as a symmetry with a price tag attached.
Necessary is not sufficient, and honesty requires the flag: complete positivity, the condition that makes a linear map a channel, applies to this family as it did to the whole space. The old checklist splits here exactly as it always has: normalization is built in (T[I] = I, and traces are preserved by the label bookkeeping), while the positivity half is the fee. Not every setting of skeleton and scale factors is a lawful channel, and no amount of tidy bookkeeping waives that fee. What the small room changes is how the fee gets paid: by inspection, not by an estimate. For the one channel this section is hunting, we will exhibit lawfulness outright, no criterion needed.
Two panels. On the left, a Bloch ball, the continuum of qubit states, shaded by purity with a latitude and longitude wireframe, carrying three coloured coordinate axes: X = (1,0) toward the lower left, Y = (1,1) to the right, Z = (0,1) upward, and a grey identity dot labelled (0,0) at the centre. On the right, the finite plane of labels: four points, the identity (0,0) drawn as a grey dot matching the ball centre, and the three nonzero points (1,0), (0,1), (1,1) in the matching axis colours, cycled by an example homomorphism h.
The family is small, but everything this post has met so far is already inside it. Three exhibits.
First, the classical copier, lifted. Flip the qubit with probability a: that is the channel T[\rho] = (1-a)\,\rho + a\,X\rho X. Conjugating by X leaves X itself alone and flips the sign of Y and of Z (two quick visits to the multiplication table: XYX = -Y and XZX = -Z), so the mixture has skeleton h = \mathrm{id} and scale factors (1,\; 1-2a,\; 1-2a). Restricted to the vertical diameter it multiplies Z by 1 - 2a: exactly the classical copier we translated at the start. The lift is faithful.
Second, the reversible members. Conjugation by X alone is the case a = 1: scale factors (1, -1, -1), nothing shrunk, two axes reflected. Conjugation by the Hadamard gate H = (X + Z)/\sqrt{2}, the unitary that exchanges the roles of X and Z, gives the first nontrivial skeleton: h swaps X \leftrightarrow Z and fixes Y, with scale factors (1, -1, 1). Negative scale factors are legal, and reversible Clifford channels are precisely the famous Clifford gates, met here in channel clothing.
Third, total erasure itself. Set every scale factor to zero. Each Pauli dies, every Bloch vector is sent to the origin, and T is the completely depolarizing channel P itself, whatever the skeleton. The object we want roots of is a member of the family. The hunt can begin at home.
Apply a Clifford channel twice, and watch the bookkeeping run itself: T^2[X] \;=\; \lambda_X\, T[h(X)] \;=\; \lambda_X\, \lambda_{h(X)}\, h^2(X), and likewise for the other letters. Nothing new is ever created. Each letter walks, one step along h per application of the channel. And the scale factors multiply along the walk: after n steps a letter carries the product of the n scale factors it collected on departure. Meanwhile P is the channel that kills all three letters. So T^n = P \quad\Longleftrightarrow\quad \text{every letter's $n$-step product of scale factors has died.} The channel question has become a question about walks on three points and products of numbers along them. This is the reduction the whole post has been steering toward, and it will survive word for word when three letters become d^2 - 1.
One consequence is immediate, and it echoes the classical bit. Scale factors are real numbers, and a product of nonzero numbers is never zero. A walk’s product dies only by stepping on a zero scale factor. Erasure, in this family, is not a gradual conspiracy of small numbers. It happens exactly where the zeros are.
And now the hunt fits in three short paragraphs, because a shuffle of three letters has only three possible shapes.
The skeleton could fix all three letters. Then each letter walks in place, multiplying its own scale factor over and over, and dying forces that scale factor to be zero. All three scale factors zero means T = P from the very start. This is the classical bit’s tragedy, tripled: no roots live here.
The skeleton could swap two letters and fix the third. The fixed letter needs its own zero, as before. The swapped pair walk into each other, so at least one of their two scale factors must vanish, and then both of those walks are dead within two steps. Order two at best: a square root of erasure, the quantum sibling of the classical d = 3 construction, and nothing more.
Or the skeleton could cycle all three letters. Now a single zero serves everybody, because every walk eventually passes through it, and the walks reach it at different times. Put the zero on X, keep the other two scale factors alive at one half: T[X] = 0, \qquad T[Y] = \tfrac12\, X, \qquad T[Z] = \tfrac12\, Y . X dies immediately. Y steps onto X and dies departing it: two steps. Z takes the long way round, and it pays to compute it once in full: T[Z] = \tfrac12\, Y, \qquad T^2[Z] = \tfrac14\, X, \qquad T^3[Z] = 0 . So T^3 = P, while T^2 \neq P: the quarter of X still alive at step two is the witness. Order exactly three.
Three is the ceiling for the entire family, because the survey was exhaustive: no shuffle of three letters offers a longer walk to a zero. And three is d^2 - 1 at d = 2. Read that twice. The tiny, rigid family, six skeletons and three scale factors, reaches the same maximal order that the whole quantum machinery allows. Nothing was lost by retreating into the small room (Figure 6).
A large, gently irregular convex blob, the nine-parameter continuum of unital qubit channels. Through the grey point P inside it, the completely depolarizing channel, runs a bouquet of six thin straight teal needles, the Clifford channels: one sheet per skeleton, with the scale factors varying continuously along each, all sheets meeting at P. The needles extend further toward positive scale factors than negative ones, and the identity channel sits at the tip of the identity-skeleton needle, marked id.
You have seen this channel before. On Bloch vectors it sends (r_1, r_2, r_3) to (r_2/2,\; r_3/2,\; 0), which is the three-step eraser of Figure 4, the one the previous section produced without explanation. Its z, then y, then x stages are nothing but the walk around the cycle, one axis per step, and the cycle itself is the very one drawn on the right panel of Figure 5. What arrived last section as a rabbit from a hat is, in coordinates, a two-line design: spend one zero, take the longest walk. (The halves are a choice with a ceiling of their own: the two surviving scale factors cannot sum to more than one, so ours sit exactly on the boundary of what is allowed.7)
One debt remains, and it is the decisive one. A linear map of the right order is not yet a channel: complete positivity still has to be checked. Our T is, so far, four tidy equations. Is it physical?
Here is the same T wearing different clothes. Let U be the rotation of the Bloch ball by a third of a turn about the diagonal axis through (1,1,1), oriented so that it carries the x-axis onto the z-axis, the z-axis onto the y-axis, and the y-axis onto the x-axis. Then T[\rho] \;=\; \tfrac12\; U \rho\, U^\dagger \;+\; \tfrac14\; (XU)\, \rho\, (XU)^\dagger \;+\; \tfrac14\; (YU)\, \rho\, (YU)^\dagger . In words: flip a three-sided coin with weights one half, one quarter, one quarter, and depending on the outcome apply one of three rotations to the qubit: U, or U followed by an X-flip, or U followed by a Y-flip. That is the entire channel. A mixture of unitaries is a channel beyond any possible doubt: each branch is reversible physics, and forgetting the outcome of a coin flip cannot break positivity, complete or otherwise. Lawfulness by inspection. The fee the general construction paid with a shrinking factor and a Choi-matrix estimate is paid here, in the small room, with a coin and three rotations.
The coin and the three rotations, worked out
Two steps: split T into a rotation followed by a shrink, then write the shrink as a coin flip.
The rotation. Define U \;=\; \tfrac12\bigl(I + i\,(X + Y + Z)\bigr). Unitarity is one line with the multiplication table: writing S = X + Y + Z, the product (I + iS)(I - iS) = I + S^2, and S^2 = 3I because the six cross terms cancel in anticommuting pairs (XY + YX = iZ - iZ = 0, and likewise for the other two pairs). So U U^\dagger = \tfrac14 (I + 3I) = I. Conjugation by U cycles the Paulis, U X U^\dagger = Z, \qquad U Z U^\dagger = Y, \qquad U Y U^\dagger = X, each a patient exercise with the table. Write V[\rho] = U \rho\, U^\dagger for this rotation: a lawful channel, because it is unitary.
The shrink. Let D be the map with D[X] = \tfrac12 X, D[Y] = \tfrac12 Y, D[Z] = 0: scale factors one half on the x and y axes, zero on z, identity skeleton. Try a mixture of doing nothing, an X-flip, and a Y-flip, with weights p_0, p_1, p_2. Conjugation by X has scale factors (1, -1, -1) and conjugation by Y has scale factors (-1, 1, -1), so the mixture has scale factors \bigl(p_0 + p_1 - p_2,\;\; p_0 - p_1 + p_2,\;\; p_0 - p_1 - p_2\bigr). Setting these equal to (\tfrac12, \tfrac12, 0) together with p_0 + p_1 + p_2 = 1 solves to p_0 = \tfrac12 and p_1 = p_2 = \tfrac14.
The composite. Applying D after V does exactly what T demands: T[X] = D[Z] = 0, T[Y] = D[X] = \tfrac12 X, and T[Z] = D[Y] = \tfrac12 Y. Substituting the mixture for D and absorbing U into each branch turns the composition into the three-term coin flip of the main text, with unitaries U, XU and YU.
Two loose threads remain, both deliberately left dangling, both pointing straight at the next section.
First, a free pass we quietly enjoyed. We called h a shuffle and never demanded that it respect the labels’ arithmetic. It did so anyway, automatically: send two of the three letters wherever you like, and their sum, which is always the third letter, has nowhere to go but the remaining slot. Every shuffle of three letters is compatible with the addition of labels. That is a coincidence of the smallest case, and it expires immediately. In the next section the label plane has eight nonzero points, and of the 40320 ways to shuffle eight points, exactly 48 respect the addition of labels. The relabelling will have to be linear, and that phrase, a linear map on a plane of labels, is the door through which the finite-field machinery enters.
Second, look once more at where we spent the zero. It sits at the label (1,0). What is the negative of that label? In arithmetic modulo 2, where 1 + 1 = 0, every label is its own negative: -(1,0) = (1,0). That innocent-looking fact has been working for us all section. The general rule, visible in the next section, is that the scale factors at a label and at its negative are complex conjugates of one another; here every label is its own mirror, which is why our scale factors merely had to be real, and why a single zero came for the price of one. For odd d, a label and its negative are different points, and every zero will drag its mirror partner down with it: two zeros, minimum, cutting the longest walk short. That coincidence, quietly worth a factor of two, is the last thing the qubit gives us for free.
Clifford channels in higher dimensions
The qubit section ended by flagging two pieces of luck: every shuffle of three letters respected the label arithmetic on its own, and every label was its own mirror. Neither survives in higher dimensions, and this section is where both bills arrive. Paying them is not a chore. The first payment turns the relabelling into a linear map on a finite plane, which is where the finite fields promised at the very start of the post finally walk on stage. The second cuts the achievable order cleanly in half, and that factor of two is the punchline the whole post has been walking toward.
The play itself you have already watched. Build labelled matrices, keep the channels that respect the labels, reduce to walks and scale factors, then design the slowest possible eraser. Only the stage grows.
Start with the cast. A system with d levels has a d \times d density matrix, and the counting from the quantum section says a basis of everything needs d^2 matrices. So we need d^2 labels: pairs (a, b), each coordinate now running 0, 1, \ldots, d-1 and wrapping around, addition modulo d in both slots. The labels fill a d \times d grid, the label plane, and we write \eta for a point (a,b) of it when the pair travels as one thing. Note what the count buys: the d^2 - 1 nonzero labels are exactly one per traceless direction, the directions the CDC has to kill. Nothing is wasted and nothing is missing.
The two generators grow up along with the labels. For a bit, the flip X swapped two states; for d levels the natural move is add one and wrap around, the odometer step. Its companion Z kicks in phases instead of positions. For d = 3: X = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}, \qquad Z = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \omega & 0 \\ 0 & 0 & \omega^2 \end{pmatrix}, \qquad \omega = e^{2\pi i / 3}, with \omega a corner of the unit triangle in the complex plane, a cube root of one. For general d the same recipes run with d slots and \omega = e^{2\pi i / d}, and X^d = Z^d = I: d applications of either is a full lap. The matrix at label (a,b) is the product X^a Z^b, just as it was for the qubit.
Multiply the generators in both orders and watch the qubit’s sign grow up too: XZ = \begin{pmatrix} 0 & 0 & \omega^2 \\ 1 & 0 & 0 \\ 0 & \omega & 0 \end{pmatrix}, \qquad ZX = \begin{pmatrix} 0 & 0 & 1 \\ \omega & 0 & 0 \\ 0 & \omega^2 & 0 \end{pmatrix} \;=\; \omega\, XZ . Same matrix, and the memory of the order is now a full d-th root of unity rather than a sign: the trailing phase has become a d-hour clock. Everything else holds: the d^2 products multiply by adding labels, up to such a phase, and they form a basis of all d \times d matrices, so a channel is still pinned down by what it does to them.
Why the $d^2$ products form a basis
First, traces. The matrix X^a shifts every basis vector a slots, so for a \not\equiv 0 its diagonal is empty and \operatorname{tr}(X^a Z^b) = 0. For a = 0 the trace of Z^b is 1 + \omega^b + \omega^{2b} + \cdots + \omega^{(d-1)b}, the sum of all d-th roots of unity taken b at a time, which vanishes unless b \equiv 0 (the terms are the corners of a regular polygon centred at the origin). So every labelled matrix is traceless except the identity at (0,0), whose trace is d.
Now take two different labels \eta \neq \eta'. The product (X^a Z^b)^\dagger (X^{a'} Z^{b'}) is, by the multiplication rule, a phase times the matrix at label \eta' - \eta \neq (0,0), so its trace vanishes. In the trace inner product \langle A, B\rangle = \operatorname{tr}(A^\dagger B) the d^2 matrices are mutually orthogonal, hence linearly independent, and d^2 independent matrices in a d^2-dimensional space are a basis.
One piece of grooming, and it is the same grooming as before. At the qubit stage we multiplied the odd sibling XZ by i to restore the family resemblance. The general recipe sprinkles a square root of \omega in front: \mathbf{w}(a, b) \;=\; \tau^{ab}\, X^a Z^b, \qquad \tau = \omega^{(d+1)/2}, \qquad \tau^2 = \omega . Read \tau^{ab} as “half of the label product ab, on the \omega-clock”, which makes sense because 2 can be divided away modulo an odd number. For odd d this square root already sits on the d-hour clock; at d = 2 it does not, which is why the qubit had to borrow i from outside. The mysterious grooming i of the last section was this convention all along.
What the grooming buys has changed, though. For d > 2 no phase makes X^a Z^b Hermitian, so the qubit’s luxury of an all-Hermitian basis is simply gone. What survives is the next best thing, a mirror symmetry: \mathbf{w}(\eta)^\dagger \;=\; \mathbf{w}(-\eta), the adjoint of the matrix at \eta is the matrix at the opposite label -\eta = (-a, -b), on the nose, no stray phase (checked in the aside below). Keep that mirror in view. It is the second debt from the qubit section, and it will collect at the very end.
And now the fine print that has been riding along quietly: from here on, d must be a prime. The grooming already divided by 2; everything below divides by worse. Modulo a prime, every nonzero number can be divided away, and the integers modulo d form a field, written \mathbb{F}_d, an arithmetic where division works as cleanly as addition. Modulo a composite the floor gives way: mod 4, for instance, 2 \cdot 2 = 0, and a “plane” over such an arithmetic has lines that collapse. So the label plane is \mathbb{F}_d^2, a plane over a field, and the linear algebra we are about to do on it can be trusted. (Prime powers have a parallel story over their own finite fields; genuinely composite d is murkier territory, and the theorem below is a prime-d theorem.)
Here is the family, at full scale. A Clifford channel in dimension d sends each labelled matrix to a multiple of one labelled matrix: T[\mathbf{w}(\eta)] \;=\; \lambda(\eta)\, \mathbf{w}(h(\eta)), \qquad \lambda(0,0) = 1, with h a relabelling of the plane fixing (0,0), and one scale factor \lambda(\eta) per label, complex now, sizes at most one. (At the qubit stage we earned that size bound by feeding a state through the channel. Here the labelled matrices are no longer Hermitian, and that trick only delivers a slightly weaker bound. The sharp one is complete positivity’s doing, and the aside on the CP criterion later in this section records the one-line argument.) But here the first debt falls due. For three letters, any shuffle respected addition on its own. On a bigger plane that is spectacularly false, and respecting the group structure, h(\eta + \eta') = h(\eta) + h(\eta'), forces h to be linear: an invertible 2 \times 2 matrix with entries in \mathbb{F}_d, acting on label pairs. (Invertible, because a relabelling worthy of the name must not crush two directions into one. The count: the first column can be any of the d^2 - 1 nonzero pairs, the second anything off the line through the first, d^2 - d choices. For d = 2 that is 3 \cdot 2 = 6 maps for 6 shuffles, which is why every qubit shuffle passed for free. For d = 3 it is 8 \cdot 6 = 48, against 8! = 40320 shuffles of the eight nonzero labels: the collapse promised last section.)
The scale factors are constrained the same way they were for the qubit, with the mirror doing the work Hermiticity used to do. A channel maps Hermitian to Hermitian (real combinations of states, as before), and chasing that through the mirror symmetry gives the mirror rule: \lambda(-\eta) \;=\; \overline{\lambda(\eta)} . The scale factor at a label and the scale factor at its mirror are complex conjugates. At d = 2, where -\eta = \eta, this collapses to “scale factors are real”, which is exactly what we found. And complete positivity is still to be checked: not every (h, \lambda) is a lawful channel. The fee gets paid at the end of the section, with the same \varepsilon coin that paid it classically.
The mirror rule, derived
First the mirror symmetry of the basis itself. Taking the adjoint of \mathbf{w}(a,b) = \tau^{ab} X^a Z^b gives \overline{\tau^{ab}}\, Z^{-b} X^{-a}. Slide X^{-a} back past Z^{-b} with the commutation rule (ZX = \omega XZ, applied ab times in the exponents): Z^{-b} X^{-a} = \omega^{ab}\, X^{-a} Z^{-b}. The accumulated phase is \overline{\tau^{ab}}\,\omega^{ab} = \tau^{-ab}\,\tau^{2ab} = \tau^{ab}, and since ab = (-a)(-b) this is precisely the grooming phase belonging to the label (-a, -b): \mathbf{w}(a,b)^\dagger = \tau^{(-a)(-b)}\, X^{-a} Z^{-b} = \mathbf{w}(-a,-b) . This is what the square-root grooming was for: the raw products X^aZ^b obey the same law only up to a trailing phase, and the \tau soaks it up exactly.
Now the rule for the scale factors. A channel preserves Hermitian matrices, hence adjoints: T[A^\dagger] = T[A]^\dagger for every A. Apply both sides to A = \mathbf{w}(\eta). The left side is T[\mathbf{w}(-\eta)] = \lambda(-\eta)\,\mathbf{w}(h(-\eta)) = \lambda(-\eta)\,\mathbf{w}(-h(\eta)), using linearity of h in the last step. The right side is \overline{\lambda(\eta)}\,\mathbf{w}(h(\eta))^\dagger = \overline{\lambda(\eta)}\,\mathbf{w}(-h(\eta)). The matrices match, so the coefficients must: \lambda(-\eta) = \overline{\lambda(\eta)}.
The reduction now carries over word for word, as promised. Apply T repeatedly and nothing new is ever created: each label walks, one step of h per application, and the scale factors multiply along the walk: T^{\,n}[\mathbf{w}(\eta)] \;=\; \lambda(\eta)\,\lambda(h\eta)\cdots\lambda(h^{n-1}\eta)\; \mathbf{w}(h^{n}\eta) . P is the channel that kills every nonzero label, so T^n = P exactly when every label’s n-step product has died, and a product of nonzero numbers never dies, so every walk must step on a zero of \lambda. Since h is invertible it chops the d^2 - 1 nonzero labels into closed cycles, and the game is suddenly a board game: mark some squares with zeros, subject to the rules, and ask how long the luckiest token stays alive, where a token dies on the turn it departs a marked square, since the scale factor is applied on departure. Two questions decide everything. How long can a cycle be? And how few marked squares can we get away with?
Take the cycle question first. The best imaginable h would sweep all d^2 - 1 nonzero labels in one grand cycle, and it is not obvious such a linear map exists: linearity is a strong leash. The reason it exists is the loveliest structural fact in this post: the label plane is secretly a number system. Recall how the complex numbers are built from the reals: the equation x^2 + 1 = 0 has no solution, so you adjoin a symbol i that solves it, and pairs a + b\,i close up into a field. Now run the same construction over \mathbb{F}_3. The polynomial x^2 + x + 2 has no root there (its values at x = 0, 1, 2 are 2, 1, 2), so adjoin a symbol g that solves it, g^2 \;=\; -g - 2 \;=\; 2g + 1, and consider all expressions a + b\,g with a, b \in \mathbb{F}_3. There are nine of them, they add and multiply like ordinary numbers (reducing g^2 via the rule above), and they form a field with nine elements, written \mathbb{F}_9. But pairs (a,b) are exactly our labels: the label plane \mathbb{F}_3^2 and the field \mathbb{F}_9 are the same set. The plane we have been drawing points on all along can secretly multiply.
That changes everything, because now “multiply by g” is a candidate relabelling. It is linear in (a, b), since multiplication distributes over addition. Its matrix is read off column by column: g \cdot 1 = g sends (1,0) to (0,1), and g \cdot g = 2g + 1 sends (0,1) to (1,2), so h \;=\; \begin{pmatrix} 0 & 1 \\ 1 & 2 \end{pmatrix} . And its cycle structure is a question about powers of g. Compute them, reducing with g^2 = 2g + 1 as you go: g^2 = 2g + 1, \qquad g^3 = g \cdot g^2 = 2g^2 + g = 2g + 2, \qquad g^4 = g \cdot g^3 = 2g^2 + 2g = 2 . Pause on that last line. In \mathbb{F}_3, the number 2 is -1: four multiplications by g amount to a single overall sign flip. Squaring once more, g^8 = 1, and no earlier power returns to 1 (the powers g, g^2, g^3 visibly involve g, and g^4 = -1). So g has order exactly 8 = d^2 - 1: its powers g^0, g^1, \ldots, g^7 are eight different nonzero elements, and there are only eight to be had. The powers of g visit every nonzero label exactly once. Translated back to pairs, the matrix h drives the whole plane around one grand cycle, (1,0) \to (0,1) \to (1,2) \to (2,2) \to (2,0) \to (0,2) \to (2,1) \to (1,1) \to (1,0), which is the ring drawn in Figure 7. An element like g, whose powers exhaust every nonzero element, is called a generator, its minimal polynomial x^2 + x + 2 is called a primitive polynomial, and the matrix h built from it is that polynomial’s companion matrix. Generators exist for every prime d, not just d = 3, and the aside below proves it from scratch, so a grand cycle of length d^2 - 1 is always available.
The eight nonzero labels of the three-by-three label plane, arranged on a ring in the order the matrix h visits them: (1,0), (0,1), (1,2), (2,2), (2,0), (0,2), (2,1), (1,1), and back to (1,0). Arrows step from each label to the next around the ring. The labels (1,0) and (2,0) sit at opposite ends of a dashed horizontal diameter labelled eta maps to minus eta; both are highlighted in a warm accent and tagged lambda equals zero. That pair splits the ring into an upper arc of four steps and a lower arc of four steps.
Primitive polynomials and the single long cycle
Two facts from algebra stand behind the construction: a quadratic with no root always exists, so that a field with d^2 elements can be built at all, and the nonzero elements of that field form a single multiplicative cycle, so that a generator exists. Both are classical.8 Neither needs to be taken on faith: this aside proves both, with a pencil, from things the post already uses.
A rootless quadratic exists. Square every nonzero element of \mathbb{F}_d. The elements a and -a always land on the same square, and for odd d they are genuinely different elements, so squaring is two-to-one: at most \tfrac{d-1}{2} of the d - 1 nonzero values are squares. Non-squares exist. Pick one, call it s, and the quadratic x^2 - s has no root, by the very meaning of “non-square”. Two things are worth savoring here. This is exactly how the complex numbers arise: -1 is a non-square of the reals, and i is the adjoined root of x^2 + 1. And look at which fact did the work. “a \neq -a for odd d” is the mirror fact, the same arithmetic that will shortly force zeros of \lambda to come in genuine mirror pairs. The odd-d arithmetic that halves the achievable order is also the arithmetic that guarantees the label plane can multiply. (At d = 2 every element is its own negative, squaring is one-to-one, and the non-square well is dry; there the lone irreducible quadratic x^2 + x + 1 is checked by hand, since neither 0 nor 1 is a root.)
Adjoining the root gives a field. The pairs a + b\,g, with every g^2 that appears reduced by the quadratic’s rule, add and multiply like ordinary numbers, and “no root” is the same as “does not factor” for a quadratic, so no product of two nonzero expressions can reduce to zero. Inverses then come from finiteness for free: multiplying the d^2 - 1 nonzero expressions by a fixed nonzero one is injective (nothing collapses to zero), and an injective reshuffling of a finite set hits everything, including 1. So every nonzero expression has an inverse, and the d^2 expressions form the field \mathbb{F}_{d^2}.
Every nonzero element is a root of x^n = 1, where n = d^2 - 1. Fix a nonzero x and multiply every nonzero element by it. That map is injective, so it merely reshuffles the n nonzero elements. Multiply all n of them together, before and after the reshuffle: as a set the product is unchanged, but factor by factor it has picked up x exactly n times. So x^n times the product equals the product, and cancelling the nonzero product leaves x^n = 1. The order of x, the first exponent at which its powers return to 1, then divides n: write n = qe + r with 0 \le r < e, and 1 = x^n = (x^e)^q\, x^r = x^r forces r = 0.
Root scarcity. A polynomial of degree m has at most m roots over a field. A root a can be divided out: dividing by x - a leaves a constant remainder, and evaluating at a shows that remainder to be zero, so the polynomial is (x - a) times something of degree m - 1. In a field a product vanishes only if a factor does, so every further root is a root of the quotient, and the degrees run out after m steps. In particular x^e = 1 has at most e solutions.
Elements of equal order come in batches. Suppose some element a has order e. Its powers 1, a, \ldots, a^{e-1} are e distinct solutions of x^e = 1, and scarcity says they are all the solutions. Any element of order e solves that equation, so it is one of these powers. Which powers have order exactly e? Precisely the a^k whose exponent shares no factor with e: a shared factor t > 1 gives the early return (a^k)^{e/t} = (a^e)^{k/t} = 1, while if k shares no factor with e, then (a^k)^m = 1 means e divides km, and with nothing to find in k, all of e must divide m: the first return is at m = e. The count of such exponents is written \varphi(e), Euler’s function. So for every divisor e of n, the elements of order e number either zero or exactly \varphi(e), never anything else.
The batches must all be full. Here is the counting identity that closes the trap: \sum_{e \mid n} \varphi(e) \;=\; n . To see it, write the n fractions \tfrac1n, \tfrac2n, \ldots, \tfrac nn and reduce each to lowest terms. Every reduced denominator is a divisor e of n; the reduced fractions with denominator e are exactly the \varphi(e) fractions \tfrac ke with k sharing no factor with e; and each arises from exactly one fraction on the original list. Counting the list both ways proves the identity. Now sort the n nonzero field elements into batches by their order, which is always a divisor of n. Each batch holds at most \varphi(e) elements, and the capacities \varphi(e) sum to exactly n, the number of elements to be sorted. There is no slack: every batch is full. In particular the batch e = n is not empty, and an element of order n = d^2 - 1 exists. That is the generator, and root scarcity did all the pushing: x^e = 1 has too few solutions for the group to splinter, so it stays in one cycle.
From generator to matrix. A generator g cannot lie in the base field: nonzero elements of \mathbb{F}_d satisfy x^{d-1} = 1 (the same reshuffling trick, run inside \mathbb{F}_d), and g’s order d^2 - 1 is larger than d - 1. So 1 and g are linearly independent over \mathbb{F}_d, they span the plane, and 1, g, g^2 must be linearly dependent: g satisfies a monic quadratic with coefficients in \mathbb{F}_d (the g^2 coefficient cannot vanish, or 1 and g would already be dependent), irreducible because a factorization would hand g a linear equation and put it in the base field. That quadratic is the primitive polynomial, and its companion matrix is the multiplication-by-g map in the coordinates (a, b) \leftrightarrow a + b\,g, which is why the matrix has order d^2 - 1: its powers track the powers of g.
For the worked example none of this machinery was needed on faith: x^2 + x + 2 was checked to be irreducible by trying all three arguments, and g was checked to be a generator by computing g^4 = -1 \neq 1, which rules out every proper divisor of 8 as its order.
So cycles can be as long as d^2 - 1, and one marked square per cycle is the least the rules could possibly demand. If that were the end of the story, the Clifford family would match the full quantum bound d^2 - 1 in every dimension: put the single zero on the grand cycle, and the slowest token, starting just after it, walks the whole ring and dies only on turn d^2 - 1, the turn it must depart the zero itself. For the qubit, that is exactly what happened.
Here the second debt falls due. Zeros of \lambda cannot be placed one at a time, because the mirror rule pairs the scale factors up: |\lambda(-\eta)| = |\lambda(\eta)|, so where one scale factor dies its mirror dies with it. For the qubit this cost nothing, since every label was its own mirror. But for odd d, a nonzero label and its mirror are always different points (\eta = -\eta would mean 2\eta = 0, and modulo an odd prime you can divide the 2 away, leaving \eta = 0). Zeros now come in genuine pairs: mark one square and a second square is marked for you, whether you wanted it or not.
And the geometry of the grand cycle decides where that unwanted second zero lands. The mirror map is multiplication by -1, and on the cycle of g we have already met -1: it is g^{(d^2-1)/2}, the halfway point. (That is no accident of d = 3: the element c = g^{(d^2-1)/2} satisfies c^2 = 1 while c \neq 1, and in a field the equation x^2 = 1 has no room for solutions beyond 1 and -1.) So the mirror of any label sits exactly half a cycle away, diametrically opposite on the ring, just as Figure 7 shows. Mark the square z, and the rules mark -z: not adjacent, not random, but precisely antipodal, cutting the grand cycle into two arcs of length exactly \tfrac{d^2-1}{2} each. The slowest token starts just after either zero and walks the far arc, alive after every turn but the last, dying exactly on turn k \;=\; \frac{d^2 - 1}{2}, the turn it must depart the other zero, and not one sooner. The mirror rule has taken the qubit’s gift back, and it has taken exactly a factor of two.
Assemble the channel and settle its legality. Take h the companion matrix of a primitive polynomial, and set the scale factors to \lambda(0,0) = 1, \qquad \lambda(z) = \lambda(-z) = 0 \;\ \text{for one mirror pair,} \qquad \lambda(\eta) = \varepsilon \;\ \text{everywhere else,} with \varepsilon a small positive number. The mirror rule holds (\varepsilon is real, and mirrors carry equal scale factors), the walk products die exactly as the arcs dictate, so T^{(d^2-1)/2} = P while T^{(d^2-1)/2 - 1} \neq P: the token that started just after a zero is still alive, carrying \varepsilon^{(d^2-1)/2 - 1} \neq 0, as the witness. And complete positivity, the fee the qubit section paid with a coin flip of three rotations, is where the Clifford family shows its final virtue: here the condition has an explicit face. A Clifford channel is completely positive exactly when a single d^2 \times d^2 matrix assembled from the scale factors is positive semidefinite, and a classical eigenvalue theorem turns that condition into a simple sufficient condition on the absolute values of the scale factors: \sum_{\eta \neq 0} |\lambda(\eta)| \;\le\; 1 . If the absolute values of the scale factors sum to at most one, the channel is lawful. Our root sets \lambda = \varepsilon on the d^2 - 3 surviving labels, so every \varepsilon \le \tfrac{1}{d^2 - 3} satisfies the condition, and the order of the root never cared how small \varepsilon is. The aside shows the criterion and derives the sufficient condition; the exact boundary of legality is a genuinely harder computation, and for that the thesis does the honest work.9
The complete positivity criterion for Clifford channels
Complete positivity always has a certificate, and we have met it once already: the Choi matrix, which the aside in the quantum section used purely as a black box, one big matrix assembled from the channel, positive semidefinite exactly when the channel is completely positive. For a general channel that matrix is an opaque block of numbers. For a Clifford channel, written in Weyl coordinates, its entries become explicit. Its rows and columns are indexed by the labels, one apiece, and its entries are scale factors in disguise: M_{\eta\xi} \;=\; c_{\eta\xi}\; \lambda(\eta - \xi), \qquad |c_{\eta\xi}| = 1, where the phases c_{\eta\xi} are bookkeeping determined by h and the Weyl multiplication rule. Three features matter. Every diagonal entry is \lambda(0) = 1. The sizes of the entries, |M_{\eta\xi}| = |\lambda(\eta - \xi)|, do not see h or the phases at all. And M is Hermitian, precisely because of the mirror rule. So “is this Clifford channel lawful?” has become “is this one matrix of scale factors positive semidefinite?”, a condition you can actually get your hands on.
One dividend arrives before any theorem. A positive semidefinite matrix with ones on its diagonal cannot hold an entry of size above one: the 2 \times 2 principal submatrix \bigl(\begin{smallmatrix} 1 & m \\ \bar m & 1 \end{smallmatrix}\bigr) must itself be positive semidefinite, and its determinant is 1 - |m|^2. Every scale factor appears as such an entry (\lambda(\zeta) sits wherever \eta - \xi = \zeta), so |\lambda(\zeta)| \le 1 for every label. That is where the main text’s “sizes at most one” comes from, and it is complete positivity’s doing, not mere positivity’s.
Now the classical eigenvalue theorem: Gershgorin’s circle theorem. Every eigenvalue of a matrix lies in one of its Gershgorin discs, a disc centred at a diagonal entry with radius the summed sizes of the other entries in that row. For our M every centre is 1, and every row has the same radius R = \sum_{\zeta \neq 0} |\lambda(\zeta)|, since as \xi runs through the other labels the difference \eta - \xi runs through every nonzero label exactly once. M is Hermitian, so its eigenvalues are real and live in [1 - R,\; 1 + R]. If R \le 1, none of them can be negative: M is positive semidefinite and the channel is lawful. That is the sufficient condition \sum_{\eta \neq 0} |\lambda(\eta)| \le 1 of the main text.
Check it against everything we have built. The qubit root of the last section had scale factors 0, \tfrac12, \tfrac12: the absolute values sum to exactly 1, so the condition holds with equality (and, at d = 2, this sits on the true boundary of legality, as that section’s footnote recorded). The root above sets \lambda = \varepsilon on d^2 - 3 surviving labels: the condition holds for every \varepsilon \le \tfrac{1}{d^2-3}, which for d = 3 allows \varepsilon up to \tfrac16. And it explains, one level up, why the classical aside’s \varepsilon was free: for the completely depolarizing channel every \lambda(\eta) with \eta \neq 0 vanishes, the sum is 0, and there is maximal room in every direction.
One honesty note. The condition is sufficient, not necessary: scale factors can violate it and still describe a lawful channel (the identity channel, with every \lambda(\eta) = 1, violates it grossly and is lawful all the same). The exact boundary is the positive semidefiniteness of M itself, and mapping that boundary is the thesis’s work, not this post’s.
One suspicion should still be nagging. The construction used a very particular h and the stingiest legal set of zeros. Could a cleverer h, or a cleverer placement, beat one half? It cannot, and the reason is pleasantly structural: however the board is set up, either the two zeros of a pair share a cycle, and symmetry pins them opposite each other, or they sit in two different cycles, and then each cycle is at most half the plane anyway. Both roads cap the survival time at \tfrac{d^2-1}{2}.
Why nothing beats one half
Let T be any Clifford root of P in odd prime dimension d, with relabelling h and zero set Z = \{\eta \neq 0 : \lambda(\eta) = 0\}. Every cycle of h on the nonzero labels must contain a point of Z (walks die only on zeros), and the mirror rule forces -Z = Z. One structural fact does the rest: negation commutes with h, since h is linear, h(-\eta) = -h(\eta). So negation maps cycles of h to cycles of h, either exchanging two cycles or preserving one.
Case one: a cycle C, of length L, is preserved by negation. Pick a zero z \in C \cap Z; then -z is also in C, and -z \neq z for odd d. On a cycle, a symmetry that commutes with the step map acts as a fixed rotation: if -z = h^m z, then negating any point h^j z gives h^{j+m} z, the same shift m for all of them. Negating twice returns home, so 2m is a multiple of L, and m is neither 0 nor L, forcing m = L/2: the mirror of every point of C sits exactly opposite it. The cycle carries zeros at z and h^{L/2} z at least, so every token in C is dead by turn L/2 \le \tfrac{d^2-1}{2}.
Case two: a cycle C and its negation -C are different cycles. They have the same length L and no points in common, and both live among the d^2 - 1 nonzero labels, so 2L \le d^2 - 1. Every token in C is dead by turn L \le \tfrac{d^2-1}{2}, zero or no zero to spare.
Every cycle falls under one case or the other, so every token on any legal board is dead by turn \tfrac{d^2-1}{2}: k \le \tfrac{d^2-1}{2} for every Clifford root. (Extra zeros only ever shorten survival, which is why the stingiest board is the best one.)
That is the theorem this post set out to retell. For every odd prime d there is a Clifford channel whose order is exactly \tfrac{d^2-1}{2}, and no Clifford channel does better. The qubit stays the lone exception: there the mirror degenerates, the pairing costs nothing, and the family reaches the full d^2 - 1 = 3, as we watched it do.
Line the three answers up for a three-level system. A classical copier can stretch erasure to 2 steps. The full quantum bound is 8. And the Clifford family, rigid as it is, manages 4: half of everything quantum mechanics allows, from a corner of it that you can hold in your hand.
Step back and look at where the room came from. We began with the full space of quantum channels, a space whose dimension grows like d^4, and found the bound d^2 - 1. We then threw essentially all of that freedom away. What survived was one invertible 2 \times 2 matrix over a finite field and a handful of scale factors, and the achievable order fell only from d^2 - 1 to \tfrac{d^2-1}{2}. The room to divide erasure slowly never lived in the richness of the channel family. It lives in the orbit structure of a linear map on a tiny plane: in how long one matrix can wander d^2 - 1 labels before a mirror-forced pair of zeros cuts the journey in half. Slow forgetting is not an exotic quantum resource. It is finite-field bookkeeping, and you can check every step of it with a pencil.
What’s next
One loose thread remains: the factor of two. Is (d^2 - 1)/2 the end of the story, or just the end of the Clifford story? It is only the Clifford story, and the post has already shown as much: the aside in the quantum section shrinks a nilpotent block into a lawful channel of the full order d^2 - 1, in every dimension. That construction gives up the tidy Weyl structure we leaned on, works directly at the level of the channel’s representation, and never meets a mirror pair, which is why no factor of two appears in it.10 One caution against a wrong impression the shrinking might leave: maximal roots are not condemned to huddle near total erasure. In every dimension there are maximal roots sitting at a distance from P that does not shrink as the dimension grows, and our qubit root, with its two scale factors at one half, was never a small perturbation to begin with.
Historically the discoveries ran in the opposite order from this post. Complete positivity kept the general construction out of reach for most of my thesis: a Jordan block hands you a linear map of the right order, and it was long unclear that a bound-saturating block could be shrunk into a lawful channel without losing its order. The Clifford family was the smaller room where the question first yielded, and the general root arrived only at the very end. That more general result subsumes the Clifford one, which is why the Clifford construction does not appear in the final paper. I wanted to write it up anyway, because it is the cleanest place I know to actually see the finite-field representation theory at work. In the general construction the orbit structure is buried inside linear algebra over \mathbb{C}. Here it sits on the surface: a point hopping around a plane of d^2 labels, a matrix of order d^2 - 1, and a single symmetry that costs a factor of two. The whole argument fits in the palm of your hand, and you can check the d = 3 case by stepping around an eight-point cycle with a pencil.
There is one more way to read these numbers, and it closes a loop opened at the very start of the post: the device that carries a private memory from one use to the next, and is strictly forgetful when that memory is provably purged after finitely many uses. A qubit memory can survive for at most three uses. A Clifford memory of odd prime dimension d can survive for (d^2 - 1)/2, and the most stubborn quantum memory of all for d^2 - 1. After that, the influence of how the memory began is not merely small. It is gone.
Here is the scoreboard of Table 1 with its third column filled in.
| Classical | Quantum | Clifford | |
|---|---|---|---|
| Copiers considered | bistochastic matrices | channels fixing the centre I/d | channels sending each labelled matrix to a multiple of one labelled matrix |
| Free parameters | (d-1)^2 | (d^2-1)^2 | one invertible 2 \times 2 matrix over \mathbb{F}_d, plus d^2 - 1 scale factors |
| The condition with teeth | non-negative entries | complete positivity | complete positivity, as positivity of one d^2 \times d^2 matrix of scale factors; sufficient: their absolute values sum to at most one |
| Largest order k | d - 1 | d^2 - 1 | (d^2 - 1)/2 for odd prime d; d^2 - 1 = 3 at d = 2; open for composite d |
| Reached by | a nilpotent N on the deviations, scaled gently | a nilpotent N on the traceless operators, shrunk until the Choi matrix stays positive | a grand cycle of the label plane with zeros on one mirror pair, a small \varepsilon everywhere else |
| Seen in action | d = 3, two steps (Figure 2) | d = 2, three steps (Figure 4) | d = 2, three steps (Figure 4); d = 3, the eight-point ring (Figure 7) |
One thread I never pulled: the Clifford result is a prime-d result. Prime powers should tell a parallel story over their own finite fields, and genuinely composite d, where the label plane is no longer a plane over a field, is territory I never found the time to look at.
The full development, including the classical and general quantum bounds and the Clifford channels above, is in my diploma thesis.11
Page views: …
Footnotes
The systematic treatment of this asymptotic question is D. Burgarth, G. Chiribella, V. Giovannetti, P. Perinotti and K. Yuasa, “Ergodic and mixing quantum channels in finite dimensions”, New Journal of Physics 15, 073045 (2013). A sharp cousin is the quantum Wielandt inequality, bounding how many steps it can take a channel before every output state has full rank: M. Sanz, D. Pérez-García, M. M. Wolf and J. I. Cirac, IEEE Transactions on Information Theory 56, 4668 (2010). For a pedagogical entry point, Michael Wolf’s lecture notes Quantum Channels & Operations: Guided Tour (2012).↩︎
The framework of quantum channels with memory is due to D. Kretschmann and R. F. Werner, “Quantum channels with memory,” Phys. Rev. A 72, 062323 (2005); arXiv:quant-ph/0502106.↩︎
We meet qubits, density matrices, and channels here at the level of pictures, not bra-ket algebra, so you can follow along cold. If you want the real foundations, single qubits, gates, and the |0\rangle, |1\rangle notation built from scratch, Matuschak and Nielsen’s Quantum Computing for the Very Curious is the gentlest on-ramp I know, and it is the model this post is written in.↩︎
For the structure theory of quantum channels, including the Kraus decomposition and the Stinespring dilation, the standard reference is Nielsen and Chuang, Quantum Computation and Quantum Information, chapter 8. Michael Wolf’s lecture notes Quantum Channels and Operations: Guided Tour are a more focused modern treatment.↩︎
A. Ahlbrecht, F. Richter and R. F. Werner, “How long can it take for a quantum channel to forget everything?”, arXiv:1205.0693 (2012); the construction is Theorem 3.4 there. The closing section of this post says how the Clifford story below relates to that paper.↩︎
The name comes from their reversible cousins: the Clifford gates of quantum computing are the unitaries that map Pauli operators to Pauli operators under conjugation, and they are the backbone of the stabilizer formalism of quantum error correction (Nielsen and Chuang, chapter 10). The channels here are the open-system version of the same idea. Not to be confused with Clifford algebras, another legacy of the same nineteenth-century geometer, William Kingdon Clifford. One further caution: in recent literature “Clifford channel” often means a channel implementable by stabilizer (Clifford) circuits, a related but different class; throughout this post the term is used in the thesis’s sense, a channel sending each labelled matrix to a scalar multiple of a single labelled matrix.↩︎
Deciding exactly which scale factors yield a lawful channel is a solved problem for qubits: M. B. Ruskai, S. Szarek and E. Werner, “An analysis of completely-positive trace-preserving maps on 2 \times 2 matrices”, Linear Algebra and its Applications 347, 159 (2002). For our root the criterion reduces to \lambda_Y + \lambda_Z \leq 1. The thesis works out the criterion for the whole Clifford family in its chapter 5 (Lemma 5.1); the next section of this post shows its face.↩︎
The textbook road through everything in this aside is R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press; chapter 2 covers the structure of finite fields, including the cyclicity of the multiplicative group and primitive polynomials. The prime-field case, the existence of primitive roots modulo a prime, is proved in Gauss’s Disquisitiones Arithmeticae (1801), and the root-counting bound goes back to Lagrange. The proofs given here are the classical ones, retold.↩︎
The criterion, phases and all, is Lemma 5.1 in chapter 5 of the thesis, following earlier work cited there; the diagonal-dominance argument behind the sufficient condition appears in sections 5.2.1 and 5.4.1 there. The condition deliberately trades sharpness for self-containedness: the exact boundary of legality is the positive semidefiniteness of M itself.↩︎
A. Ahlbrecht, F. Richter and R. F. Werner, “How long can it take for a quantum channel to forget everything?”, arXiv:1205.0693 (2012). The construction is Theorem 3.4 there; the maximal roots far from P are Proposition 3.5.↩︎
F. Richter, Finite Roots of Completely Depolarizing Channels, Diploma thesis, Institute for Theoretical Physics, Leibniz Universität Hannover, September 2010. PDF in this site’s repository.↩︎