Expressing CNOT in the eigenbasis of $X$ (Preskill lecture notes eq. 7.6)

In chapter 7, equation 7.6 says CNOT works as follows:

CNOT: $$\frac{1}{\sqrt{2}} (|0\rangle + |1\rangle )\otimes |x\rangle \rightarrow \frac{1}{\sqrt{2}} (|0\rangle + (-1)^x |1\rangle ) \otimes |x\rangle$$, where it acts trivially if the target is $$x=0$$ state, and it flips the control if the target is the $$x=1$$ state.

I've looked at a few other resources about CNOT and this is the first time I encountered the $$(-1)^x$$ term.

Could someone explain to me where that term comes from?

Given that the matrix representation of CNOT is $$\begin{pmatrix} 1 & 0 &0 &0 \\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{pmatrix}$$ I don't see how that $$(-1)^x$$ came about.

2 Answers

Expanding on Jalex

Look at what happens on the possible terms.

$$\begin{eqnarray*} \mid 0 \rangle \otimes \mid + \rangle &\to& \mid 0 \rangle \otimes \mid + \rangle\\ \mid 0 \rangle \otimes \mid - \rangle &\to& \mid 0 \rangle \otimes \mid - \rangle\\ \mid 1 \rangle \otimes \mid + \rangle &\to& \mid 1 \rangle \otimes \mid + \rangle\\ \mid 1 \rangle \otimes \mid - \rangle &\to& (-1) \mid 1 \rangle \otimes \mid - \rangle\\ \end{eqnarray*}$$

where the first 2 are unchanged because the control is $$0$$ so nothing happens. The third is unchanged because NOT applied to $$\mid + \rangle$$ just gives back $$\mid + \rangle$$. The last is the only one with change because NOT applied to $$\mid - \rangle$$ gives $$(-1) \mid - \rangle$$.

We can summarize these possibilities by knowing that $$\mid + \rangle$$ goes with $$x=0$$ and $$\mid - \rangle$$ with $$x=1$$ as:

$$\begin{eqnarray*} \mid 0 \rangle \otimes \mid x \rangle &\to& \mid 0 \rangle \otimes \mid x \rangle\\ \mid 1 \rangle \otimes \mid x \rangle &\to& (-1)^x \mid 1 \rangle \otimes \mid x \rangle\\ \end{eqnarray*}$$

The first two become the first one above. And third and fourth, the second above.

Now add the two together along with a $$\frac{1}{\sqrt{2}}$$ prefactor to give

$$\frac{1}{\sqrt{2}} ( \mid 0 \rangle + \mid 1 \rangle ) \otimes \mid x \rangle \to \frac{1}{\sqrt{2}} ( \mid 0 \rangle + (-1)^x \mid 1 \rangle ) \otimes \mid x \rangle$$

Here Preskill is using a physics convention that the states $$|x\rangle$$ are the eigenstates of the $$X$$ operator. So $$|x\rangle$$ with $$x=0$$ actually means $$|+\rangle$$ and with $$x=1$$ actually means $$|-\rangle$$.