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:

parity measurement

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?


1 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:

trivial parity circuit

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

Z-ified parity circuit

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

rev-z'ed parity circuit

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

Single-column parity circuit

  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}$.

  • $\begingroup$ 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. $\endgroup$
    – ocket8888
    Apr 15, 2017 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.