The Exercise

Order finding for a number $x$ coprime to $N$, with $N > 1$, uses the operator $U$ that multiplies by $x$ modulo $N$, $U|y\rangle = |xy \bmod N\rangle$. With a first register in the superposition $\sum_j |j\rangle$ and a second prepared in $|1\rangle$, applying $U^j$ to the second when the first holds $j$ leaves the two registers in $\sum_j |j\rangle U^j|1\rangle = \sum_j |j\rangle|x^j \bmod N\rangle$. The exercise asks for the same state from addition in place of multiplication: a transform $V$ that adds $x^j$ modulo $N$ to the second register when the first holds $j$, $V|j\rangle|k\rangle = |j\rangle|k + x^j \bmod N\rangle$, applied with the second register prepared in $|0\rangle$.

Multiplication and Addition Modulo $N$

The first register has dimension $m$, with basis states $|j\rangle$ for $j = 0, 1, \dots, m-1$; the second has dimension $d$, with basis states $|k\rangle$ for $k = 0, 1, \dots, d-1$. A basis state of the pair is written $|j, k\rangle = |j\rangle|k\rangle$.

For natural numbers $x$ and $N$ with $N \le d$, multiplication by $x$ modulo $N$ is the map $u$ on the labels of the second register given by $$u(y) = \begin{cases} xy \bmod N, & y < N, \\ y, & N \le y \le d-1. \end{cases}$$(1)^✦ When $x$ and $N$ are coprime, the operator $U$ of order finding is the permutation of the basis states of the second register defined by $u$, $U|y\rangle = |u(y)\rangle$.^✦

For a natural number $c$, addition of $c$ modulo $N$ is the map $s_c$ on the same labels given by $$s_c(k) = \begin{cases} (k + c) \bmod N, & k < N, \\ k, & N \le k \le d-1, \end{cases}$$(2) and the adder modulo $N$ is the permutation $A_c$ of the basis states of the second register defined by $s_c$: $$A_c|k\rangle = |s_c(k)\rangle, \qquad k = 0, 1, \dots, d-1.$$(3)

The Transform $V$ and the Two States

The permutation $\pi$ of the transform $V$ is the map on label pairs $(j, k)$ of the two registers that applies to $k$ the addition of $x^j$ modulo $N$: $$\pi(j, k) = \bigl(j, \, s_{x^j \bmod N}(k)\bigr).$$(4)^✦ The transform $V$ is the permutation matrix of $\pi$, the matrix on the two registers that moves each basis state as $\pi$ moves its labels: $$V|j, k\rangle = |\pi(j, k)\rangle = |j\rangle A_{x^j \bmod N}|k\rangle.$$(5)^✦ For $k < N$ this is $|j\rangle|(k + x^j) \bmod N\rangle$, the transform of the exercise.

The state of order finding from the powers of $U$ is the vector of the two registers $$|\psi_U\rangle = \sum_{j=0}^{m-1} |j\rangle\, U^j|1\rangle,$$(6) and the state from the transform is $V$ applied to the sum of the first register’s basis states with the second register in $|0\rangle$: $$|\psi_V\rangle = V \sum_{j=0}^{m-1} |j\rangle|0\rangle.$$(7)

The Claim

What Is Checked

The claim is stated over the states (6) and (7): the first built from the operator $U$ and its multiplication map $u$, the second from the transform $V$ and, through its permutation $\pi$, from the adders $A_c$ and their addition maps $s_c$.

About these constructions the library proves that $u$ is injective when $x$ and $N$ are coprime, $x$ being invertible modulo $N$, and that $s_c$ is injective for every $c$. An injective map of the $d$ labels to themselves is a bijection.