Parity Measurement Using a Single c-Z gate

Question

I have a system with some number of qubits. To make it simple, but non-trivial, let's say that number is 3. I want to know the parity of the system's state (meaning I can assume that each individual qubit is either $|0\rangle$ or $|1\rangle$). In particular, I should do this using a single application of a c-$Z^{\otimes n}$ gate (where in this case $n=3$ and the 'c-' prefix indicates that the gate is 'controlled'). I've looked it up, and the solution appears to be something like this:

I've seen some parity implementations using cascading CNOT gates on a static $|0\rangle$ input, and that makes perfect sense to me. As you can see by the '?'s in this image, though, I don't get what this circuit is doing at all. The measurement seems to only apply to the bottom wire, but how could this ever output anything but a measurement of $H|+\rangle=|0\rangle$ or $0$ 100% of the time?

Answer 1

There are two key facts you need here: $H \cdot Z \cdot H = X$ and $C \otimes Z = Z \otimes C$. (Also, you should look up the concept of "phase kickback".)

1. Start with a trivial parity circuit:

2. Use $H \cdot Z \cdot H = X$ to replace those X gates with Z gates.

3. Use $C \otimes Z = Z \otimes C$ to flip the direction of control:

4. The operations have a common control, so shove 'em together:

5. You're done. You can replace the three small Z boxes with a single big $Z^{\otimes 3}$ box, but that's just decoration.

At first this kind of stuff seems weird, but as you start thinking of controls and operations as interchangeable it becomes natural. And the pattern "control the operation $U$ with $HCH$ to measure the observable $U$ (if $U$'s eigenvalues are all +1 and -1)" is quite common. In this case $U = Z^{\otimes 3}$.