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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.