Efficient generation of permutational invariant quantum states

Question

Starting from $|00\cdots 0\rangle$, can permutational invariant quantum states, i.e. the following one: $$ |\psi_n\rangle = \frac1{n!} \sum \prod_{\pi\in S_n} |\pi(0)\rangle|\pi(1)\rangle\cdots|\pi(n-1)\rangle, $$ where $\pi$ runs over all permutations of the symmetric group $S_n$, e.g. $$ |\psi_3\rangle = \frac16\left(|012\rangle+|021\rangle+|201\rangle+|210\rangle+|201\rangle+|210\rangle\right) $$ be generated efficiently, i.e. in polynomial time? If so, how?

Choose $n$ to a power of $2$ if you need...

Answer 1

Yes, they can. Recall that any reversible classical function can be computed in superposition. Now, generate the state $$ \frac{1}{\sqrt{n!}}\left(\sum_{i=1}^n |i \rangle \right) \left( \sum_{i=1}^{n-1} |i \rangle \right)\left(\sum_{i=1}^{n-2} |i\rangle \right) \ldots \left(\sum_{i=1}^2 |i\rangle \right) \bigg(| 1\rangle \bigg) . $$ This is the superposition of all sequences where the $i$'th position contains a number between 1 and $n+1-i$. It's easy to generate because it's a tensor product of $n$ registers.

Then, find a reversible classical mapping from these sequences to permutations. One way of doing this is as follows. If there is an $i$ in the $t$'th position, take the $i$'th unused number available for the permutation. For example: suppose we have the sequence 24211. This gets mapped to the permutation as follows:

$$\begin{array}{r|l} 24211 & \ \ \ \emptyset \\ 4211 & 2 \\ 211 & 25 \\ 11 & 253 \\ 1 & 2531 \\ \emptyset \ \ \ & 25314 \end{array} $$ To illustrate, the third element of the permutation is $3$ because at the third step, the available numbers are $1$, $3$, $4$, ($2$ and $5$ are already in use) and the second of these is $3$. You can easily check that each of these steps is a reversible computation, and so implementable in superposition on a quantum computer.