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:

enter image description here

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:

enter image description here

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?

draks ...

Posted 2020-04-25T14:50:58.190

Reputation: 578

1If 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 – 2020-04-25T15:04:15.807

@nr2618 ok, but that's just some 1qubit gates away, right? – draks ... – 2020-04-25T15:08:29.313

Yes, it's just a comment on the line in the question that says "Starting from $\vert 0,0.. 0\rangle$.." – rnva – 2020-04-25T15:12:06.783

If you leave a comment along with a downvote I can work on it... – draks ... – 2020-04-27T08:58:00.613



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.


Posted 2020-04-25T14:50:58.190

Reputation: 443

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? – draks ... – 2020-04-25T21:00:46.687

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 – 2020-04-25T22:32:13.200

You can implement any controlled permutation using a combination of controlled swap gates (

– rnva – 2020-04-25T22:37:43.717

Hi, I added further explanations and examples to my question and would be happy if you could have a look. Thanks... – draks ... – 2020-04-27T06:27:09.647


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.

Craig Gidney

Posted 2020-04-25T14:50:58.190

Reputation: 11 207


@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. – Craig Gidney – 2020-04-27T10:31:01.000

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? – draks ... – 2020-04-27T10:46:51.957

@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. – Craig Gidney – 2020-04-30T00:33:51.160