The Exercise

Two qubits, a control and a target, are in a state $\rho$, pure or mixed. The exercise is to write out explicitly, in the computational basis, the action of the controlled NOT gate (CNOT) on the density matrix of $\rho$.

Two Qubits

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ A pure state $\lvert\psi\rangle$ of $S$ is a unit vector in the state space of $S$.^✦ A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$.^✦

The qubit $Q$ is the quantum system whose state space is $\mathbb{C}^2$, and its computational basis states $\lvert 0\rangle$ and $\lvert 1\rangle$ are the pure states whose vectors are the standard basis vectors $e_0$ and $e_1$. The composite system $S \otimes T$ of two systems $S$ and $T$ is the system whose state space is the tensor product of their state spaces.^✦ The product $\lvert\psi\rangle \otimes \lvert\varphi\rangle$ of a pure state of $S$ and a pure state of $T$ is the pure state of $S \otimes T$ whose vector is the tensor product of the two vectors.^✦ Two qubits form the composite system $Q \otimes Q$, with the four product basis states $\lvert ab\rangle = \lvert a\rangle \otimes \lvert b\rangle$ for $a, b \in \{0, 1\}$.

The density matrix of a state $\rho$ of two qubits is the complex $4 \times 4$ matrix whose rows and columns are labelled by pairs of bits and whose entries are the matrix elements of $\rho$ between product basis states, $$\rho_{(a,b),(c,d)} = \langle ab \rvert\, \rho \,\lvert cd \rangle , \qquad a, b, c, d \in \{0, 1\}.$$(1)^✦

The CNOT Gate

A unitary $U$ of a system $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$, where $1$ is the identity on the state space of $S$.^✦ The evolution of a state $\rho$ of $S$ under a unitary $U$ of $S$ is the state $U \rho U^\dagger$.^✦

The Pauli $X$ gate, the quantum NOT, is the unitary of the qubit given on $\mathbb{C}^2$ by the matrix $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.$$(2)^✦

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of the composite system $Q \otimes S$ of a control qubit and a target $S$ given by $$C(U) = \lvert 0\rangle\langle 0\rvert \otimes 1 + \lvert 1\rangle\langle 1\rvert \otimes U ,$$(3)^✦ where $1$ is the identity on the state space of $S$.

The CNOT gate is the controlled gate $C(X)$ of two qubits, the first the control and the second the target: it flips the target exactly when the control is $\lvert 1\rangle$.^✦ On the product basis it therefore sends $\lvert ab\rangle$ to $\lvert \pi(a,b)\rangle$, where $\pi$ is the permutation of the four pairs of bits $$\pi(a, b) = (a,\, b \oplus a),$$(4)^✦ with $\oplus$ addition modulo $2$.

The Claim

What Is Checked

The claim is stated over an arbitrary state of two qubits, the CNOT gate as the controlled $X$ acting by conjugation, the density matrix (1) in the product basis and the permutation (4) of its labels.

About these constructions the library proves that the controlled gate (3) is unitary, $C(U)^\dagger C(U) = C(U)\, C(U)^\dagger = 1$, for every unitary $U$ of every system, and that the matrix $X$ is unitary, so that the CNOT gate is a unitary of two qubits. It proves as well that conjugating a density operator by a unitary gives a density operator, so that $\mathrm{CNOT}\,\rho\,\mathrm{CNOT}^\dagger$ is again a state, and that the tensor product of two unit vectors is a unit vector, so that each $\lvert ab\rangle$ is a pure state of the two qubits.