The Exercise

The exercise asks for a quantum circuit on three qubits that leaves the basis state $|000\rangle$ alone and moves each of the other seven computational basis states one step along a single cycle. On the labels this is the partial cyclic permutation $\pi$ of triples of bits: $$\pi(000) = 000, \qquad 001 \mapsto 010 \mapsto 011 \mapsto 100 \mapsto 101 \mapsto 110 \mapsto 111 \mapsto 001 .$$(1)^✦ The library’s answer is a circuit of eight gates, each a controlled NOT (CNOT) gate or a Toffoli gate on some of the three qubits.

Three Qubits

A quantum system $S$ is described by its state space, a finite dimensional complex Hilbert space.^✦ The composite system $S \otimes T$ of two systems $S$ and $T$ has for its state space the tensor product of their state spaces.^✦ The qubit $Q$ is the system whose state space is $\mathbb{C}^2$, and three qubits form the composite system $Q \otimes (Q \otimes Q)$.

A pure state $\psi$ of a system $S$ is a unit vector in the state space of $S$.^✦ For pure states $\psi$ of $S$ and $\varphi$ of $T$, the product $\psi \otimes \varphi$ is the pure state of $S \otimes T$ whose vector is the tensor product of the two vectors.^✦ The basis states $|0\rangle$ and $|1\rangle$ of the qubit are the pure states given by the standard basis vectors $e_0$ and $e_1$ of $\mathbb{C}^2$, and for bits $q_1$, $q_2$, $q_3$ the basis state of three qubits is the product $$|q_1 q_2 q_3\rangle = |q_1\rangle \otimes \bigl(|q_2\rangle \otimes |q_3\rangle\bigr).$$(2)

Gates

A unitary $U$ of a system $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$; it carries a pure state $\psi$ of $S$ to the pure state $U\psi$. The composite $UV$ of two unitaries $U$ and $V$ of $S$ applies first $V$, then $U$, and the identity evolution of $S$ is the unitary $1$. For unitaries $U$ of $S$ and $V$ of $T$, the product unitary $U \otimes V$ of $S \otimes T$ is the tensor product of the two operators.^✦ A gate $G$ on a system of qubits is a unitary of that system; on a composite system, a gate acting on the first factor alone is $U \otimes 1$, and one acting on the last factor alone is $1 \otimes V$.

The Pauli $X$, the quantum NOT, is the unitary of the qubit with matrix $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.$$(3)^✦ For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of $Q \otimes S$, with the qubit as control and $S$ as target, given by $$C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U.$$(4)^✦ The CNOT gate of two qubits is $C(X)$.^✦ For a unitary $U$ of the qubit, controlling once more gives the doubly controlled gate $C^2(U) = C(C(U))$ of three qubits, which applies $U$ to the third qubit when the first two are both $|1\rangle$; the Toffoli gate is $C^2(X)$.

A unitary $U$ of a system $S$ is the same thing as a linear isometric bijection of the state space of $S$ onto itself.^✦ The SWAP of two copies of $S$ is the unitary of $S \otimes S$ given by the isometry that exchanges the factors, $\mathrm{SWAP}(u \otimes v) = v \otimes u$.^✦ The reversed CNOT $\mathrm{CNOT}^{\mathrm{rev}}$ of two qubits, the CNOT with its control on the second qubit and its target on the first, is the unitary of $Q \otimes Q$ obtained by conjugating the CNOT with the SWAP of two qubits: $$\mathrm{CNOT}^{\mathrm{rev}} = \mathrm{SWAP}\;\mathrm{CNOT}\;\mathrm{SWAP}.$$(5)^✦

The Circuit

Write $\mathrm{CNOT}_{i \to j}$ for a CNOT on three qubits with control on qubit $i$ and target on qubit $j$, and $\mathrm{TOF}_{ij \to k}$ for a Toffoli gate with controls on qubits $i$ and $j$ and target on qubit $k$. On $Q \otimes (Q \otimes Q)$, $\mathrm{TOF}_{12 \to 3}$ is the Toffoli gate itself; $\mathrm{CNOT}_{1 \to 2} = C(X \otimes 1)$ and $\mathrm{TOF}_{13 \to 2} = C(\mathrm{CNOT}^{\mathrm{rev}})$ are controlled by the first qubit; $\mathrm{CNOT}_{2 \to 3} = 1 \otimes \mathrm{CNOT}$ and $\mathrm{CNOT}_{3 \to 2} = 1 \otimes \mathrm{CNOT}^{\mathrm{rev}}$ act on the last two.

An identification $e$ of a system $S$ with a system $T$ is a linear isometric bijection of the state space of $S$ onto that of $T$; its inverse $e^{-1}$ identifies $T$ with $S$, and a unitary $U$ of $S$ is carried along $e$ to the unitary $e\,U\,e^{-1}$ of $T$. The regrouping $\alpha$ of three systems $S_1$, $S_2$, $S_3$ is the identification of $S_1 \otimes (S_2 \otimes S_3)$ with $(S_1 \otimes S_2) \otimes S_3$ that sends $u \otimes (v \otimes w)$ to $(u \otimes v) \otimes w$.^✦ The gate $\mathrm{CNOT}_{2 \to 1}$ is $\mathrm{CNOT}^{\mathrm{rev}} \otimes 1$ on $(Q \otimes Q) \otimes Q$ carried along $\alpha^{-1}$ to three qubits: $$\mathrm{CNOT}_{2 \to 1} = \alpha^{-1} \bigl(\mathrm{CNOT}^{\mathrm{rev}} \otimes 1\bigr)\, \alpha .$$(6)^✦

The circuit $U_\pi$ for the partial cyclic permutation is the unitary of three qubits that applies these gates in turn, the rightmost first: $$U_\pi = \mathrm{CNOT}_{2 \to 3}\, \mathrm{CNOT}_{1 \to 2}\, \mathrm{TOF}_{12 \to 3}\, \mathrm{CNOT}_{3 \to 2}\, \mathrm{CNOT}_{2 \to 1}\, \mathrm{TOF}_{13 \to 2}\, \mathrm{CNOT}_{2 \to 1}\, \mathrm{CNOT}_{1 \to 2} .$$(7)^✦

The Claim

What Is Checked

The claim is stated over the circuit $U_\pi$ of (7), the basis states (2) and the permutation $\pi$ of (1).

About these constructions the library proves that the controlled gate $C(U)$ of (4) is unitary for every unitary $U$ of every system $S$, $C(U)^\dagger C(U) = C(U)\,C(U)^\dagger = 1$.^✦ With it, and with the unitarity of $X$, of composites and tensor products of unitaries and of a unitary carried along an identification, every gate of (7) and the circuit itself are unitaries of three qubits.