# Generate a quantum state that sums up all permutations of elements

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.

1. 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.
2. 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?

• If you start from $\vert 0,0,...0\rangle$, the state is permutation invariant. You must start from $\vert x_1, x_2,.. x_n\rangle$ (you have to specify the $x_i$ for this input state) and then you can write a circuit that acheives a superposition of permutations.
– rnva
Apr 25 '20 at 15:04
• @nr2618 ok, but that's just some 1qubit gates away, right? Apr 25 '20 at 15:08
• Yes, it's just a comment on the line in the question that says "Starting from $\vert 0,0.. 0\rangle$.."
– rnva
Apr 25 '20 at 15:12
• If you leave a comment along with a downvote I can work on it... Apr 27 '20 at 8:58

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.

• If n=2 you end up with a Bell state and this and every other operation is unitary unless you invoke measurements. How do implement all the controlled permutations? Apr 25 '20 at 21:00
• If $n=2$, you end up with the state $\frac{1}{\sqrt{2}}(\vert 0\rangle\otimes\vert x_1, x_2\rangle + \vert 1\rangle\otimes \vert x_2, x_1\rangle)$. This is not a Bell State. I'm not sure what you mean by "this and every other operation is unitary". Symmetrization is not unitary unless you allow auxiliary qubits to store the lost information as explained in the answer.
– rnva
Apr 25 '20 at 22:32
• You can implement any controlled permutation using a combination of controlled swap gates (en.wikipedia.org/wiki/Quantum_logic_gate#Fredkin_(CSWAP)_gate).
– rnva
Apr 25 '20 at 22:37
• Hi, I added further explanations and examples to my question and would be happy if you could have a look. Thanks... Apr 27 '20 at 6:27

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.

• Hi, I added further explanations and examples to my question and would be happy if you could have a look. Thanks... Apr 27 '20 at 6:27
• @draks if you feed the state |0>|1>|2>... into the algorithm described by my answer you get the state asked for by your updated question. Apr 27 '20 at 10:31
• Are you looking at $(1)$? It carries an additional unwanted sign factor. And what if I need a procedure without measurements and no ancillas? Or do I need them to achieve a substantial speedup? Apr 27 '20 at 10:46
• @draks... Ah, yes, the paper adds phase factors so that odd permutations have a negative sign. Those are not an intrinsic part of the algorithm, just an extra detail that was added on. Apr 30 '20 at 0:33