I'm having trouble understanding why I'm getting the wrong answer when simplifying a quantum circuit:

The relevant matrices are \begin{align*} H = \frac{1}{\sqrt{2}}\left[\begin{matrix} 1 & 1 \\ 1 & -1\end{matrix}\right]\ ,\ X = \left[\begin{matrix} 0 & 1 \\ 1 & 0\end{matrix}\right]\ ,\ Z = \left[\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}\right] \end{align*}

and the middle gate is a CNOT: $\left[\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{matrix}\right]$

If the top qubit register is $|x\rangle$, the bottom is $|y\rangle$, and the computational basis is $\lbrace |0\rangle,|1\rangle\rbrace$, then:

\begin{align*} (H \otimes I)(I \otimes H)(I \otimes X^x)(H \otimes I)(I \otimes H)|x\rangle |y\rangle &= (H^2 \otimes HX^x H)|x\rangle |y\rangle \\ &= (I \otimes HX^x H)|x\rangle|y\rangle \end{align*}

But since $Z = HXH$, then $Z^x = (HXH)^x = HX^xH$, so:

\begin{align*} LHS = (I \otimes Z^x)|x\rangle|y\rangle \end{align*}

But this isn't correct. What you're supposed to get is $(X^y \otimes I)|x\rangle|y\rangle$. I can't see where the error is though.

• You're assuming things commute. They don't. The source of the problem is that you're using the incredibly misleading notation $I⊗X^x$, which is not a tensor product at all. Is that your notation? If not, whoever devised it laid a subtle trap for all their students, which you blundered into. Jul 19, 2016 at 13:16
• Thanks Peter! I've always thought that the notation was a little fishy. I got it from Nielsen & Chuang: i.imgur.com/ozBPDsF.png In certain simple cases, the notation appears to work, e.g. proving that CNOT can be constructed from a Controlled-Z and Hadamards: i.imgur.com/epWkxMe.png. However, I'm still a bit confused about when it's valid and when it's not. When you say that things don't commute, do you mean in particular that I can't commute Hadamard's through the control qubit? (Edit: Just saw the answer saying that this is indeed the commutation error.) Jul 20, 2016 at 1:58

That's... weird notation. $M^r$ means "apply operation $M$ controlled by qubit $r$"? (Please avoid calling your states $x$, $y$, or $z$ when you also have operations using those letters.)

Anyways, the mistake you made was passing a Hadamard gate over the control. I agree with Peter Shor about this being a mistake attributable to the notation being poor.

You did this:

x> --H--I----H--   =   x> --HH--I------
y> --H--X_x--H--       y> --H---X_x--H--


But that's not a valid transformation. That little 'x' by the big 'X' represents an operation conditioned on the first qubit. You have to look at the whole column to understand whether or not that I is lying to you or not (which is what makes the notation bad).

It's all very obvious when you just show the control inline:

--H--C--H--   !=   --HH--C-----
--H--X--H--        --H---X--H--


You'd be better off pretending controls can be represented by a matrix $C$ than continuing to do that subscript thing. Though I wouldn't recommend taking that $C$ thing too seriously.

Hint for the problem:

Merging the bottom Hadamards into the X to make a Z is a good idea. But before you can merge the top Hadamards you need to flip the controlled-Z.

Try doing it step by step by making small tweaks to the boxed-in part of this circuit in Quirk without changing the output superposition: