The Exercise

Let $V$ be a unitary of one qubit. The gate $C^5(V^2)$ acts on six qubits, five controls and a target: when all five controls are in $\lvert 1 \rangle$ it applies $V$ twice to the target, and otherwise it acts as the identity. The task is to build this gate on the six qubits alone, with no work qubit, as a circuit of gates with fewer controls. Besides $V$ and its adjoint, the circuit may apply to the target further unitaries of a qubit chosen for the given $V$.

Qubits and Unitaries

A quantum system is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ The composite system $S \otimes T$ of two quantum systems $S$ and $T$ is the quantum system whose state space is the tensor product of the state spaces of $S$ and $T$.^✦ The qubit $Q$ is the quantum system whose state space is $\mathbb{C}^2$.^✦ A pure state $\psi$ of a system $S$ is a unit vector in the state space of $S$.^✦ The computational basis states $\lvert 0 \rangle$ and $\lvert 1 \rangle$ of the qubit are the pure states given by the standard basis vectors $e_0$ and $e_1$ of $\mathbb{C}^2$.^✦

A unitary $U$ of a system $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$, the evolution of $S$ as a closed system.^✦ The adjoint $U^\dagger$ of a unitary $U$ of $S$ is the unitary of $S$ given by the adjoint operator, and the identity $1$ of $S$ is the unitary given by the identity operator. For two unitaries $U$ and $V$ of $S$, the product $UV$ is the unitary of $S$ given by the composite operator: first $V$, then $U$.^✦

For unitaries $U$ of $S$ and $W$ of $T$, the product unitary $U \otimes W$ is the unitary of $S \otimes T$ whose operator is the tensor product of the operators of $U$ and $W$.^✦ The gate $U \otimes 1$ applies $U$ to $S$ and the identity to $T$; the gate $1 \otimes W$ applies the identity to $S$ and $W$ to $T$.

The Pauli $X$ gate, the quantum NOT, is the unitary of the qubit whose matrix in the computational 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 $Q \otimes S$, a control qubit followed by the target $S$, given by $$C(U) = \lvert 0 \rangle\langle 0 \rvert \otimes 1 + \lvert 1 \rangle\langle 1 \rvert \otimes U.$$(2)^✦

The control register of $n$ qubits around a system $S$ is the system $Q^{\otimes n} \otimes S$ of $n$ control qubits composed on the left of $S$ one at a time: $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$ that applies $E$ to $S$ when all $n$ control qubits are in $\lvert 1 \rangle$ and acts as the identity otherwise.^✦ The gate $C^n(E)$ is defined one control at a time by $$C^0(E) = E, \qquad C^{n+1}(E) = C\bigl(C^n(E)\bigr).$$(3)

For a unitary $E$ of $S$, the idle gate $1^{\otimes n} \otimes E$ is the unitary of $Q^{\otimes n} \otimes S$ that applies the identity to each of the $n$ qubits and $E$ to $S$.^✦

The Circuit

The circuit is assembled from layers of one shape, each given by a number $k$ of controls and a unitary $W$. Take a number $k$ of controls, a system $M$ with a unitary $W$, and the register $Q^{\otimes k} \otimes (Q \otimes M)$: $k$ control qubits, one further qubit $c$, and $M$. The Barenco reduction circuit $R_k(W)$, which is the layer, and its tail $T_k(W)$ are the unitaries of the register $Q^{\otimes k} \otimes (Q \otimes M)$ given by $$\begin{aligned} T_k(W) &= C^k(X \otimes 1)\,\bigl(1^{\otimes k} \otimes C(W^\dagger)\bigr)\, C^k(X \otimes 1)\,\bigl(1^{\otimes k} \otimes C(W)\bigr), \\ R_k(W) &= C^k(1 \otimes W)\,T_k(W), \end{aligned}$$(4) where $X \otimes 1$ is the NOT on $c$ with $M$ idle and $1 \otimes W$ is $W$ on $M$ with $c$ idle. In $C(W)$ and $C(W^\dagger)$ the qubit $c$ is the control and $M$ the target.

Number the six qubits $1$ to $6$ with the target last. For four unitaries $V_1$, $V_2$, $V_3$, $V_4$ of a qubit, the Barenco circuit for five controls is the unitary of $Q^{\otimes 4} \otimes (Q \otimes Q)$ given by $$B(V_1, V_2, V_3, V_4) = R_1\bigl(1^{\otimes 3} \otimes V_4\bigr)\, T_2\bigl(1^{\otimes 2} \otimes V_3\bigr)\,T_3\bigl(1 \otimes V_2\bigr)\,T_4(V_1).$$(5)^✦ In the layer with index $k$, qubits $1$ to $k$ are the controls, qubit $k+1$ is $c$, and $M$ consists of qubits $k+2$ to $6$, on which the unitary of the layer acts on the target alone.

The Claim

The register $Q^{\otimes 4} \otimes (Q \otimes Q)$ of the circuit is the register $Q^{\otimes 5} \otimes Q$ of five controls around the target, so the circuit and the gate $C^5(V^2)$ act on the same register.

What Is Checked

The claim is stated over the gate $C^5(V^2)$ with five controls, built from the controlled gate (2) by the recursion (3), and over the circuit (5) with its layers (4).

Of these constructions the library proves that they give unitaries. The matrix (1) is unitary, and the tensor product $U \otimes W$ and the product $UV$ of two unitaries are again unitary.