The Exercise

The quantum algorithm for the discrete logarithm works modulo a positive integer $N$. It is given a unit $a$ of the integers modulo $N$, of order $r$, the least positive integer with $a^r = 1 \bmod N$, together with a power $b = a^s \bmod N$, and the unknown is the exponent $s$. The algorithm evaluates the function of two exponents $$f(x_1, x_2) = a^{s x_1 + x_2} \bmod N = b^{x_1} a^{x_2} \bmod N$$(1) and writes its values on a register of dimension $N$.

The Fourier transform over both exponents takes the states $|f(x_1, x_2)\rangle$ of that register to states $|\hat f(\ell_1, \ell_2)\rangle$, labelled by integers $\ell_1$ and $\ell_2$ from $0$ to $r - 1$. The exercise runs the transform backwards: it sums the states $|\hat f(\ell_1, \ell_2)\rangle$ over both labels with the phases $e^{\pm 2\pi i (\ell_1 x_1 + \ell_2 x_2)/r}$ and asks which state of the register comes out. The library gives the answer for both signs of the exponent.

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 unit vector in the state space of $S$, determined physically up to a global phase.^✦ The qudit with $d$ levels is the quantum system whose state space is $\mathbb{C}^d$ itself, with its standard inner product, and for a level $i$ less than $d$ the computational basis state $|i\rangle$ of the qudit is the pure state whose vector has entry $1$ at $i$ and $0$ elsewhere.

The register of the exercise is the qudit with $N$ levels. Its basis states are labelled by residues: for a natural number $k$, $a^k \bmod N$ is the natural number less than $N$ that represents the power $a^k$, and $|a^k \bmod N\rangle$ is the basis state it labels.

The Fourier States

The value state $|f(x_1, x_2)\rangle$ for natural numbers $x_1$ and $x_2$ is the basis state $|a^{s x_1 + x_2} \bmod N\rangle$ of the qudit with $N$ levels.^✦

For a label $\ell$ less than $r$, the eigenstate $|u_\ell\rangle$ used in order finding, the algorithm that determines the order $r$, is the pure state of the same qudit with $N$ levels $$|u_\ell\rangle = \frac{1}{\sqrt r} \sum_{k=0}^{r-1} e^{-2\pi i \ell k/r}\, |a^k \bmod N\rangle .$$(2)^✦

The Fourier state $|\hat f(\ell_1, \ell_2)\rangle$, for labels $\ell_1$ and $\ell_2$ less than $r$, is the vector of the state space of the qudit $$|\hat f(\ell_1, \ell_2)\rangle = \begin{cases} |u_{\ell_2}\rangle & \text{if } \ell_1 = s \ell_2 \bmod r, \\ 0 & \text{otherwise.} \end{cases}$$(3)^✦

For natural numbers $x_1$ and $x_2$, the inverse Fourier sum $|\Phi_+(x_1, x_2)\rangle$ is the vector of the state space of the qudit with $N$ levels obtained by summing the Fourier states over both labels with phases: $$|\Phi_+(x_1, x_2)\rangle = \frac{1}{r} \sum_{\ell_1=0}^{r-1} \sum_{\ell_2=0}^{r-1} e^{2\pi i (\ell_1 x_1 + \ell_2 x_2)/r}\, |\hat f(\ell_1, \ell_2)\rangle$$(4)^✦

For natural numbers $x_1$ and $x_2$, the forward Fourier sum $|\Phi_-(x_1, x_2)\rangle$ is the vector of the state space of the qudit with $N$ levels obtained by summing the Fourier states over both labels with the phases of the previous sum taken with the opposite sign: $$|\Phi_-(x_1, x_2)\rangle = \frac{1}{r} \sum_{\ell_1=0}^{r-1} \sum_{\ell_2=0}^{r-1} e^{-2\pi i (\ell_1 x_1 + \ell_2 x_2)/r}\, |\hat f(\ell_1, \ell_2)\rangle .$$(5)^✦

The Claim

What Is Checked

The claim is stated over the eigenstates $|u_\ell\rangle$ of order finding, which enter both sums through the Fourier states (3), and over the basis states $|a^k \bmod N\rangle$ of the qudit with $N$ levels in which both sides are written.

About these constructions the library proves that each $|u_\ell\rangle$ is a pure state of the qudit.