The Exercise

Take a system with $d$ levels and computational basis $|0\rangle, \dots, |d-1\rangle$, and fix a level $y$. Adding $y$ to the label, $|x\rangle \mapsto |x + y \bmod d\rangle$, permutes the basis states cyclically. The exercise is to show that this shift is carried out by phases $e^{2\pi i yk/d}$ on the levels $k$, placed between a quantum Fourier transform and its inverse.

The Fourier transform turns a shift of the label into a phase.

The Qudit

A quantum system $S$ is a physical object 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$ with its standard inner product; for $d = 2^n$ it is a register of $n$ qubits.^✦ A pure state $|\psi\rangle$ of a quantum system $S$ is a unit vector in the state space of $S$.^✦ For a level $i$ of the qudit, the computational basis state $|i\rangle$ is the pure state whose vector is the standard basis vector of $\mathbb{C}^d$, with entry $1$ at $i$ and $0$ elsewhere.^✦

A unitary $U$ of a quantum system $S$, a closed system evolution of $S$, is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦ Applied to a pure state $|\psi\rangle$ of $S$, it gives the pure state $U|\psi\rangle$.^✦ The adjoint $U^\dagger$ of a unitary $U$ of $S$ is the unitary of $S$ given by the Hilbert space adjoint of the operator $U$.^✦ For two unitaries $U$ and $V$ of $S$, $U$ after $V$ is the unitary $UV$ of $S$, which applies first $V$ and then $U$.^✦

The Fourier Transform

The primitive $d$th root of unity is $\omega = e^{2\pi i/d}$.^✦ The quantum Fourier transform matrix in dimension $d$ is the $d \times d$ complex matrix, with rows and columns labelled $0, \dots, d-1$, whose entries are $$F_{kj} = \frac{\omega^{jk}}{\sqrt{d}}.$$(1)^✦ For $d \geq 1$, the quantum Fourier transform $F$ of the qudit with $d$ levels is the unitary whose matrix in the computational basis is (1).^✦ The inverse Fourier transform $F^{-1}$ of the qudit is the adjoint $F^\dagger$ of $F$.^✦

The Circuit

For real angles $\theta_0, \dots, \theta_{d-1}$, one for each level of the qudit, the diagonal phase gate $D$ is the unitary of the qudit that is diagonal in the computational basis, $$D = \operatorname{diag}\bigl(e^{i\theta_0}, \dots, e^{i\theta_{d-1}}\bigr).$$(2)^✦ For a level $y$, the Fourier phase layer $D_y$ is the gate (2) with angles $\theta_k = 2\pi yk/d$: $$D_y = \operatorname{diag}\bigl(1, \omega^{y}, \omega^{2y}, \dots, \omega^{(d-1)y}\bigr).$$(3)^✦ For $d \geq 1$, the Fourier addition circuit $A_y$ is the unitary of the qudit that applies the phase layer between the Fourier transform and its inverse: $$A_y = F^{-1} D_y F.$$(4)^✦

The Claim

What Is Checked

The claim (5) is stated over the circuit (4), acting on the computational basis states of the qudit as a unitary acts on pure states.

The library proves that the matrix (1) is unitary, and that the phase gate (2) is unitary because each of its entries has modulus one. The adjoint of a unitary and the composite of two unitaries are again unitaries, and a unitary preserves norms, so $A_y|x\rangle$ is a pure state of the qudit.