Generate a quantum state that sums up all permutations of elements

Question

First a definition: Let there be a quantum like that consists of $2^n=N$ partitions each of size $n=\log_2 N$: $$|x_0\rangle|x_1\rangle\cdots|x_{n-1}\rangle = |x_0x_1\dots x_{n-1}\rangle $$

Like in most state preparation schemes I start from $|00\dots0\rangle|00\dots0\rangle\cdots|00\dots0\rangle$ (where every $00\dots0$ represents a binary with $n$ bits, and I don't say that I permute $0$'s, it's just my initial state!). Is there an efficient way to generate to following quantum state: $$ \sum_{\pi_k\in S_N} |\pi_k(x_0x_1\dots x_{n-1})\rangle, $$ where $\pi(x_0x_1\dots x_{n-1})$ are all possible $n!$ permutations of $n$ elements. The final state is permutationally invariant under all permutations, but I'm not sure if this can be used for the generation.

I prefer implementations without measurements and no ancilla.

Update: A worked out example, another one and an inefficient way

Starting from the $2$ qubit state $|00\rangle$ I'd like to end with $\frac1{\sqrt 2}(|01\rangle+|10\rangle)$, which is accomplished by the following circuit:

Everything unitary! Since it was addresed in on of the answers: What happens to $|10 \rangle$? It revertibly maps to $\frac1{\sqrt 2}(|01\rangle-|10\rangle)$.

Let's try with $n=4$:

1. Let's start again with $$|00\rangle|00\rangle|00\rangle|00\rangle$$
2. Create a superposition in the first register: $$ \frac1{\sqrt 4}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)|00\rangle|00\rangle|00\rangle$$
3. Pick one, lets say $|11\rangle$. We need to split the second register in an equal superposition of 3 levels, but in a controlled way. So every unitary in the linked answer needs to be performed controlled by the first register, i.e. doubly controlled. There are four of these operations. Here is the circuit for register 1 and 2:

where I condensed the controlled-split-into-3 gate into a easy-to-replicate block. The Toffoli's after the block take care of the fact that we need to split into varying sets of 3, according to the first register.

EDIT Since they only idle around, I ommitted the third and forth register (qubits 5 to 8) in this step.

3. Along the same line for the third register, where we apply $4\cdot3=12$ operations, which split the third register in 2 levels vontrolled by the first and second register.
4. Another $24$ operations for the forth register or maybe less because we can skip those who have to end on a $|0\rangle$, because it is already there...

The final state I would get with this procedure, written in decimal basis is $$\tiny |3210\rangle+|2310\rangle+|3120\rangle+|1320\rangle+|2130\rangle+|1230\rangle+|3201\rangle+|2301\rangle+|3021\rangle+|0321\rangle+|2031\rangle+|0231\rangle+|3102\rangle+|1302\rangle+|3012\rangle+|0312\rangle+|1032\rangle+|0132\rangle+|2103\rangle+|1203\rangle+|2013\rangle+|0213\rangle+|1023\rangle+|0123\rangle $$ and in qubit representation: $$\tiny |11100100\rangle+|11100001\rangle+|11011000\rangle+|11010010\rangle+|11001001\rangle+|11000110\rangle+|10110100\rangle+|10110001\rangle+|10011100\rangle+|10010011\rangle+|10001101\rangle+|10000111\rangle+|01111000\rangle+|01110010\rangle+|01101100\rangle+|01100011\rangle+|01001110\rangle+|01001011\rangle+|00111001\rangle+|00110110\rangle+|00101101\rangle+|00100111\rangle+|00011110\rangle+|00011011\rangle $$

This approach extends to an exponential number of multiply controlled operations. Does anyone know if there is a more efficient one?

Answer 1

We start with the state $\vert x_1, x_2, ... x_n\rangle$ and wish to obtain the state $\frac{1}{\sqrt{n!}}\sum\limits_{k=1}^{n!}\hat{\pi}_k\vert x_1, x_2, ... x_n\rangle$.

First note that the operation is not a unitary operation. You cannot reverse it since the symmetrized state has lost information about the original $\vert x_1, x_2, ... x_n\rangle$. Therefore, the best you can achieve is the state $$\frac{1}{\sqrt{n!}}\sum\limits_{k=1}^{n!}\vert k\rangle\otimes\hat{\pi}_k\vert x_1, x_2, ... x_n\rangle.$$

The general idea to achieve this is by introducing $\log(n!)$ auxilliary qubit registers and defining control swap gates. I do not know if Qiskit has an efficient way to do this.

Answer 2

The operation as you have specified it is not reversible. For example, it would map $|a\rangle|b\rangle$ to the same state it maps $|b\rangle|a\rangle$ to. However, if you require that the list of input numbers is sorted and all elements are unique then it is possible and is explained in Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians by Berry et al.

The basic idea is to first produce a "sorting magic state" by sorting a list of 'random' integers using a reversible sorting network. Each integer in the list is initialized so that its qubits are a bunch of $|+\rangle$ states. After applying the sorting network to the integers, you will get as output the sorted list of integers and also ancillae related to how the comparisons played out within the sorting network. The ancillae are your magic state. To ensure the sorted list of integers is not entangled with this state, you measure it and confirm there are no duplicates in the list. If there are, restart the magic state preparation procedure.

Once you have your "sorting magic state", all you have to do is run the sorting network backwards. Except instead of feeding in the list of sorted integers that was used to produce the magic state, you instead feed in the sorted list of values you want to turn into a uniform superposition of all permutations in that list.