The Exercise

The problem is to build any unitary $U$ on $n$ qubits, to within a distance $\epsilon$, from one and two qubit gates, by way of a Hamiltonian that generates it. One writes $U = e^{-iH}$ with $H$ Hermitian and its eigenvalues between $0$ and $2\pi$, and expands $H = \sum_g h_g\, g$ with real coefficients $h_g$, where $g$ runs over the $4^n$ tensor products of $n$ Pauli matrices drawn from $I$, $X$, $Y$ and $Z$.

Fix a positive integer $k$ and set $\Delta = 1/k$. Each factor $e^{-ih_g g\Delta}$ is a circuit of $O(n)$ one and two qubit gates. The product of these factors over all $g$, in a fixed order, is the Trotter product; it differs from $e^{-iH\Delta}$ by $O(\Delta^2)$, and its $k$th power differs from $U$ by $O(4^n/k)$. With $k$ large enough to bring this error below $\epsilon$, the whole circuit has $O(n\,16^n/\epsilon)$ gates.^✦

The library states each of these steps as a theorem, and the circuit for a single factor as two: one for the unitary it computes, one for its gate count.

A Register of Qubits

A quantum system $Q$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ The qudit with $d$ levels is the quantum system whose state space is $\mathbb{C}^d$ itself, with its standard inner product, and a register of $n$ qubits is the qudit with $2^n$ levels.^✦ The computational basis of a register of $n$ qubits is the standard basis of $\mathbb{C}^{2^n}$, with vectors $|x\rangle$ labelled by bit strings $x = (x_1, \dots, x_n)$; the qubits of the register are its wires $1, \dots, n$.

A unitary $U$ of $Q$ is an operator on the state space of $Q$ with $U^\dagger U = U U^\dagger = I$.^✦ An observable $H$ of $Q$ is a self adjoint operator, $H^\dagger = H$, on the state space of $Q$.^✦ The propagator of an observable $H$ from time $t_1$ to time $t_2$ is the unitary $e^{-iH(t_2 - t_1)/\hbar}$; with $\hbar = 1$, $t_1 = 0$ and $t_2 = t$ it is $e^{-iHt}$.^✦ The matrix of an observable $H$ of the qudit with $d$ levels is the matrix of $H$ in the standard basis of $\mathbb{C}^d$, with rows and columns labelled by bit strings when the qudit is a register.^✦

The Pauli matrices are the four $2 \times 2$ matrices $$\sigma_0 = I, \qquad \sigma_1 = X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad \sigma_2 = Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \qquad \sigma_3 = Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}.$$(1) A Pauli string $g$ on $n$ qubits is a tensor product $g = \sigma_{g_1} \otimes \cdots \otimes \sigma_{g_n}$ of one Pauli matrix for each wire, given by its indices $g_j \in \{0, 1, 2, 3\}$; its matrix elements between computational basis states are $\langle x | g | y \rangle = \prod_j (\sigma_{g_j})_{x_j y_j}$.^✦ The support of $g$ is the set of wires $j$ with $g_j \neq 0$.^✦ For a real number $c$, the Hamiltonian $c\,g$ is the observable of the register whose matrix is $c$ times that of $g$.^✦

The Generator and Its Pauli Expansion

A Circuit for One Pauli String

A single qubit gate $G$ on wire $j$ of a register is the unitary $G^{(j)}$ of the register that acts as $G$ on qubit $j$ and as the identity on the others: $\langle x | G^{(j)} | y \rangle = G_{x_j y_j}$ when the bit strings $x$ and $y$ agree on every wire but $j$, and $0$ otherwise.^✦ The Pauli vector is $\vec\sigma = (X, Y, Z)$; for a vector $\vec n$ in three dimensions with real components $n_1, n_2, n_3$, the matrix $\vec n \cdot \vec\sigma$ is $n_1 X + n_2 Y + n_3 Z$, and the rotation by an angle $\theta$ about an axis $\hat n$ is $R_{\hat n}(\theta) = \exp(-i\theta\, \hat n \cdot \vec\sigma / 2)$; about the $\hat z$ axis, $\hat n = (0, 0, 1)$, it is $R_z(\theta) = e^{-i\theta Z/2}$.

The basis change gates $B_0, \dots, B_3$ are made from the Hadamard gate $\mathsf{H}$ and the phase gate $S$: $$\mathsf{H} = \frac{1}{\sqrt 2} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \qquad S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}, \qquad B_0 = B_3 = I, \quad B_1 = \mathsf{H}, \quad B_2 = S\mathsf{H}.$$(4) The basis change layer of a Pauli string $g$ on $n$ qubits is $B = B_{g_1}^{(1)} B_{g_2}^{(2)} \cdots B_{g_n}^{(n)}$, the gate $B_{g_j}$ of (4) on each wire $j$.

For a set $A$ of control wires and a target wire $b$ outside $A$, the multiply controlled NOT is the permutation of bit strings that flips bit $b$ when every control bit is $1$, $$x_b \mapsto x_b \oplus \prod_{i \in A} x_i,$$(5) and leaves the other bits unchanged; here $\oplus$ is addition modulo $2$. The gate of the multiply controlled NOT with controls $A$ and target $b$ is the unitary of the register that permutes the computational basis states $|x\rangle$ in the same way.^✦ The CNOT gate $\mathrm{CNOT}_{ab}$ with control $a$ and target $b$ is the case of one control, $A = \{a\}$.^✦

For a wire $w_0$ and a list $w_1, \dots, w_r$ of other wires, the CNOT fan $F = \mathrm{CNOT}_{w_1 w_0} \cdots \mathrm{CNOT}_{w_r w_0}$ adds the bits on $w_1, \dots, w_r$ to the bit on $w_0$, modulo $2$.^✦ The circuit $V(\theta)$ for a Pauli string $g$ on the wires $w_0, w_1, \dots, w_r$, with $w_0$ the collector wire on which the rotation acts, at an angle $\theta$, is $$V(\theta) = B\, F^\dagger\, R_z^{(w_0)}(\theta)\, F\, B^\dagger.$$(6)^✦

A unitary $U$ of a register has gate budget $(N, M)$, written $U \in \mathcal{G}(N, M)$, when it is built, up to an isomorphism of registers (a unitary identification of their state spaces), as a product of pieces of two kinds, with at most $N$ gates counted in pieces of the first kind and at most $M$ in pieces of the second. A piece of the first kind is a classical block: a unitary that sends each computational basis state $|x\rangle$ to $|x'\rangle$, where $x'$ is what a sequence of NOT, CNOT and Toffoli gates (multiply controlled NOT gates with at most two controls) makes of $x$, counted as the number of gates in the sequence.^✦ A piece of the second kind is a single qubit gate, possibly beside idle qubits and possibly controlled by one further qubit, counted as one.

The Trotter Product

Let real coefficients $h_g$ be given, one for each Pauli string $g$ on $n$ qubits. The Trotter factor of $g$ at time $t$ is the circuit $W_g(t) = V(2 h_g t)$ for $g$, with the first wire of its support as collector wire and the rest of the support as the other wires; for the identity string, whose support is empty, it is the global phase gate $W_g(t) = e^{-i h_g t}\, I$.^✦ The Trotter step is the product of the factors over all Pauli strings, $$W(t) = \prod_g W_g(t).$$(9)^✦

The norm $\|A\|$ of an operator $A$ is its operator norm, the largest length of $A|\psi\rangle$ over unit vectors $|\psi\rangle$, and the gate error between unitaries $U$ and $V$ is $E(U, V) = \|U - V\|$.^✦ A fixed numerical constant $K$ appears in the error bounds of Theorems 6 and 7.

What Is Checked

The seven theorems are stated over the unitaries and observables of a quantum system and of a register of qubits, the propagator $e^{-iHt}$, the Pauli strings and their Hamiltonians $c\,g$, the circuit $V$ of (6), the Trotter step $W$ of (9) built from it, the gate error and the gate budget.

About these constructions the library proves that the propagator of an observable is a unitary, that a Pauli string is Hermitian, so that $c\,g$ is an observable, and that the adjoint $U^\dagger$ of a unitary is a unitary. It proves that the multiply controlled NOT is its own inverse, so that its gate is a unitary, and that the basis change gates, the rotations $R_z(\theta)$, a single qubit unitary placed on one wire and the global phase gate are unitaries of the register.