Controlled NOT Gate: Explained

[Dragonfall]

I'm not sure where to post this, so here it is:

$$\left[\begin{array}{cccc} 1&0&0&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0\\ \end{array}\right]$$

How is this a controlled NOT gate? If I multiply this with $$\left[\begin{array}{c}1\\0\\1\\0\end{array}\right]$$, the second bit is flipped regardless.

 

[Hurkyl]

That looks fine to me. Maybe it would be more clear with Kronecker products in the ket notation? Let |0> and |1> denote the standard basis on C². Then...

$$\left[\begin{array}{c}1\\0\\1\\0\end{array}\right] = |0\rangle \otimes |0\rangle + |1\rangle \otimes |0\rangle$$

while

$$\left[\begin{array}{c}1\\0\\0\\1\end{array}\right] = |0\rangle \otimes |0\rangle + |1\rangle \otimes |1\rangle$$

 

[Dragonfall]

Which coordinates in that column vector represents the control, and which the target bit?

 

[Hurkyl]

Which coordinates in that column vector represents the control, and which the target bit?

You're thinking classically. Your state vector cannot be partitioned into "control" and "target" parts -- instead, the vector represents the joint amplitudes of the two qubits. In your chosen basis, the components of the state vector correspond to each of the four ways to choose a basis vector for each qubit. If you had three qubits, your state vector would have eight components.

Algebraically, the joint state space is the tensor product of the individual state spaces. You, however, were thinking of the direct sum (equivalently, direct product) of the individual state spaces.

 

[Dragonfall]

So suppose my control bit is 0, and target is 1, then the vector representing the joint amplitudes of them (on which the matrix acts) is $$\left[\begin{array}{c}1\\0\end{array}\right] \otimes \left[\begin{array}{c}0\\1\end{array}\right] = \left[\begin{array}{c}0\\1\\0\\0\end{array}\right]$$

 

[Hurkyl]

That looks right.