How can I see, without math, the action of a gate in matrix form?

Question

Suppose we have the Fredkin gate with

$$ F= \left( {\begin{array}{cc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} } \right) $$

But how is it possible to "see" what its action is without making any matrix multiplication?

In this document, on solving 4.25, they claim that the action of $F$ is, in the computational basis, $F|0,y,z\rangle=|0,y,z\rangle$ and $F|1,y,z\rangle=|1,z,y\rangle$. But how is it possible to know this beforehand? I feel that I am missing this mental "gymnastic" that I feel is crucial for developing algorithms.

Answer 1

Besides the already given answers note that there is indeed some "mental gymnastics" involved here. As soon as you're getting more acquainted with quantum computing, you know some of your usual gates, including the $\mathsf{SWAP}$ gate that appears in your question: \begin{align} \mathsf{SWAP} = \begin{bmatrix} 1 &0 &0 &0 \\ 0 &0 &1 &0 \\ 0 &1 &0 &0 \\ 0 &0 &0 &1 \\ \end{bmatrix} \end{align}

Now, how do we see that the Fredkin gate corresponds to a controlled $\mathsf{SWAP}$ gate? Looking closer at the Fredkin gate shows us that it has a block structure where the upper left block is an identity matrix and the lower right block is the $\mathsf{SWAP}$ gate: \begin{align} \mathsf{Fredkin} = \mathsf{CSWAP} = \begin{bmatrix} \mathbb{I} & 0 \\ 0 & \mathsf{SWAP} \end{bmatrix} \end{align}

And this structure is in fact general! All gates that are controlled on the first qubit have this block structure. Consider for example the well known $\mathsf{CNOT}$ gate \begin{align} \mathsf{CNOT} = \begin{bmatrix} 1 &0 &0 &0 \\ 0 &1 &0 &0 \\ 0 &0 &0 &1 \\ 0 &0 &1 &0 \\ \end{bmatrix}= \begin{bmatrix} \mathbb{I} & 0 \\ 0 & X \end{bmatrix} \end{align} which is an identity matrix on the upper left (hence the $\mathsf{C}$ in $\mathsf{CNOT}$) and a Pauli $\mathsf{X}$ gate -- which is the quantum $\mathsf{NOT}$ gate -- on the lower right.

So why is this the case? As pointed our by DaftWullie, we assume that the basis vectors in our Hilbert space correspond in ascending order to our basis states, i.e. \begin{align} 000, 001, 010, 011, 100, 101, 110, 111 \end{align} for three qubits. If we want to perform an arbitrary unitary $\mathsf{U}$ on the second and third qubit controlled by the first qubit, the corresponding matrix must act trivially (i.e. as identity matrix) on the first 4 basis vectors, just because for them the control bit is $0$. On the last 4 basis vectors, the control bit is $1$ and the operation $U$ is thus performed on these basis vectors. As the control bit must not change under the whole operation, the basis states starting with $0$ and the basis states starting with $1$ can not mix, yielding the overall matrix structure \begin{align} \mathsf{CU} = \begin{bmatrix} \mathbb{I} & 0 \\ 0 & \mathsf{U} \end{bmatrix} \end{align}

Answer 2

For a 0/1 matrix, the sort of protocol that I use is to write out the basis in the standard order. For three qubits, this is: 000,001,010,011,100,101,110,111 (the numbers 0 to 7 written in order in binary). You can list these next to the rows and the columns. Now, a given 1 entry in the matrix has a specific row and column (and there is only one of these for each row and column). The matrix acts to transform the column label into the row label.

So, for example, the first 4 elements $0xy$ all transform into themselves (because that part of the matrix is identity). Whereas 110 (penultimate column) transforms into 101, the 6th row.

Answer 3

We care about $F$'s action on the basis states, where basis states are represented by

\begin{equation}\begin{pmatrix} 1\\0\\0\\0\\0\\0\\0\\0 \end{pmatrix}, \begin{pmatrix} 0\\1\\0\\0\\0\\0\\0\\0 \end{pmatrix}, \ldots, \begin{pmatrix} 0\\0\\0\\0\\0\\0\\0\\1 \end{pmatrix}\end{equation}

It should be fairly easy to see that on most basis states, this gate will act as the identity. The only exceptions are $(0,0,0,0,0,1,0,0)^T$ and $(0,0,0,0,0,0,1,0)^T$, which get swapped.

States of the form $|0yz\rangle$ are those with a one in one of the first four rows. Clearly these don't get swapped.

States of form $|1yz\rangle$ have a one in one of the last four rows. Look how they get mapped:

\begin{align} |1yz\rangle :=|100\rangle &\mapsto |100\rangle = |1zy\rangle\\ |1yz\rangle :=|101\rangle &\mapsto |110\rangle = |1zy\rangle\\ |1yz\rangle :=|110\rangle &\mapsto |101\rangle = |1zy\rangle\\ |1yz\rangle :=|111\rangle &\mapsto |111\rangle = |1zy\rangle\\ \end{align}

as desired. What might be tripping you up is the fact that mapping $|100\rangle$ to $|100\rangle$ (and similarly for $|111\rangle$) can technically be thought of as swapping the last two bits.

What's the intuition? This gate is very close to being diagonal. It's easy to see the action of a diagonal matrix on a vector (especially a vector with only one nonzero entry, i.e. computational basis states), so my first instinct was to look at that action, and then assess where it deviates from diagonality and try to figure out what that deviation actually does.