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, 2020 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$ Jul 15, 2020 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, 2020 at 7:17

1 Answer 1


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

  • $\begingroup$ Could you explain what the summation of Z_j represents? Is it a Pauli matrix? $\endgroup$ Jan 13, 2022 at 16:04
  • $\begingroup$ @Alternative7 Yes, $Z_j$ is the Pauli $Z$ matrix applied to qubit $j$ (tensored with identities on all other qubits) $\endgroup$
    – DaftWullie
    Jan 14, 2022 at 8:08
  • $\begingroup$ So the summation of the Pauli Z is their tensor product? I assume that H is a 8x8 matrix with 3 qubits, and since they're not under superposition the number of 1s is indicated by the location of single 1 among the elements in their state vector. (For ex, if the state vector is {10000000}^T, that means none of the qubits are in 1) Did I understand it right? $\endgroup$ Jan 14, 2022 at 9:19
  • $\begingroup$ No, the summation is not their tensor product. $\sum_{j=1}^j$Z_j$ means $Z\otimes I\otimes I+I\otimes Z\otimes Z+I\otimes I\otimes Z$. $\endgroup$
    – DaftWullie
    Jan 14, 2022 at 9:56
  • $\begingroup$ Ah, now I got it. You mean IZI, not IZZ, for the middle term, right? $\endgroup$ Jan 14, 2022 at 10:57

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.