Suppose we have a 3-qubit input; each bit is either 0 or 1. How to decide if there are more 1's than 0's? Only 1 extra qubit may be used for the output. (Yes I know this can be achieved using 3 Toffoli gates, but can it be done without Toffoli gates?)

Now suppose we have an answer to the above question, then, how to extend the above circuit to deal with a 5-qubit input?

  • $\begingroup$ do you know that this can be done, or are you just asking in hope? $\endgroup$ – DaftWullie Jul 14 at 16:01
  • $\begingroup$ @DaftWullie Thanks for the reply; I have rephrased my question. Could you please have a look at my second question? $\endgroup$ – Isomorphism Jul 15 at 0:52
  • $\begingroup$ I can do it (I believe, without having written it out completely) using no Toffolis but two ancilla qubits. $\endgroup$ – DaftWullie Jul 15 at 7:17

Here's a general strategy that doesn't quite fulfil the brief: for an $n$-qubit input where $n+1=2^k$, $k$ an integer (e.g. $n=3,k=2$), it uses $k$ ancilla qubits but no Toffolis. (You can do something similar if $n+1$ is not a powe of 2, but you'd need some classical post-processing and I'd have thought you might as well just measure the input qubits!)

The idea is to define a Hamiltonian $$ H=\left(\sum_{j=1}^nZ_j+nI\right)/2. $$ Note that this has eigenvalues $0,1,2,3,\ldots,n$ corresponding to the number of 1s in the string it's acting on. So, let $U=e^{2i\pi H/2^k}$. This is a unitary with the eigenvectors that we need. If you run a phase estimation procedure using $k$ ancilla qubits, it will exactly read out the number of 1s for you. This requires controlled-$U$, which is just a bunch of controlled-phase gates (i.e. all two-qubit gates) and the Fourier transform which, again, is two-qubit gates. Actually you only need the semi-classical Fourier transform, so it's just one-qubit gates with feed-forward of measurement results.

So, once you know who many 1s there are, you can classically process that to decide if it's greater than $n/2$. In the case of $n+1$ being a power of 2, this is particularly simple. You just look at the bit representation of the output, and the most significant bit will give you the answer. So, this would be the only qubit you would need to measure. (Note that this is the last bit output by the Fourier transform, not the first).

| improve this answer | |

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.