The Exercise

A register has $d$ basis states $|0\rangle, |1\rangle, \dots, |d-1\rangle$, labelled by the numbers $0$ to $d-1$. Fix natural numbers $x$ and $N$ with $N \le d$ and $x$ coprime to $N$. Multiplication by $x$ modulo $N$ shuffles the labels $0, \dots, N-1$ among themselves, and the labels from $N$ to $d-1$ stay where they are. The operator $U$ of order finding is the matrix of this shuffle, and the exercise is to show that $U$ is unitary.

The Multiplication Map

For natural numbers $x$ and $N \le d$, the multiplication map $f_x$ is the map of the labels $\{0, 1, \dots, d-1\}$ to themselves that multiplies a label below $N$ by $x$ modulo $N$ and fixes every other label: $$f_x(y) = \begin{cases} xy \bmod N, & 0 \le y < N, \\ y, & N \le y \le d-1. \end{cases}$$(1)^✦

For $x$ coprime to $N$, the permutation $\pi_x$ of the labels $\{0, \dots, d-1\}$ is $f_x$ taken as a bijection, with each label written above its image: $$\pi_x = \begin{pmatrix} 0 & 1 & \cdots & N-1 & N & \cdots & d-1 \\ 0 & x \bmod N & \cdots & (N-1)x \bmod N & N & \cdots & d-1 \end{pmatrix}.$$(2)^✦

The Operator

For $x$ coprime to $N$ and $N \le d$, the operator $U$ of order finding is the permutation matrix of $\pi_x$, the $d \times d$ complex matrix with entries $$U_{yz} = \begin{cases} 1, & z = \pi_x(y), \\ 0, & \text{otherwise}, \end{cases} \qquad y, z = 0, 1, \dots, d-1.$$(3)^✦

The Claim

What Is Checked

The claim is stated over the operator $U$ of (3), the permutation matrix of $\pi_x$, which is built from the multiplication map $f_x$ of (1). About these constructions the library proves that $f_x$ is one to one whenever $x$ is coprime to $N$, the fact that makes $\pi_x$ in (2) a permutation of the $d$ labels.