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