# Density matrices of multiples copies of a single Haar-Random state

In Pseudorandom States, Non-Cloning Theorems and Quantum Money, the authors state that:

Let $$\rho_\mu^m$$ be the density matrix of a random $$|\psi\rangle^{\otimes m}$$ for $$|\psi\rangle$$ chosen from the Haar measure $$\mu$$. It is well-known that $$\rho_\mu^m=\begin{pmatrix}N+m-1\\m\end{pmatrix}^{-1}\sum_{\mathbf{x};\mathrm{Sym}}|\mathbf{x};\mathrm{Sym}\rangle\langle\mathbf{x};\mathrm{Sym}|$$

where $$N$$ is the dimension of the original Hilbert space we're working with (the one in which $$|\psi\rangle$$ lives), $$m$$ is the number of copies and $$|\mathbf{x};\mathrm{Sym}\rangle$$ is defined as: $$|\mathbf{x};\mathrm{Sym}\rangle=\frac{1}{\sqrt{\left(\prod_{j\in\mathcal{X}}m_j!\right)m!}}\sum_{\sigma\in\mathfrak{S}_m}\left|x_{\sigma(1)},x_{\sigma(2)},\cdots,x_{\sigma(m)}\right\rangle$$ with $$1\leqslant x_i\leqslant N$$ representing a vector from the canonical basis of the Hilbert space.

Is there a paper or a textbook where this fact is proven?

You can think of this as a generalization of the maybe better-known result that $$\int d\psi \,\mathbb{P}_\psi = \frac{I}{d},$$ where I used the notation $$\mathbb{P}_\psi\equiv|\psi\rangle\!\langle\psi|$$ to denote the projection onto the pure state $$\psi$$, and the integral is taken with respect to the uniform Haar measure in the space of (pure) states. This fact is often seen in the slightly more general form: $$\int_{\mathbf U(d)} dU\, UXU^\dagger = \frac{\operatorname{tr}(X)I}{d},$$ for any linear operator $$X$$, with the integral over the uniform Haar measure in the unitary group $$\mathbf U(d)$$. This is essentially a direct consequence of Schur's lemma: you observe that this object commutes with the standard representation of $$\mathbf U(d)$$ on $$\mathbb{C}^d$$, and being this representation irreducible, the object must be a multiple of the identity. There are great explanations of this results on this site, see e.g. Show that, averaging over uniformly random unitaries, $\mathbb{E}[UXU^\dagger]=\operatorname{Tr}(X)\frac{I}{d}$, Why does the twirl of a quantum channel give a depolarizing channel?, Random quantum states and Schur-Weyl duality.

The same property generalizes to tensor products of the projection: you have $$\int d\psi\, \mathbb{P}_\psi^{\otimes t}= \frac{\Pi_{\rm sym}}{\binom{d+t-1}{t}}$$ with $$\Pi_{\rm sym}$$ the projection onto the symmetric subspace of $$(\mathbb{C}^d)^{\otimes t}$$. Think of it as the closest you can get to having an identity in this equation, due to the left-hand side only spanning symmetric vectors. Note that the symmetric subspace of $$(\mathbb{C}^d)^{\otimes t}$$ has dimension $$\binom{n+t-1}{t}$$, hence $$\operatorname{tr}(\Pi_{\rm sym})=\binom{n+t-1}{t}$$, and we thus need the normalization on the RHS to ensure an overall unit trace. Regarding this relation, see also Prove that uniformly random states have moments ${\bf E}_\psi|\langle x|\psi\rangle|^{2t}\sim1/\binom d t$.

The only missing aspect is the writing as a sum over permutations that you have in your $$|\mathbf x;\operatorname{Sym}\rangle$$. This is but a way to write explicitly what $$\Pi_{\rm sym}$$ is. To see it, observe that $$\Pi_{\rm sym}$$, being a projection, is characterised by the eigenspace corresponding to its $$\lambda=1$$ eigenvalue. This eigenspace must clearly be invariant permutations, since a totally symmetric vector remains such permuting its elements in any way. So to write the orthogonal vectors spanning this eigenspace, you can take different basis product states, symmetrize them, take the projection over the correponding symmetrized state, and iterate the procedure.

This is much easier to see than it is to explain I think. Consider the situation with $$t=2$$. You want the projection onto the symmetric subspace of $$(\mathbb{C}^d)^{\otimes 2}$$:

1. Consider $$|0,0\rangle$$. This is already symmetric, so we don't need to do anything else, and we get the first projector as $$\mathbb{P}(|0,0\rangle)$$.
2. Consider $$|1,1\rangle$$. Again, already symmetric. We get $$\mathbb{P}(|1,1\rangle)$$.
3. Consider now $$|0,1\rangle$$. Symmetrizing it we get $$|0,1\rangle+|1,0\rangle$$, with an added normalization factor. We thus get the projector $$\mathbb{P}\left(\frac{|0,1\rangle+|1,0\rangle}{\sqrt2}\right)$$.

In conclusion, the projection $$\Pi_{\rm sym}$$ equals $$\Pi_{\rm sym} = \mathbb{P}(|0,0\rangle) + \mathbb{P}(|1,1\rangle) + \mathbb{P}\left(\frac{|0,1\rangle+|1,0\rangle}{\sqrt2}\right).$$ You might also notice this equals $$\Pi_{\rm sym}=\frac{I+W}{2}$$ with $$W$$ the swap operator.

You can find a nice exposition of the symmetric space and how to write explicitly the associated projections in (Harrow 2013).