The Exercise

Period finding works with a function $f$ of period $r$ and the states $|f(x)\rangle$ of its values, the label $x$ read modulo $r$. The shift $U_y$ moves each of them along by $y$, to $|f(x+y)\rangle$. From these states one builds the Fourier states $|\hat f(\ell)\rangle$, one for each $\ell = 0, \dots, r-1$: superpositions of $|f(0)\rangle, \dots, |f(r-1)\rangle$ with equal weights and with phases that wind $\ell$ times around the unit circle as $x$ runs over a period. The exercise asks to show that each Fourier state is an eigenstate of every shift $U_y$, and to write each $|f(x_0)\rangle$ back as a superposition of Fourier states.

A Qudit and Its Basis

A quantum system $S$ is given by its state space, a finite dimensional complex Hilbert space.^✦ A pure state $|\psi\rangle$ of a system $S$ is a vector of unit norm in the state space of $S$, determined physically up to a global phase.^✦

A unitary $U$ of a system $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦ A pure state $|\psi\rangle$ of $S$ is an eigenstate of a unitary $U$ of $S$, with eigenvalue the complex number $\mu$, when $U|\psi\rangle = \mu|\psi\rangle$.^✦

The qudit with $d$ levels is the quantum system whose state space is $\mathbb{C}^d$ with its standard inner product.^✦ For a level $i$ among $0, \dots, d-1$, its computational basis state $|i\rangle$ is the pure state given by the standard unit vector with a one in position $i$ and zeros elsewhere, and the $d$ of them form the computational basis $\{|i\rangle\}$, an orthonormal basis of $\mathbb{C}^d$. The library states the exercise on the qudit with $r$ levels, the basis state $|x\rangle$ standing for $|f(x)\rangle$.

Shifts of the Basis

For a permutation $\sigma$ of the levels $0, \dots, d-1$, the basis permutation gate $P_\sigma$ of the qudit with $d$ levels is the unitary given by the linear isometry of $\mathbb{C}^d$ onto itself that permutes the computational basis by $\sigma$: $$P_\sigma |x\rangle = |\sigma(x)\rangle .$$(1)^✦

The period shift $U_y$, with $r$ a positive integer and $y$ a shift among $0, \dots, r-1$, is the basis permutation gate of the qudit with $r$ levels for the cyclic shift by $y$, $$U_y |x\rangle = |(x + y) \bmod r\rangle .$$(2)^✦

The Fourier States

On the qudit with $d$ levels, with $k$ a label among $0, \dots, d-1$, the Fourier state $F^{-1}|k\rangle$, the image of $|k\rangle$ under the inverse quantum Fourier transform, is the pure state $$F^{-1}|k\rangle = \frac{1}{\sqrt d} \sum_{j=0}^{d-1} e^{-2\pi i jk/d}\, |j\rangle .$$(3)^✦ On the qudit with $r$ levels, with $|j\rangle$ read as $|f(j)\rangle$, this is the book’s Fourier state, $|\hat f(\ell)\rangle = F^{-1}|\ell\rangle$.

The Claim

What Is Checked

The claim is stated over the qudit with $r$ levels and its computational basis, the period shift $U_y$ of (2) as a basis permutation gate, the Fourier states of (3), and the relation of eigenstate and eigenvalue between a pure state and a unitary.

Of these constructions, the library proves that each computational basis state and each Fourier state has unit norm, so that both are pure states. It proves as well that a linear isometry of a state space onto itself is a unitary operator, which makes every basis permutation gate, and with it the period shift, a unitary of the qudit.