The Exercise

The quantum Fourier transform $U$ on $n$ qubits has a circuit of Hadamard gates and controlled phase gates $R_k = \mathrm{diag}(1, e^{2\pi i/2^k})$, with $k$ up to $n$, so the phases it calls for shrink to $2\pi/2^n$. Suppose each controlled $R_k$ is carried out with its phase off by $\Delta = 1/p(n)$, and let $V$ be the circuit that results. The exercise is to show that the gate error $E(U,V)$ between the two unitaries scales as $\Theta(n^2/p(n))$.

The library builds $V$ gate by gate and bounds $E(U,V)$ from above and from below.

A Quantum System

A quantum system $S$ is given by its state space, a finite dimensional complex Hilbert space, and every such space $H$ is the state space of a system. The qudit with $d$ levels is the system whose state space is $\mathbb{C}^d$ with its standard inner product and computational basis $|0\rangle, \dots, |d-1\rangle$.^✦ The qudit with $d = 2^n$ levels is a register of $n$ qubits, its basis states labelled by strings $x = (x_0, \dots, x_{n-1})$ of $n$ bits, $x_j$ being the bit on wire $j$.

A unitary $W$ of a system $S$ is an operator on the state space of $S$ with $W^\dagger W = W W^\dagger = 1$.^✦ The gate of a unitary $d \times d$ matrix $M$ is the unitary of the qudit with $d$ levels that acts on state vectors as $M$ does in the computational basis.^✦

The gate error between two unitaries $U$ and $V$ of $S$ is the operator norm of their difference, $$E(U,V) = \|U - V\| = \max_{\| |\psi\rangle \| = 1} \|(U - V)|\psi\rangle\|.$$(1)^✦

The Fourier Transform

The Fourier matrix $F$ in dimension $d$ is the complex $d \times d$ matrix, rows and columns labelled $0, \dots, d-1$, built on the primitive $d$th root of unity $\omega$: $$F_{kj} = \frac{\omega^{jk}}{\sqrt{d}}, \qquad \omega = e^{2\pi i/d}.$$(2) For $d \neq 0$ the quantum Fourier transform on the qudit with $d$ levels is the unitary whose matrix in the computational basis is $F$.^✦ On the register of $n$ qubits, where $d = 2^n$, it is the transform $U$ of the exercise.

The Circuit

Each gate of the circuit acts on one wire of the register. The single qubit gate of a complex $2 \times 2$ matrix $g$ on wire $j$ applies $g$ to bit $j$ and leaves the other bits alone.^✦ More generally, when a $2 \times 2$ block $f(y)$ is assigned to each pattern $y$ of the other bits, the gate on wire $j$ block by block applies $f(y)$ to that wire whenever the other bits read $y$, and leaves them unchanged.^✦ For a complex $2 \times 2$ matrix $\tilde U$ and a set $K$ of control wires, the multiply controlled gate $C^K(\tilde U)$ on target wire $j$ is the case $f(y) = \tilde U$ when every wire of $K$ carries a $1$ in $y$, and $f(y) = 1$ otherwise.^✦

A permutation $\sigma$ of the bit strings defines a permutation gate, the matrix sending $|x\rangle$ to $|\sigma(x)\rangle$.^✦ The bit reversal $\sigma(x)_j = x_{n-1-j}$ reverses the order of the wires, and its gate is written $P$.^✦

Two single qubit matrices enter: the Hadamard gate, and for each $k$ the phase gate $R_k'$, which shifts the phase $2\pi/2^k$ of $R_k$ by $\Delta$: $$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \qquad R_k' = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i/2^k + i\Delta} \end{pmatrix}.$$(3)

Let $H_t$ be the Hadamard gate on wire $t$, and $C_{t,c} = C^{\{c\}}(R_{c-t+1}')$ the controlled phase gate with control wire $c$ and target wire $t$. The circuit with phase error $\Delta$ reverses the wires and then runs the block $B_t$ of each wire $t$ in turn, a Hadamard followed by the controlled gates from the later wires $c = t+1, \dots, n-1$; with the rightmost factor acting first, its matrix is $$V = B_{n-1} \cdots B_1 B_0 \, P, \qquad B_t = C_{t,n-1} \cdots C_{t,t+1} \, H_t .$$(4) The approximate Fourier transform $V$ with phase error $\Delta$ on the register of $n$ qubits is the gate of the matrix (4) on that register.

The number of controlled gates is $$N(n) = \frac{n(n-1)}{2}.$$(5)^✦

The Claim

What Is Checked

The claim is stated over the register of $n$ qubits, the quantum Fourier transform $U$ with the matrix (2), the approximate transform $V$ given by the circuit (4) at $\Delta = 1/p(n)$, their gate error (1), and the count (5) of controlled gates.

About these constructions the library proves that the matrix (4) of the circuit is unitary for every number of qubits and every phase error $\Delta$.^✦