The Exercise

A system with $d$ levels has the computational basis $|0\rangle, \dots, |d-1\rangle$. The quantum Fourier transform $F$ spreads each basis state evenly over all of them, with phases that are powers of the root of unity $e^{2\pi i/d}$. The exercise concerns the inverse transform $F^{-1}$: applied after $F$ it returns every state as it was, and on a basis state $|k\rangle$ it gives the same even superposition with every phase replaced by its complex conjugate.

A Quantum System

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ A pure state $|\psi\rangle$ of $S$ is a vector of unit norm in the state space of $S$, determined physically up to a global phase.^✦ The qudit with $d$ levels is the quantum system whose state space is $\mathbb{C}^d$ with its standard inner product, the levels labelled $0, \dots, d-1$.^✦ For a level $i$, the computational basis state $|i\rangle$ is the pure state of the qudit whose vector has entry $1$ at $i$ and $0$ elsewhere.^✦

A unitary $U$ of $S$, the evolution of $S$ as a closed system, is an operator on the state space of $S$ whose Hilbert space adjoint $U^\dagger$ satisfies $U^\dagger U = U U^\dagger = I$, with $I$ the identity operator.^✦ The adjoint $U^\dagger$ of a unitary $U$ is the unitary of $S$ whose operator is the Hilbert space adjoint of $U$.^✦ The product $UV$ of two unitaries $U$ and $V$ of $S$ is the unitary whose operator is the composite, first $V$ and then $U$; the identity unitary $I$ has the identity operator. Under a unitary $U$, a pure state $|\psi\rangle$ of $S$ goes to the pure state $U|\psi\rangle$, the vector of $|\psi\rangle$ acted on by $U$.^✦

The Fourier Transform

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

For a level $k$, the inverse Fourier image of $|k\rangle$ is the pure state of the qudit $$|\phi_k\rangle = \frac{1}{\sqrt{d}} \sum_{j=0}^{d-1} e^{-2\pi i jk/d}\, |j\rangle.$$(2)^✦

The Claim

What Is Checked

The claim is stated over the quantum Fourier transform $F$ with matrix (1), its adjoint $F^{-1}$, the product of two unitaries and the identity unitary of the qudit, and, in its second part, the image of a basis state $|k\rangle$ under $F^{-1}$ and the state $|\phi_k\rangle$ of (2).

Of these constructions the library shows that the matrix (1) is unitary. The vector (2) has unit norm, so $|\phi_k\rangle$ is a pure state.