The Clifford group as a permutation group

July 6, 2025

By Robert Smith

The Clifford group is an important mathematical group that is foundational to the field of quantum error correction and quantum benchmarking. I’ve long been interested in computing with the Clifford group.

I wrote a paper called The Computational Structure of the Clifford Groups which gives an implementation perspective of the math. The paper can be found on page 44 of the proceedings of the 2018 European Lisp Symposium.
Much of that paper is implemented in QUILC. I helped write the Common Lisp code for manipulating Clifford group elements specifically for the purpose of randomized benchmarking.
The Clifford group is a foundational tool in QUILC’s discrete compiler, which was implemented in Coalton.
I wrote a fast Clifford circuit simulator in the main implementation of the quantum virtual machine, called the stabilizer QVM.

In lieu of actually defining the Clifford group (the Computational Structure paper does that fine if you’re interested), I’ll tell you one interesting fact about it: It is, in some sense, the largest collection of quantum operations you can fit together, before adding any other would make the collection computationally universal.

One of the greatest discoveries of the 20th century was the tractability of studying finite groups on a computer. Specifically, two breakthrough algorithms laid the foundation for the field of computational group theory:

The Todd–Coxeter algorithm solves coset enumeration of finitely presented groups (i.e., groups that are specified by a set of symbols and rewrite equations). It was discovered in the 1930s, and it’s even feasible to do by hand in some cases.
For a permutatuion group $G$ generated by $\ell$ permutations of $n$ points, the Schreier–Sims algorithm produces a data structure for $G$ in something like $O\big(n^2(\log\vert G\vert)^3+\ell n\log\vert G\vert\big)$ time and $O(n^2\log\vert G\vert + \ell n)$ space. This data structure lets us compute the size of $G$, determine whether any permutation is an element of $G$, manufacture uniformly random elements of $G$, and numerous other things.

These algorithms led to a revolution, resulting in advanced mathematical software like GAP¹ which can be used to do truly breathtaking group-theoretic calculations.

Permutation groups remain the most practical and widely used algebraic structure that admits feasible computation. My Common Lisp library CL-PERMUTATION handles them nicely.

The Clifford group, though, is usually constructively specified as a matrix group generated by matrix and tensor products of a set of generators. For example, let

$$ \Gamma := \left\{ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}, \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} \right\}. $$

Then the Clifford group on $n$ qubits is constructed as

$$ C_n = \langle g\in\Gamma^{\otimes n} \mid \dim g = 2^n \rangle. $$

Such a construction is obtuse at best, and admits not much more than ways to mechanically simulate, or treat the group as a black-box.

Sometime, around 2018, I had a discussion my then-colleague Charles Hadfield about how we might be able to leverage computational group theory to study the Clifford group. Lazily, I had already Google’d around and wasn’t coming up with anything. About a day later, Charles came back to me with an answer that led me to have the biggest mathematical facepalm.

The usual definition, which I avoided giving above, is full of mathematical jargon about normalizers and quotients. Much simpler (and of course essentially equivalent) is to see an element of the Clifford group, say $g\in C_n$, as one that conjugates Pauli group ($P_n$) elements to Pauli group elements. That is to say, $g\in C_n \Leftrightarrow gP_ng^{-1} = P_n$.

But this is none other than a permutation! It works as follows:

Label each element of the Pauli group $P_n$ from $1$ to $\vert P_n\vert=4^{n+1}$. Call them $(p_1, \ldots, p_{4^{n+1}})$.
Compute the action of $p_j = g p_i g^{-1}$ for all $i$.
The permutation encoding of $g$ is thus the product of the maps $i\mapsto j$.

In plain English, enumerate the Paulis and look at where they go under conjugation. Paired with your favorite Clifford group generators, you now have an object suitable for the machinery of computational group theory.

This is of course an expensive representation of the Clifford group, seeing as elements of $C_n$ need to be represented as arrays of $4^{n+1}$ machine integers. We can easily reduce this to $2^{2n+1}-2$ by exploiting symmetries. In quantum computing, $n$ is usually not very large anyway, usually $n<10$.

This logic is implemented in QUILC. After downloading QUILC and CL-PERMUTATION, one can experiment.

$ sbcl
> (ql:quickload "cl-quil")
> (in-package #:cl-quil.clifford)
> (defvar C4 (clifford-group-as-perm-group 4))
C4
> (perm:group-order C4)
12128668876800
> (perm:random-group-element C4)
#<PERM 277 278 381 382 103 104 445 446 168 167 192 191 469 470
       472 471 205 206 166 165 431 432 102 101 368 367 280 279
       14 13 142 141 407 408 496 495 230 229 303 304 37 38 77
       78 344 343 342 341 64 63 39 40 318 317 231 232 510 509
       405 406 127 128 352 351 118 117 30 29 264 263 221 222
       455 456 416 415 182 181 183 184 429 430 453 454 207 208
       261 262 15 16 119 120 365 366 493 494 247 248 144 143
       389 390 79 80 325 326 302 301 55 56 53 54 287 288 327
       328 94 93 392 391 158 157 245 246 480 479 209 210 451
       452 428 427 185 186 364 363 121 122 18 17 260 259 266
       265 28 27 115 116 354 353 180 179 417 418 457 458 219
       220 91 92 329 330 290 289 52 51 481 482 244 243 156 155
       393 394 388 387 146 145 250 249 492 491 57 58 300 299
       324 323 81 82 433 434 164 163 204 203 474 473 11 12 282
       281 369 370 99 100 105 106 379 380 276 275 1 2 467 468
       193 194 170 169 443 444 316 315 42 41 66 65 340 339 129
       130 403 404 507 508 233 234 228 227 497 498 409 410 140
       139 345 346 76 75 35 36 306 305 211 212 450 449 425 426
       187 188 361 362 123 124 20 19 257 258 268 267 25 26 114
       113 356 355 177 178 419 420 459 460 218 217 90 89 331
       332 292 291 49 50 483 484 241 242 153 154 395 396 385
       386 148 147 252 251 489 490 59 60 297 298 321 322 83 84
       435 436 161 162 201 202 476 475 10 9 284 283 371 372 98
       97 107 108 378 377 273 274 3 4 466 465 195 196 172 171
       442 441 313 314 44 43 68 67 337 338 131 132 402 401 506
       505 235 236 225 226 499 500 411 412 137 138 347 348 73
       74 34 33 308 307 5 6 271 272 375 376 109 110 439 440
       174 173 198 197 463 464 478 477 199 200 160 159 437 438
       96 95 374 373 286 285 8 7 136 135 413 414 502 501 224
       223 309 310 31 32 71 72 350 349 336 335 70 69 45 46 312
       311 237 238 504 503 399 400 133 134 358 357 112 111 24
       23 270 269 215 216 461 462 422 421 176 175 189 190 423
       424 447 448 213 214 255 256 21 22 125 126 359 360 487
       488 253 254 150 149 383 384 85 86 319 320 296 295 61 62
       47 48 293 294 333 334 88 87 398 397 152 151 239 240 486
       485>
> (perm:to-cycles * :canonicalizep nil)
(#<CYCLE (292 291)*>
 #<CYCLE (173 393 174 394)*>
 #<CYCLE (411 286 217 193 164 289 331 371)*>
 #<CYCLE (122 157 219 170 243 409 374 138)*>
 #<CYCLE (412 285 218 194 163 290 332 372)*>
 #<CYCLE (121 158 220 169 244 410 373 137)*>
 #<CYCLE (459 422 223 316 322 162 330 283)*>
 #<CYCLE (92 120 391 439 237 233 403 160)*>
 #<CYCLE (460 421 224 315 321 161 329 284)*>
 #<CYCLE (91 119 392 440 238 234 404 159)*>
 #<CYCLE (461 176 387 375 347 172 155 457)*>
 #<CYCLE (59 405 437 312 60 406 438 311)*>
 #<CYCLE (462 175 388 376 348 171 156 458)*>
 #<CYCLE (54 317 83 453 270 258 449 112)*>
 #<CYCLE (467 447 358 338 377 73 455 215)*>
 #<CYCLE (53 318 84 454 269 257 450 111)*>
 #<CYCLE (468 448 357 337 378 74 456 216)*>
 #<CYCLE (32 141 260 426)*>
 #<CYCLE (477 359 131 428 72 222 444 400)*>
 #<CYCLE (31 142 259 425)*>
 #<CYCLE (478 360 132 427 71 221 443 399)*>
 #<CYCLE (27 280 178 145 28 279 177 146)*>
 #<CYCLE (487 85 207 105 325 476 126 479)*>
 #<CYCLE (26 367 225 42 38 229 340 274)*>
 #<CYCLE (488 86 208 106 326 475 125 480)*>
 #<CYCLE (25 368 226 41 37 230 339 273)*>
 #<CYCLE (489 319 435 45 344 465 423 309)*>
 #<CYCLE (24 101 389 109 55 231 129 451)*>
 #<CYCLE (490 320 436 46 343 466 424 310)*>
 #<CYCLE (23 102 390 110 56 232 130 452)*>
 #<CYCLE (491 296 484 149 354 43 77 182)*>
 #<CYCLE (22 432 335 107 302 396 197 474)*>
 #<CYCLE (492 295 483 150 353 44 78 181)*>
 #<CYCLE (21 431 336 108 301 395 198 473)*>
 #<CYCLE (493 61 127 209 379 34 408 95)*>
 #<CYCLE (20 165 52 40 304 386 272 267)*>
 #<CYCLE (494 62 128 210 380 33 407 96)*>
 #<CYCLE (19 166 51 39 303 385 271 268)*>
 #<CYCLE (497 293 49 64 351 313 297 241)*>
 #<CYCLE (18 206 100 143 266 124 246 139)*>
 #<CYCLE (498 294 50 63 352 314 298 242)*>
 #<CYCLE (17 205 99 144 265 123 245 140)*>
 #<CYCLE (499 333 98 248 346 196 203 369)*>
 #<CYCLE (16 471 255 211 276 113 287 90)*>
 #<CYCLE (500 334 97 247 345 195 204 370)*>
 #<CYCLE (15 472 256 212 275 114 288 89)*>
 #<CYCLE (501 88 262 188 323 201 282 420)*>
 #<CYCLE (12 191 433 70 263 361 402 200)*>
 #<CYCLE (502 87 261 187 324 202 281 419)*>
 #<CYCLE (11 192 434 69 264 362 401 199)*>
 #<CYCLE (503 398 464 190 82 430 349 442)*>
 #<CYCLE (10 167 481 253 306 147 115 327)*>
 #<CYCLE (504 397 463 189 81 429 350 441)*>
 #<CYCLE (9 168 482 254 305 148 116 328)*>
 #<CYCLE (505 152 179 250 75 416 135 364)*>
 #<CYCLE (8 446 134 186 299 153 417 413)*>
 #<CYCLE (506 151 180 249 76 415 136 363)*>
 #<CYCLE (7 445 133 185 300 154 418 414)*>
 #<CYCLE (507 239 228 65 118 93 365 235)*>
 #<CYCLE (4 382 307 252 36 495 47 342)*>
 #<CYCLE (508 240 227 66 117 94 366 236)*>
 #<CYCLE (3 381 308 251 35 496 48 341)*>
 #<CYCLE (509 486 384 6 104 80 184 58)*>
 #<CYCLE (2 278 355 68 29 14 470 214)*>
 #<CYCLE (510 485 383 5 103 79 183 57)*>
 #<CYCLE (1 277 356 67 30 13 469 213)*>)

The cool thing is that these operations all happen basically instantaneously.

P.S. This insight is easily achieved by asking an LLM. Who needs mathematicians anymore? :-)

Unfortunately, like a lot of mathematical software born in and around the 1980s, it became its own bespoke, awful, underspecified, imperative programming language with a variety of algebraic APIs. The system can be learned about from its website. ↩︎