# How to create a quantum algorithm that produces 2 n-bit sequences with equal number of 1-bits?

I am interested in a quantum algorithm that has the following characteristics:

1. output = 2n bits OR 2 sets of n bits (e.g. 2 x 3 bits)
2. the number of 1-bits in the first set of n-bits must be equal to the number of 1-bits in the second set. E.g. correct output = 0,0,0, 0,0,0 (both 3-bit sets have zero 1-bits); 1,0,0, 0,1,0 (both 3-bit sets have one 1-bit); 1,1,0, 0,1,1 (both 3-bit sets have two 1-bit)
3. Each time the quantum algorithm runs it must randomly return one of the possible solutions. There are 2 good ways to interpret "randomly return one of the possible solutions": (1) each possible good solution has equal chance of being returned by the quantum algorithm. (2) every possible good solution has a chance > 0 of being returned.

Any idea how I can best implement such an algorithm on a quantum computer ?

FYI I have tried the following algorithm (where n = 2 ) but it missed the 2 answers 0110 and 1001. screenshot of the quantum circuit + simulator output

• Classical algorithms are a special case of quantum algorithms, so why not just use an easy classical algorithm? – usul Jun 1 '18 at 14:40
• I am just learning about quantum computing. Understanding how simple problems can be translated into a quantum algorithm would hopefully help me some day to create quantum algorithms for problems that can not be handled by classical algorithms in a reasonable time frame. – JanVdA Jun 1 '18 at 15:14
• the quantum algorithm would provide a true random number generator (which a classical algorithm cannot) – Carlo Beenakker Jun 1 '18 at 19:02
• Questions liek this are well-received at quantumcomputing.stackexchange – Jalex Stark Jun 1 '18 at 20:05
• thanks for the comment - I have cross posted the question : quantumcomputing.stackexchange.com/questions/2209/… – JanVdA Jun 1 '18 at 20:26

Here is one way to achieve this, for concreteness described for $n=2$: Start with two registers of $2$ qubits, initialised as $|00\rangle|00\rangle$; apply a Hadamard transformation to each of the qubits in the first register, resulting in $$(|00\rangle+|10\rangle+|01\rangle+|11\rangle)|00\rangle$$ (I leave out the normalisation factor). Then apply a sequence of CNOT gates with qubit $p\in\{1,2,3\}$ from register 1 as control and qubit $p$ from register 2 as target. This produces the entangled state $$|00\rangle|00\rangle+|11\rangle|11\rangle+|10\rangle|10\rangle+|01\rangle|01\rangle$$ To obtain also the permutations $|10\rangle|01\rangle$ and $|01\rangle|10\rangle$ perform a square-root-of-SWAP operation $\sqrt{\text{SWAP}}$ on the qubits in the second register.
recall that $\sqrt{\text{SWAP}}|\alpha\beta\rangle=\frac{1}{\sqrt{2}}\left(|\alpha\beta\rangle+i|\beta\alpha\rangle\right)$
The resulting state is $$(1+i)|00\rangle|00\rangle+(1+i)|11\rangle|11\rangle+ |10\rangle(|10\rangle+i|01\rangle)+|01\rangle(|01\rangle+i|10\rangle)$$
• I just noticed that the cross-posted question on quantumcomputing.stackexchange follows a different approach using $n^2$ ancilla qubits in addition to the $2n$ data qubits to carry out the permutation. Which algorithm you prefer may depend on the available resources... – Carlo Beenakker Jun 2 '18 at 8:33
• I finally managed to validate this on IBM composer using the following implementation of $\sqrt{\text{SWAP}}$ : quantumcomputing.stackexchange.com/questions/2228/… . And exactly like you already predicted the even parity terms (0000, 1111) are double as likely as the odd parity terms. Excellent. – JanVdA Jun 6 '18 at 12:35