Parity Measurement Using a Single c-Z gate

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?

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: 1. Use $H \cdot Z \cdot H = X$ to replace those X gates with Z gates. 1. Use $C \otimes Z = Z \otimes C$ to flip the direction of control: 1. The operations have a common control, so shove 'em together: 1. 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}$.

• So I never really got around to writing my own answer, but I'd be happy to accept yours. There's just one thing I think should be clarified. A lot of the issues I was having stemmed from not understanding that the target gate could affect the control gate; I was thinking of the controls classically. Now that I understand phase kickback I understand how that circuit works, but that last line "how could this ever output anything but $0$?" demonstrates a lack of understanding entanglement through controlled gates. – ocket8888 Apr 15 '17 at 10:23