Efficient generation of permutational invariant quantum states 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...
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 &amp; \ \ \ \emptyset \\
4211 &amp; 2 \\
211 &amp; 25 \\
11 &amp; 253 \\
1 &amp; 2531 \\
\emptyset \ \ \  &amp; 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.