The Exercise

On qubits with computational basis $\lvert 0 \rangle$, $\lvert 1 \rangle$, the gate $C^n(X)$ applies the NOT gate $X$ to a target qubit under $n$ control qubits: it flips the target between $\lvert 0 \rangle$ and $\lvert 1 \rangle$ exactly when every control is in $\lvert 1 \rangle$. The exercise is to build it on its own $n+1$ qubits, with no work qubits, from Toffoli gates (NOT gates with two controls), controlled NOT (CNOT) gates and single qubit gates, their number growing no faster than $n^2$.

Qubits and Gates

A quantum system is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ Two quantum systems $S$ and $T$ form the composite system $S \otimes T$, whose state space is the tensor product of the state spaces of $S$ and $T$.^✦ A pure state $\lvert \psi \rangle$ of a quantum system $S$ is a unit vector in the state space of $S$, determined physically up to a global phase.^✦ A unitary $U$ of a quantum system $S$, an evolution of $S$ as a closed system, is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦

The qubit $Q$ is the two level system whose state space is $\mathbb{C}^2$.^✦ For a bit $i \in \{0, 1\}$, the basis state $\lvert i \rangle$ of the qubit is the pure state whose vector is the standard basis vector $e_i$ of $\mathbb{C}^2$.^✦ The Pauli $X$, the quantum NOT, is the unitary of the qubit whose matrix in this basis is $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.$$(1)^✦

Controlled Gates

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 the target $S$ with operator $$C(U) = \lvert 0 \rangle\langle 0 \rvert \otimes 1 + \lvert 1 \rangle\langle 1 \rvert \otimes U .$$(2)^✦ The CNOT is $C(X)$.

For a system $S$, the register of $n$ control qubits on $S$ is the system $Q^{\otimes n} \otimes S$, with $Q^{\otimes 0} \otimes S = S$ and $Q^{\otimes (n+1)} \otimes S = Q \otimes (Q^{\otimes n} \otimes S)$.^✦ For a unitary $E$ of $S$, the gate $C^n(E)$ with $n$ controls is the unitary of $Q^{\otimes n} \otimes S$ given by the recursion $$C^0(E) = E, \qquad C^{n+1}(E) = C\bigl(C^n(E)\bigr),$$(3)^✦ It applies $E$ to $S$ when all $n$ controls are in $\lvert 1 \rangle$ and acts as the identity otherwise. The NOT with $n = k+1$ controls of the exercise is the gate $C^k(C(X))$, that is $k$ further controls on a CNOT, acting on the $k+2$ qubits of $Q^{\otimes k} \otimes (Q \otimes Q)$.

Counting Gates

A unitary $E$ of a system $S$ has elementary gate budget $(t, s)$ when, after identifying $S$ with a register of qubits by an isomorphism of systems, that is, an identification of their state spaces, $E$ is a circuit of at most $t$ NOT gates with at most two controls and at most $s$ single qubit gates, each of the latter acting alone or under one control.^✦

A classical block on $m$ qubits is a unitary $U$ of a register of $m$ qubits that acts on the computational basis as a list of $\ell$ NOT gates, each with at most two controls and its target outside them, run as a classical reversible circuit: $$U \bigl( \lvert c_1 \rangle \otimes \cdots \otimes \lvert c_m \rangle \bigr) = \lvert c'_1 \rangle \otimes \cdots \otimes \lvert c'_m \rangle$$(4) for every string $c$ of $m$ bits, where $c'$ is the output of the list on $c$. Its budget is $(\ell, 0)$.

A single qubit gate $V$ has budget $(0, 1)$, on its own or on one qubit beside idle ones, and so do the controlled gates $C(V)$ and $C(V^\dagger)$, with idle qubits before the control and between the control and the target. Budgets add under composition. If $E$ and $F$ have budgets $(t_1, s_1)$ and $(t_2, s_2)$, the circuit $F$ followed by $E$, the unitary $EF$, has budget $(t_1 + t_2, s_1 + s_2)$. A budget is kept when a unitary of $S$ is carried along an isomorphism of $S$ with another system $T$, and a budget $(t, s)$ may be raised to any $(t', s')$ with $t' \ge t$ and $s' \ge s$.

The Claim

What Is Checked

The claim is stated over the gate $C^k(C(X))$, made by the recursion (3) from the controlled gate (2) and the Pauli $X$ of (1) on the register $Q^{\otimes k} \otimes (Q \otimes Q)$, and over the elementary gate budget with its classical blocks (4).

About these constructions the library proves that $C(U)$ is unitary for every unitary $U$ of a system $S$, $C(U)^\dagger C(U) = C(U) C(U)^\dagger = 1$ on the state space of $Q \otimes S$, and that the matrix (1) is unitary, so that $X$, and through (3) every $C^k(C(X))$, is a unitary of its system.