The Exercise

In the discrete logarithm problem one is given a unit $a$ of the integers modulo $N$ and a power $a^s$, and asked for the exponent $s$. Let $r$ be the order of $a$, the least positive integer with $a^r \equiv 1 \pmod{N}$. The quantum algorithm evaluates the function $f(x_1,x_2) = a^{s x_1 + x_2} \bmod N$ on all pairs of exponents below $r$ and then Fourier transforms both exponents modulo $r$. The exercise is to compute the transform of $f$ at a pair of labels $(\ell_1,\ell_2)$ and to find the pairs at which it does not vanish. The library gives the answer in terms of the eigenstates used in the order finding algorithm, which finds the order $r$ of $a$.

The Register

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

The register of the algorithm is the qudit with $N$ levels. For a unit $a$ modulo $N$ and a natural number $k$, the residue $a^k \bmod N$ is the integer below $N$ that represents the power $a^k$; it labels the basis state $|a^k \bmod N\rangle$ of the register.^✦ For a natural number $s$ and natural numbers $x_1$ and $x_2$, the function value state $|f(x_1,x_2)\rangle$ is the basis state $|a^{s x_1 + x_2} \bmod N\rangle$.^✦

The Fourier Sums

For natural numbers $\ell_1$ and $\ell_2$, the double Fourier sum of $f$ is the vector $$|\Phi(\ell_1,\ell_2)\rangle = \sum_{x_1=0}^{r-1}\sum_{x_2=0}^{r-1} e^{-2\pi i(\ell_1 x_1 + \ell_2 x_2)/r}\,|f(x_1,x_2)\rangle$$(1) in the state space of the register, and for a natural number $\ell$ the single Fourier sum $|\varphi(\ell)\rangle$ is the vector $$|\varphi(\ell)\rangle = \sum_{j=0}^{r-1} e^{-2\pi i \ell j/r}\,|a^j \bmod N\rangle.$$(2) For a label $\ell < r$, the order finding eigenstate $|u_\ell\rangle$ is the pure state of the register $$|u_\ell\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1} e^{-2\pi i \ell k/r}\, |a^k \bmod N\rangle.$$(3)^✦ For labels $\ell_1, \ell_2 < r$, the Fourier state of $f$ is the vector $$|\hat f(\ell_1,\ell_2)\rangle = \begin{cases} |u_{\ell_2}\rangle & \text{if } \ell_1 \equiv s\ell_2 \pmod{r},\\ 0 & \text{otherwise.} \end{cases}$$(4)^✦

The Claim

What Is Checked

The identities (5) and (6) are stated over the double sum (1) of the function value states and the single sum (2); the identity (7) relates the double sum to the Fourier state (4), built from the order finding eigenstates (3).

About these constructions the library proves that every computational basis state $|i\rangle$ is a unit vector, so each $|f(x_1,x_2)\rangle$ is a pure state, and that each eigenstate $|u_\ell\rangle$ is a pure state as well: the basis states $|a^k \bmod N\rangle$ with $k < r$ are orthonormal, and the $r$ coefficients of $|u_\ell\rangle$ each have squared modulus $1/r$.