Algorithm to compute the parity of n qubits in n/2 queries

Question

Deutsch's algorithm is a special case of Deutsch-Josza's algorithm where the number of qubits evaluated = 2. This is equivalent to performing the operation $x_1 ⊕ x_2$ i.e. checking the parity of 2 qubits. A corollary of Deutsch algorithm says that there is a quantum algorithm that checks the parity of $n$ qubits with at most $\frac{n}{2}$ queries. I'm trying to come up with such an algorithm.

At first, I thought of repeatedly applying Deustch's algorithm (i.e. operating on two qubits with the unitary for parity checking) and increasing the number of qubits by one every iteration. However this does not seem to give me the upper limit of $\frac{n}{2}$ queries which the corollary states. How do I reduce the number of queries? Is my approach even valid? If not, how would I go about doing this?

Answer 1

You should think of Deutsch's algorithm as comparing two different bit values, and telling you if they're the same or different. Now, if you need to know the parity of $n$ bits, think of this as comparing the parity of the first $n/2$ bits with the parity of the second $n/2$ bits. To compute either only requires $n/2$ queries.