The Exercise

Let $N$ be a positive integer and $x$ an invertible residue modulo $N$, the residue of an integer coprime to $N$. Its order $r$ is the least positive integer with $x^r = 1$, the number that order finding computes. On a register of $N$ levels, with basis states $|0\rangle, \dots, |N-1\rangle$ labelled by the residues modulo $N$, the powers $1, x, \dots, x^{r-1}$ label $r$ basis states $|x^k \bmod N\rangle$. A discrete Fourier transform over the exponent $k$ turns them into $r$ states $|u_0\rangle, \dots, |u_{r-1}\rangle$, the eigenstates of order finding. The exercise runs the transform backwards: it asks for each basis state $|x^k \bmod N\rangle$, and for $|1\rangle$ in particular, as a superposition of the $|u_s\rangle$.

The library answers with two identities between vectors of the register’s state space.

A Quantum System

A quantum system $S$ is a physical object whose state space is 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.^✦

The system modelled on a finite dimensional complex Hilbert space $H$ is the quantum system whose state space is $H$.^✦ The qudit with $d$ levels is the system modelled on $\mathbb{C}^d$ with its standard inner product; its levels are $0, 1, \dots, d-1$, and the register of the exercise is the qudit with $N$ levels.^✦ For a level $i$ of the qudit with $d$ levels, 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.^✦

The Eigenstates of Order Finding

For a natural number $k$, the level $x^k \bmod N$ of the qudit with $N$ levels is the remainder of $x^k$ on division by $N$, a number between $0$ and $N-1$, and $|x^k \bmod N\rangle$ is the computational basis state at that level.

For $s = 0, 1, \dots, r-1$, the order finding eigenstate $|u_s\rangle$ is the pure state of the qudit with $N$ levels given by $$|u_s\rangle = \frac{1}{\sqrt r} \sum_{k=0}^{r-1} e^{-2\pi i sk/r}\, |x^k \bmod N\rangle .$$(1)^✦

The Claim

What Is Checked

The claim is stated over the eigenstates $|u_s\rangle$ of order finding, defined by the Fourier sum (1), and over the computational basis states of the qudit with $N$ levels: $|x^k \bmod N\rangle$ at the remainder of $x^k$, and $|1\rangle$.

The library also establishes that each $|u_s\rangle$ is a unit vector of $\mathbb{C}^N$, so that the sum (1) defines a pure state.