# How to permute (reshuffle) an n-bit input?

I am interested in a quantum algorithm that gets as input an n-bit sequence and that produces as output a reshuffled (permuted) version of this n-bit sequence.

E.g. if the input is 0,0,1,1 (so n=4 in this case) then the possible answers are:

• 0,0,1,1
• 0,1,0,1
• 0,1,1,0
• 1,0,0,1
• 1,0,1,0
• 1,1,0,0

Note that only one output should be generated which is randomly chosen among all possible valid outputs.

How can this best be implemented in a quantum algorithm ?

A solution for this is already proposed as part of one of the answers for How to create a quantum algorithm that produces 2 n-bit sequences with equal number of 1-bits?. But the problem with this solution is that this requires about $\binom{n}2$ help qubits which becomes rapidly huge if n is big.

Note:

• Please, do not provide a classical algorithm without any explanation of how the steps of the classical algorithm can be mapped to a universal quantum computer.
• for me there are 2 good ways to interpret "randomly chosen among all possible good outputs": (1) each possible good output has equal chance of being chosen. (2) every possible good output has a chance > 0 of being chosen.
• The input is a binary string of length $n$ where $k$ of the bits are 1's, and the output is any of the $\binom{n}{k}-1$ possible permutations of it? This can be done on a classical computer with 1 step. Do you want alll possible outputs? – user1271772 Jun 3 '18 at 17:15
• No, only one output should be generated which is randomly chosen amongst all possible outputs. – JanVdA Jun 3 '18 at 19:58
• Would a classical algorithm be good enough? (You could still run it on a quantum computer.) Or do you require sth. which outperforms the best classical algorithm? – Norbert Schuch Jun 3 '18 at 22:21
• @JanVdA: Why not just pick any 1 and any 0 and swap the two on a classical computer? – user1271772 Jun 4 '18 at 3:36
• As you have not specified the random distribution you want, I'll just leave these here: Dilbert and XKCD ;) – Ali Jun 5 '18 at 7:56

It could be done with $\lceil\log n\rceil$ additional qubits along these lines:

1. Transform the additional qubits so that they encode a number $k\in\{0,\ldots,n-1\}$ chosen uniformly at random.

2. Cyclically shift the input qubits $k$ times.

3. Let the last of the original input qubits be fixed as an output and recurse on the remaining $n-1$ of them.

This is a classical algorithm, but you can run it on a quantum computer of course, as Norbert has suggested in a comment. (The aspect of the question that is adamant about the algorithm being quantum is still not clear to me, so if running a classical algorithm such as the one I have suggested on a quantum computer is not sufficient, it would be helpful for the question to be clarified.)

Note that because the question asks for a random output, the algorithm is going to have to generate entropy at some point, presumably through measurements or performing other non-unitary operations on qubits (such as initializing them). In the algorithm above, it is the first step that generates entropy: regardless of the state of the additional qubits before the operation in step 1 is performed, they should have the state $$\frac{1}{n} \sum_{k = 0}^{n-1} \lvert k \rangle \langle k \rvert$$ after step 1 is performed (with $k$ encoded in binary, let's say).

• thanks for the answer. I am interested in an actual quantum algorithm for the problem - if you could map above classical algorithm to a quantum program then that it also fine but I have no clue how to do this. – JanVdA Jun 4 '18 at 15:15
• I think the question is now coming into focus: you're not really looking for an algorithm, you're looking for code. What I've described is an algorithm, and the task that remains is to implement that algorithm (or a different one) as code in some language or as the low-level description of a quantum circuit. I suggest you revise the question to make this more clear -- but be aware that you're asking someone to do tedious and conceptually uninteresting work for you. The alternative of learning how to do this yourself may seem daunting, but might end up being the better solution in the long run. – John Watrous Jun 4 '18 at 15:52
• I have added a note to the question. I think that we have interpreted the concept quantum algorithm differently. For me a_classical algorithm_ is not a quantum algorithm but might be mapped into a quantum algorithm. – JanVdA Jun 4 '18 at 17:14
• @JanVdA: What do you mean by quantum algorithm? For example, do you require that it involves at least one $H$ gate? Or that it requires at least one $Y$ gate? Or that it requires some other specific gate set? What gate set do you wish for this algorithm to use? – user1271772 Jun 5 '18 at 15:13
• A quantum algorithm is an algorithm that can be mapped (at step level) to a program for a universal quantum computer. The input and output of the steps of the quantum algorithm are qubits (or could be mapped to a series of qubits). The last step of the quantum algorithm = reading out (observing) the values of the qubits (so the qubits become mapped to actual bits) There are no restrictions on the gate set. The idea is that the complete algorithm can run on a universal quantum computer. – JanVdA Jun 5 '18 at 15:44

Note: this answer assumes you want the permutation to be coherent, i.e. you want $\frac{1}{\sqrt{3}} ( |001\rangle + |010\rangle + |100\rangle)$ instead of a 1/3 chance of $001$, a 1/3 chance of $010$, and a 1/3 chance of $100$.

Be careful how you specify this task, because it could very easily be impossible due to reversibility constraints. For example, for the input $|001\rangle$ you want to output the GHZ state $\left| {3 \atop 1} \right\rangle = \frac{1}{\sqrt{3}} (|001\rangle + |010\rangle + |100\rangle)$. But if you also want to output the GHZ state for the input $|010\rangle$ and $|100\rangle$, that won't work. You can't send multiple input states to the same output state (without decoherence). As long as you say "I only care about sorted-ascending inputs like 0000111 but not 1110000 or 0010110; you can do whatever you want with those", this will be fine.

One trick to producing a quantum permutation of a sorted input is to first prepare a "permutation state" by applying a sorting network to a list of seed values each in a uniform superposition. The sorting network will output qubits holding the sorted seeds, but also qubits holding the sorting network comparisons. The permutation state is just the comparison qubits. To apply it to your input, you simply run the input through the sorting network in reverse. Note that there are some tricky details here; see the paper "Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians". You would have to generalize this technique to work on inputs with repeated values, instead of only unique values.

You may also want to look into "quantum compression", which is very closely tied to the $\left| {n \atop k} \right\rangle$ states (uniform superpositions of all $n$-bit states with $k$ bits set) that you want to produce. The main difference is that you would run the quantum compression circuit in reverse, and it expects a number encoding "how many ones are there?" instead of "give me a state with the correct number of ones".

I guess what I'm saying is that producing these kinds of states is more complicated than you might have expected. I think the reason it is complicated is because the magnitude of the amplitudes in your outputs depend on the computational basis state of your input. For example, for $|0001\rangle$ you want an output which is a superposition of four classical states, so you have a prefactor of $\frac{1}{\sqrt{4}}$ hidden inside $\left| {4 \atop 1} \right\rangle$. But for $|0011\rangle$ the desired output has six classical states and so $\left| {4 \atop 2} \right\rangle$ hides a prefactor of $\frac{1}{\sqrt{6}}$.

• I need some more studying to value your answer but I don't fully agree with your 2nd paragraph about the reversibility constraint. Note that you have used $\frac{1}{\sqrt{3}} (|001\rangle + |010\rangle + |100\rangle)$ as solution for $|001\rangle$ but there are many more solutions as we are working with complex numbers (e.g. the following is also a possible solution $\frac{1}{\sqrt{3}} (|001\rangle - |010\rangle + i. |100\rangle)$ – JanVdA Jun 5 '18 at 12:29
• @JanVdA Correct, one can use the phases to make the various outputs orthogonal. My reading of your question was that you wanted the same phase in all cases. – Craig Gidney Jun 5 '18 at 12:34

A quantum computer can do classical computations. The optimal algorithm would be to:

1. Pick any bit (the fastest one you can get access to).
2. Find a bit that has the opposite value (if in step 1 you got a 0, find a 1)
3. Switch them (0 becomes 1 and 1 becomes 0).

Step 2 involves searching through an $N$ bit string which using classical operations takes $\mathcal{O}(N)$ operations, but if you can get the $n^{\textrm{th}}$ bit value by evaluating a function, you may be able to use Grover's quantum algorithm to find the opposite bit with $\mathcal{O}\left(\sqrt{N}\right)$ operations.

• Thanks but the algorithm would only switch 2 bits (so it won't generate all permutations) and it is still a classical algorithm, while I would like to see a quantum algorithm. – JanVdA Jun 4 '18 at 13:03