# How to compute k-moment of Haar averaging with n qubits

Let us consider the following Haar averaging over $$k$$ copies of Pauli strings of $$n$$ qubits:

$$\mathbb{E}_U \left[ U^{\otimes k}\sigma_{q_1} \otimes … \otimes \sigma_{q_k} (U^{\dagger})^{\otimes k}\right]$$

where the averaging is done with respect to the Haar measure $$U(2^n)$$, and $$\sigma_{q_j}$$ is a string of Paulis on $$n$$ qubits,$$\sigma_{q_j} \in \{I,X,Y,Z\}^{\otimes n}$$. Therefore, in every copy there are $$4^n$$ possible strings, and there are $$4^{nk}$$ operators of the form $$\sigma_{q_1} \otimes … \otimes \sigma_{q_k}$$. My question is, for how many of these operators will the averaging above yield exactly $$0$$? Is there a simple lower bound for this number?

Thank you very much for your help.

In general, $$\mathbb{E}_U \left[ U^{\otimes k}M (U^{\dagger})^{\otimes k}\right]$$ equals to the projection of $$M$$ onto the subspace of permutation matrices $$\Pi_\pi$$, $$\pi \in S_k$$ (permutations of $$k$$ elements), defined by $$\Pi_\pi |\psi_1\rangle \otimes \dots \otimes |\psi_k\rangle = |\psi_{\pi^{-1}(1)}\rangle \otimes \dots \otimes |\psi_{\pi^{-1}(k)}\rangle.$$ It's not that easy to compute this projection since $$\Pi_\pi$$ are not orthogonal to each other in the space of matrices. But the projection will be exactly $$0$$ iff projections of $$M$$ on each $$\Pi_\pi$$ are $$0$$. This is equivalent to $${\rm Tr}(M\Pi_\pi^\dagger) = 0,$$ for each $$\pi \in S_k$$.
There are ways to compute and estimate the dimension of the space spanned by all $$\Pi_\pi$$ (you can start here Schur–Weyl duality, also check this answer). Let's denote this dimension by $$r(k,2^n)$$. It follows that the number of $$M=\sigma_{q_1} \otimes … \otimes \sigma_{q_k}$$ which average to $$0$$ can't be bigger than $$4^{nk} - r(k,2^n)$$, since they are orthogonal to each other and to all $$\Pi_\pi$$. I'm not sure right now how to compute this exactly, but I hope this helps.