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

  • $\begingroup$ Huh...why the downvote? Is something wrong or trivial? $\endgroup$ – draks ... Jan 19 '15 at 22:34
  • $\begingroup$ Sometimes we get random downvoters on stackexchange sites. $\endgroup$ – Peter Shor Jan 20 '15 at 3:03

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.

  • $\begingroup$ Great. Do you know a reference where something like this was used? $\endgroup$ – draks ... Jan 20 '15 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.