<p>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.</p>

<p>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:</p>

<p>$$\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.</p>

CC BY-SA 3.0
2015-01-20T20:47:31.757Z
Great. Do you know a reference where something like this was used?
draks ...
CC BY-SA 3.0
2015-01-20T02:54:16.810Z
2015-01-20T15:05:10.313Z
2015-01-20T15:05:10.313Z
Peter Shor 
<p>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?</p>

<p>Choose $n$ to a power of $2$ if you need...</p>

CC BY-SA 3.0
2015-01-19T22:34:06.007Z
Huh...why the downvote? Is something wrong or trivial?
draks ...
CC BY-SA 3.0
2015-01-20T03:03:56.067Z
Sometimes we get random downvoters on stackexchange sites.
Peter Shor 
<quantum-computing><gr.group-theory>
Efficient generation of permutational invariant quantum states
draks ...
# Efficient generation of permutational invariant quantum states

(Asked by: username_0 on 2015-01-19)

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...

**Tags:** quantum-computing, gr.group-theory
> **Comments:**
> **username_0**: Huh...why the downvote? Is something wrong or trivial?  
> **username_1**: Sometimes we get random downvoters on stackexchange sites.  

---

## 1 answers

### Answer by username_1 on 2015-01-20. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: Great. Do you know a reference where something like this was used?  

---

