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.

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: enter image description here


2 Answers 2


There are probably better ways than this, but here’s one you could try:

Start as you have done, with Hadamards on every qubit of the first register, then controlled nots between matching pairs of qubits across the two registers. This creates a uniform superposition of terms $|x\rangle|x\rangle$.

Now you need to somehow perform a random permutation on the second register. Introduce $\binom{n}2$ ancillary qubits. Apply Hadamard on each, and use each qubit to control the application of a swap between a different pair of qubits on the second register. Then forget about the ancillary qubits, and just measure the first two registers. (I’m guessing this gives you a sufficiently random permutation.)

  • $\begingroup$ In the MathOverflow StackExchange: I have received a different answer on the same question (see mathoverflow.net/questions/301733/…). $\endgroup$
    – JanVdA
    Commented Jun 3, 2018 at 8:35
  • $\begingroup$ @JanVdA I see how that solution works for n=2. It’s not obvious to me how you generalise it to larger n, but that might just be me. Also, I inferred from your question that you wanted all outputs with equal probability, which isn’t the case there. $\endgroup$
    – DaftWullie
    Commented Jun 3, 2018 at 10:32
  • $\begingroup$ @JanVdA Perhaps the trick is to come up with something that works just like the quantum Fourier Transform, but just within fixed excitation subspaces. I'll have a think about this... $\endgroup$
    – DaftWullie
    Commented Jun 3, 2018 at 12:30
  • $\begingroup$ thanks for the answer, I have created a separate question for how to best handle the permutation issue : quantumcomputing.stackexchange.com/questions/2222/… $\endgroup$
    – JanVdA
    Commented Jun 3, 2018 at 12:43

I know we already have an answer here, but going back to the problem specification, there's a much simpler way to achieve this if the only thing that's important is the output, comprising a binary string. All the protocol actually has to do is:

  • Select an $n$-bit string, $x\in\{0,1\}^n$ at random. If you don't want to trust classical randomness, use $n$ qubits, starting in $|0\rangle$, with Hadamard acting on them, and measure in the computational basis. In fact, just use 1 qubit, and repeat the same thing $n$ times with it.

  • Let $w_x$ be the Hamming weight of $x$ (i.e. the number of 1s). Select a random $y\in\{0,1\}^n$ such that $w_y=w_x$. There are several ways you might do this, but, for example, use $m=\lceil\log_2\binom{n}{w_x}\rceil$ bits. Generate an answer $z\in\{0,1\}^m$ uniformly at random (i.e. $p_z=1/2^m$). $\binom{n}{w_x}$ of these strings $z$ can be mapped onto a suitable $y$. If a given answer cannot, just keep choosing a random $z$ until it can. On average, you won't need more than 2 gos.

  • Give the answer $x,y$.

  • $\begingroup$ thanks for the update. It is not yet fully clear to me. What do you mean by ... can be mapped onto a suitable y and how should this mapping be implemented on a quantum computer ? $\endgroup$
    – JanVdA
    Commented Jun 4, 2018 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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