The Exercise

Let $U$ be a unitary on one qubit. The gate $C^n(U)$ acts on $n$ control qubits and a target qubit: it applies $U$ to the target when every control is in $|1\rangle$ and acts as the identity otherwise. The exercise asks for a circuit on these $n+1$ qubits that implements $C^n(U)$ with $O(n^2)$ gates, each a single qubit gate, a controlled NOT (CNOT) or a Toffoli gate, which is a NOT with two controls.

The library answers with an explicit circuit, made from a sequence of single qubit gates, and with a count of the gates that $C^n(U)$ takes.

Qubits and Registers

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ A pure state $\psi$ of $S$ is a unit vector in the state space of $S$, $\lVert \psi \rVert = 1$.^✦ A unitary $U$ of $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 composite system $S \otimes T$ of two systems $S$ and $T$ has as its state space the tensor product of their state spaces.^✦ The qubit is the two level system with state space $\mathbb{C}^2$.^✦ The basis states $|0\rangle$ and $|1\rangle$ of a qubit are the pure states given by the standard basis vectors $e_0$ and $e_1$ of $\mathbb{C}^2$, and the single qubit gates are the unitaries of a qubit. For a system $S$, the control register of $n$ qubits around $S$ is the system of $n$ control qubits composed with $S$ one at a time, on the left: it is $S$ itself for $n = 0$, and for $n + 1$ controls it is a qubit composed with the register of $n$ qubits around $S$.^✦

Controlled Gates

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of the composite $\mathrm{qubit} \otimes S$ of a control qubit and the target $S$ given by $$C(U) = |0\rangle\langle 0| \otimes 1 + |1\rangle\langle 1| \otimes U .$$(1)^✦ For a unitary $E$ of $S$, the gate $C^n(E)$ with $n$ controls is the unitary of the control register of $n$ qubits around $S$ defined by $$C^0(E) = E, \qquad C^{n+1}(E) = C\bigl(C^n(E)\bigr).$$(2)^✦ For a single qubit gate $U$ and $n \ge 1$ the recursion also writes $C^n(U)$ as $C^{n-1}\bigl(C(U)\bigr)$, the controlled gate $C(U)$ under $n-1$ further controls.

Counting Gates

A unitary $E$ of a system $S$ has gate budget $(t, s)$ when it is built from at most $t$ NOT gates with at most two controls (the NOT gate $X$, the CNOT and the Toffoli gate) and at most $s$ single qubit gates, alone or with one control.^✦ The NOT gates come in classical blocks. A classical block on a register of $m$ qubits is a unitary that sends each basis state $|c_1\rangle \otimes \cdots \otimes |c_m\rangle$, for a string $c$ of bits, to the basis state of the string that a list of NOT gates makes of $c$, each gate of the list having at most two controls and its target outside them; the block costs as many NOT gates as the list holds. A single qubit gate $g$ counts as one single qubit gate in each of four forms: $g$ under one control, $g^\dagger$ under one control, $g$ beside a qubit on which the gate acts as the identity, and $g$ alone; in the first three forms further qubits on which the gate acts as the identity may surround it.

Budgets add under products: if $E$ has budget $(t_1, s_1)$ and $F$ has budget $(t_2, s_2)$, then $EF$, which applies $F$ and then $E$, has budget $(t_1 + t_2, s_1 + s_2)$. If $E$ is a unitary of $S$ with budget $(t, s)$ and $S$ is identified with another system $S'$ by a unitary map of state spaces, then the unitary of $S'$ that corresponds to $E$ under this identification has the same budget. A budget $(t, s)$ is also a budget $(t', s')$ whenever $t' \ge t$ and $s' \ge s$.

The Claim

For $n \ge 1$ and a sequence $V = (V_0, V_1, V_2, \dots)$ of single qubit gates in which each $V_{j+1}$ is a square root of $V_j$, the Barenco circuit $B_n(V)$ is a unitary of $n$ control qubits and a target qubit, defined by recursion on $n$ from $V_1, \dots, V_n$: $B_1(V)$ is the circuit of single qubit gates and CNOT gates built from $V_1$ that acts on one control and the target, and $B_{n+1}(V)$ applies a fixed block of CNOT, Toffoli and single qubit gates built from $V_1$ and then the circuit $B_n$ built from $V_2, \dots, V_{n+1}$.^✦

What Is Checked

The claims are stated over the gate $C^n(U)$ of (2), built from the controlled gate (1) of a single qubit gate, over the Barenco circuit and over the gate budget. About these constructions the library proves that the controlled gate of a unitary $U$ of any system is unitary, $C(U)^\dagger C(U) = C(U)\, C(U)^\dagger = 1$.^✦