The weight distribution of uniformly random Clifford conjugation

Question

For an $n$ qubit system, I fix a non-identity Pauli $P$ and perform the following experiment $N$ times:

1. Sample a Clifford gate $U_i$ uniformly at random from the Clifford group (iid).
2. Compute $w_i$, the weight of $U_i^\dagger P U_i$

Is there an expression for the distribution of weights $\{w_i\}$ (asymptotically or for fixed $N$)?

If it is not known, do we know any interesting properties of the distribution? E.g. how does the distribution depend on $P$? What is the expected weight? How close is the distribution to that induced by sampling random Paulis (see below)?

---

For instance, if instead of steps (1)-(2) we sampled $P_i$ uniformly at random from the Pauli group, then we would expect the probabilty distribution of $w$ to look like $$ \text{Pr}(\text{weight}=w)= 4^{-n}{n \choose w } 3^w. $$ As far as I know, this is a completely different distribution than the one described here Is this the distribution induced by the procedure above?

Answer 1

The probability distribution induced by $U P U^\dagger$ where $U\sim\mathrm{Cl}_n$ and $P\neq I$ is indeed the uniform one on non-identity Paulis (up to signs).

This somewhat counts as folklore knowledge, which is used in different variations in the literature. To the best of my knowledge, it is not written up anywhere, because it is an immediate consequence of the transitivity of the Clifford group action.

Here's a short proof. Note that the conjugation action of the Clifford group $\mathrm{Cl}_n$ is Hermiticity-preserving, thus we consider only Hermitian elements of the Pauli group, i.e operators of the form $\pm Q$ with $Q$ a Pauli operator. This action has two orbits: The identity $\{\pm I\}$, and the non-identity Paulis $\mathcal{Q}=\{ \pm Q | Q\neq I \}$. In other words: The action is transitive on $\mathcal{Q}$. These statements follow easily from the corresponding transitive action of the symplectic group on the phase space $\mathbb{F}_2^{2n}$ (and is equivalent to the Clifford group being a 2-design [Zhu]).

Now, fix a Pauli $P\neq I$, and let $\mathrm{Cl}_{n,P}$ be its stabilizer, i.e. all Cliffords that fix $P$. By the orbit-stabilizer theorem, the image of $P$ under the group action is isomorphic to the cosets of $\mathrm{Cl}_{n,P}$, this is $\mathrm{Cl}_n\, /\, \mathrm{Cl}_{n,P}$, and by transitivity, this image is simply $\mathcal{Q}$. Note that transitivity also implies, that this does not depend on the choice of $P$. To summarize, we have $$ \mathrm{Cl}_n\, /\, \mathrm{Cl}_{n,P} \simeq \mathcal{Q} = \{ \pm Q | Q\neq I \} \,. $$ Now, we compute the induced probability distribution: $$ \mathrm{Pr}[Q] := \mathrm{Pr}_{U}[Q = UPU^\dagger] = 1_{\mathcal{Q}}(Q) \frac{|\mathrm{Cl}_{n,P}|}{|\mathrm{Cl}_n|} = 1_{\mathcal{Q}}(Q) \frac{1}{|\{ \pm Q | Q\neq I\}|} = 1_{\mathcal{Q}}(Q) \frac{1}{2(2^{2n}-1)} \,, $$ where $1_{\mathcal{Q}}$ is the indicator function on $\mathcal{Q}$.

Thus, the weight distribution is $$ \mathrm{Pr}[Q \in \mathcal{Q} \text{ has weight } w] = \frac{1}{2(2^{2n}-1)} \binom{n}{w} 3^w\,. $$ Note the different normalization, because it is a distribution on $\mathcal{Q}$.

[Zhu]: Huangjun Zhu. “Multiqubit Clifford groups are unitary 3-designs”

Answer 2

Just brute force enumerating all the Cliffords seems to indicate they follow the simple rule (up to tiny deviations due $I^{\otimes N}$ being its own island).

import collections
import math

import stim

for n in range(1, 4):
    weights = collections.Counter()
    while True:
        ps = stim.PauliString.random(n)
        if ps.weight != 0:
            break
    for t in stim.Tableau.iter_all(num_qubits=n, unsigned=True):
        image = t(ps)
        weights[image.weight] += 1
    print(
        n,
        [
            weights[w]
            for w in range(1, n + 1)
        ],
        [
            math.factorial(n) // math.factorial(w) // math.factorial(n - w) * 3**w * sum(weights.values()) * 10**6 // (weights[w] * (4**n - 1)) / 10**6
            for w in range(1, n + 1)
        ])

1 [6] [1.0]
2 [288, 432] [1.0, 1.0]
3 [207360, 622080, 622080] [1.0, 1.0, 1.0]