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

  • $\begingroup$ Classical algorithms are a special case of quantum algorithms, so why not just use an easy classical algorithm? $\endgroup$ – usul Jun 1 '18 at 14:40
  • $\begingroup$ 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. $\endgroup$ – JanVdA Jun 1 '18 at 15:14
  • $\begingroup$ the quantum algorithm would provide a true random number generator (which a classical algorithm cannot) $\endgroup$ – Carlo Beenakker Jun 1 '18 at 19:02
  • 1
    $\begingroup$ Questions liek this are well-received at quantumcomputing.stackexchange $\endgroup$ – Jalex Stark Jun 1 '18 at 20:05
  • $\begingroup$ thanks for the comment - I have cross posted the question : quantumcomputing.stackexchange.com/questions/2209/… $\endgroup$ – 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)$$
Finally measure the qubits in both registers to obtain a random output. The weights are such that there is equal probability to obtain one of the even parity terms (0000, 1111) as one of the odd parity terms (1010, 1001, 0101, 0110).

  • $\begingroup$ I have tried to simulate your algorithm (see i.stack.imgur.com/N3tzL.jpg) for n=2 but it missed the 2 correct answers 0110 and 1001. $\endgroup$ – JanVdA Jun 1 '18 at 14:11
  • $\begingroup$ indeed, I fixed that with a square-root-of-SWAP $\endgroup$ – Carlo Beenakker Jun 2 '18 at 8:27
  • $\begingroup$ 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... $\endgroup$ – Carlo Beenakker Jun 2 '18 at 8:33
  • $\begingroup$ thanks a lot for the answer - I am still figuring out how to simulate this. (quantumexperience.ng.bluemix.net/qx/community/…). $\endgroup$ – JanVdA Jun 3 '18 at 9:10
  • 1
    $\begingroup$ 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. $\endgroup$ – JanVdA Jun 6 '18 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.