The Exercise

A qudit has $p$ levels $|0\rangle, \dots, |p-1\rangle$, with $p$ a prime, and the cyclic shift $U_1$ moves each level up by one, from $|p-1\rangle$ back to $|0\rangle$. For each level $\ell$, the Fourier state $F_p^{-1}|\ell\rangle$, the image of $|\ell\rangle$ under the inverse quantum Fourier transform, is an eigenstate of $U_1$ with eigenvalue $e^{2\pi i\ell/p}$. Phase estimation with $t$ control qubits reads the phase $\ell/p$ off this eigenvalue: it returns $t$ bits, and the binary number $x$ they spell gives the estimate $x/2^t$. The best estimate, the multiple of $2^{-t}$ nearest to $\ell/p$ counted modulo one, comes out with probability at least $4/\pi^2$, however many control qubits are used.^✦

Systems and States

A quantum system $S$ is described by its state space, a finite dimensional complex Hilbert space; every such space $H$ is the state space of a system, the system modelled on $H$. The composite system $S \otimes T$ of two systems has the tensor product of their state spaces as its state space.^✦ The qudit with $d$ levels is the system modelled on $\mathbb{C}^d$, whose computational basis is the orthonormal basis of standard unit vectors $|0\rangle, \dots, |d-1\rangle$. The qubit is the system modelled on $\mathbb{C}^2$, the qudit with two levels.^✦

A pure state $\psi$ of $S$ is a unit vector $|\psi\rangle$ in the state space of $S$, and each computational basis state $|i\rangle$ is a pure state of its qudit. A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$.^✦ A pure state $\psi$ gives the state $|\psi\rangle\langle\psi|$, the projector onto $|\psi\rangle$.^✦

An identification $e$ of a system $S$ with a system $T$ is a linear isometric bijection from the state space of $S$ onto that of $T$; its inverse $e^{-1}$ identifies $T$ with $S$.

Gates

A unitary $U$ of $S$, also called a gate on $S$, is an operator on the state space of $S$ with $U^\dagger U = UU^\dagger = 1$, and it carries a pure state $\psi$ of $S$ to $U|\psi\rangle$. The adjoint $U^\dagger$ of a unitary $U$ of $S$ is a unitary of $S$ as well.^✦ For unitaries $U$ of $S$ and $V$ of $T$, the product unitary $U \otimes V$ of $S \otimes T$ has the tensor product of the two operators as its operator; with $V$ the identity of $T$ it is the gate $U \otimes 1$, which acts on the first factor of the composite and leaves the second alone. The factors of a composite are its wires.

Along an identification $e$ of $S$ with $T$, a unitary $U$ of $S$ becomes the unitary $eUe^{-1}$ of $T$.^✦

Every linear isometric bijection of the state space of $S$ onto itself is a unitary of $S$.^✦ On the qudit with $r$ levels, the basis permutation gate of a permutation $\sigma$ of the levels is the unitary that carries each basis state $|x\rangle$ to $|\sigma(x)\rangle$.^✦ For a level $y$ of the qudit with $r$ levels, the shift $U_y$ is the basis permutation gate that adds $y$ modulo $r$: $$U_y|x\rangle = |x + y \bmod r\rangle .$$(1)^✦

The quantum Fourier transform $F_d$ on the qudit with $d$ levels is the unitary whose matrix in the computational basis is $$(F_d)_{kj} = \frac{\omega^{jk}}{\sqrt d}, \qquad \omega = e^{2\pi i/d},$$(2)^✦ The inverse $F_d^{-1}$ of the quantum Fourier transform $F_d$ is its adjoint, and the inverse transform of a basis state $|\ell\rangle$ is the pure state $$F_d^{-1}|\ell\rangle = \frac{1}{\sqrt d} \sum_{j=0}^{d-1} e^{-2\pi i j\ell/d}\,|j\rangle .$$(3)

The Circuit

The control register of $t$ qubits around a system $S$ is built by composing qubits on the left of $S$ one at a time: with no qubit it is $S$ itself, and with $t+1$ it is a qubit composed with the control register of $t$ qubits around $S$.^✦ Its control wires are numbered $0$ to $t-1$ from the left, and the target $S$ sits on the right. For bits $b_0, \dots, b_{t-1}$ and a pure state $u$ of $S$, the phase estimation input state is the pure state $|b_0\rangle \otimes \cdots \otimes |b_{t-1}\rangle \otimes |u\rangle$ of the register.^✦

With $H$ the Hadamard gate of the qubit, the Hadamard layer of the control register of $t$ qubits around $S$ is the gate $H^{\otimes t} \otimes 1$, which applies $H$ on every control wire and the identity on the target.^✦ For a unitary $U$ of $S$, the controlled powers of $U$ form the gate $C_U$ in which wire $k$ applies $U^{2^{t-1-k}}$ to the target when it is in $|1\rangle$.^✦

The last gate is the inverse Fourier transform on the control wires. The split of the control register of $t$ qubits around $S$ is the identification of that register with the composite of $t$ qubits and $S$, made by splitting off one qubit at a time. The control register of $t$ qubits around the trivial system is identified with the qudit with $2^t$ levels, and along this identification $F_{2^t}^{-1}$ becomes the inverse quantum Fourier transform on the $t$ qubits.

The inverse Fourier readout gate of the control register of $t$ qubits around $S$ is the gate $F_{2^t}^{-1} \otimes 1$ on the composite of $t$ qubits and $S$, carried back along the inverse of the split.^✦

The phase estimation circuit for a unitary $U$ of $S$ with $t$ control qubits is the gate on the control register of $t$ qubits around $S$ that applies the Hadamard layer, then the controlled powers of $U$, then the inverse Fourier readout gate. On the qudit with $p$ levels, with $U = U_1$, it takes the input state with every bit $0$ and $u = F_p^{-1}|\ell\rangle$ to $$|\Psi\rangle = \bigl(F_{2^t}^{-1} \otimes 1\bigr)\, C_{U_1} \bigl(H^{\otimes t} \otimes 1\bigr) \bigl(|0\rangle^{\otimes t} \otimes F_p^{-1}|\ell\rangle\bigr).$$(4)

The Measurement

A measurement on $S$ with a finite set of outcomes $I$ is a family of operators $M_i$ on the state space of $S$, one for each outcome $i$, satisfying the completeness relation $$\sum_{i \in I} M_i^\dagger M_i = 1 .$$(5)^✦ The effects $E_i = M_i^\dagger M_i$ of a measurement $M$ on $S$ make up its positive operator valued measure.^✦ The probability of the outcome $i$ on a state $\rho$ of $S$ is given by the Born rule, $$P_\rho(i) = \operatorname{Tr}(E_i\rho) = \operatorname{Tr}\bigl(M_i \rho M_i^\dagger\bigr).$$(6)^✦

A measurement on $S$ extends to $S \otimes T$ as the measurement on the first wires, with the same outcomes and the operators $M_i \otimes 1$.^✦

Along an identification $e$ of $S$ with $T$, a measurement $M$ on $S$ becomes the measurement on $T$ with the operators $eM_ie^{-1}$.^✦

The measurement of every control wire measures the register of $t$ qubits in the computational basis, one bit $b_k$ on each wire $k$, and its outcome is the string $b = b_0 b_1 \cdots b_{t-1}$.^✦ The readout of the control register of $t$ qubits around $S$ is the measurement of every control wire on the first wires of the composite of $t$ qubits and $S$, carried back along the inverse of the split.

A string $b$ is read as the integer $$x(b) = \sum_{k=0}^{t-1} b_k\, 2^{t-1-k} .$$(7)^✦

The nearest bin to a phase $\theta$ among $d$ bins is the integer nearest to $\theta d/2\pi$, reduced modulo $d$: $$\operatorname{bin}_d(\theta) = \operatorname{round}\Bigl(\frac{\theta d}{2\pi}\Bigr) \bmod d .$$(8)^✦

The Claim

What Is Checked

The claim is stated over the qudit with $p$ levels and the control register of $t$ qubits around it, the Hadamard layer, the controlled powers of $U_1$ and the inverse Fourier readout gate built on that register, the output state $|\Psi\rangle\langle\Psi|$ and the measurement of every control wire carried back to the register around the target. It also uses the cyclic shift $U_1$, the state $F_p^{-1}|\ell\rangle$, the integer $x(b)$ read from a bit string and the nearest bin $\operatorname{bin}_{2^t}$.

The library proves that the matrix (2) is unitary, so that $F_d$ is a unitary of the qudit, and that the tensor product of two unitaries and a unitary carried along an identification are unitaries again. The library also proves that the extension of a measurement to a composite and its transport along an identification are measurements again, with the completeness relation (5), and that the projector $|\psi\rangle\langle\psi|$ onto a unit vector is a state. The library also proves that the effects $E_i$ of a measurement are positive operators that sum to the identity, and that a unitary carries a pure state to a pure state, since it preserves norms.