Shor: Modular exponentiation vs modular multiplication

Question

In his original article Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter Shor constructed an algorithm for finding a period $r$ of the modular exponentiation $a^x \mod N$, where $N$ is factored number, $a$ is random integer such that $1 < a < N$ and $\gcd\{a,N\} = 1$. This period $r$ is then used in factoring of integer $N = pq$ via the greatest common divisor: $p,q = \gcd\{a^{r/2} \pm 1, N\}$. The period $r$ is found with quantum phase estimation. This is a short description of Shor's factorization algorithm.

In the article Circuit for Shor’s algorithm using 2n+3 qubits, Stéphane Beauregard provides an implementation of Shor's algorithm which is almost the same as the one described above with the exception that rather than a period of the modular exponentiation, a period of the function $(ax) \mod N$ (modular multiplication) is searched for. This is firstly discussed on pg. 2 in fig. 1, and then several other times in the article.

However, I failed to see how finding period of the modular exponentiation and the modular multiplication are equivalent problems. Could anyone shed more light on this?

Answer 1

I think it's just an issue of terminology.

Given integers $a$ and $N$, you're looking for the order $r$ of $a$ mod $N$, that is, the smallest $r$ such that $a^r\equiv1\bmod N$. In this context, people use "period" and "order" interchangeably.

To find such $r$ via QPE, you want to look for a unitary $U$ which somehow encodes it in its eigenvalues — as QPE returns an approximation of an eigenvalue of $U$, when the input at the second register is the corresponding eigenstate. As it happens, if you use the unitary $U_{a,N}$ defined as $U_{a,N}|x\rangle=|ax\bmod N\rangle$, this will satisfy $U_{a,N}^r=I$, and thus its eigenvalues will be $\exp(2\pi i k/r)$ for $k=0,...,r-1$.

So I would say it's the "period" of the function $f:k\mapsto a^k\bmod N$, as the smallest $r$ such that $f(r)=f(0)=1$, and you retrieve it doing QPE on the unitary implementing the multiplication $x\mapsto ax\bmod N$.

Answer 2

Shor's algorithm finds the period of a modular multiplication by performing a modular exponentiation with a superposed exponent. The different authors are just emphasizing different parts of the algorithm; they're describing the same thing.

Answer 3

In Shor's algorithm one applies the Quantum Phase Estimation (QPE) algorithm to the unitary operator $U$ which implements modular multiplication (i.e. $U|x\rangle =|xa \hspace{-6pt}\mod \hspace{-4pt} N\rangle$) in order to find the period $r$ of $a$ modulo $N$ (namely, the smallest $r$ such that $a^r = 1\hspace{-4pt}\mod N$). In the QPE algorithm controlled $U^{2^i}$ are applied in sequence (for $i = 0,...,t-1$ where $t$ is the size of control register which is the register that is measured at the end of the algorithm) so that the result of this part of the algorithm is exponentiation modulo $N$ (i.e. $a^{y}\hspace{-6pt} \mod N$ where $y$ is the input of the control register - the QPE starts with a Hadamard transform on this register so that this register carries all possible input states).

The input to the QPE in Shor's algorithm is the state $|x=1\rangle$ which is an equal superposition of all $r$ eigenstates of $U$ with eigenvalues $\exp (2\pi i s/r)$, $s = 0, ... ,r-1$. The measured output of the QPE would therefore be a binary fraction which is a good approximation to $s/r$ for some $s < r$.

Note that in Shor's algorithm $U^{2^i}$ is implemented by multiplying by the corresponding power of $a$. In Beauregard's implementation QFT-based adders are used to implement modular addition and multiplication, and $a^{2^i}$ are encoded in the phases of these QFT-based adders. An implementation similar to Beauregard's version of Shor can be found in Classiq's library (Disclaimer - I am a Classiq employee) (the only difference is that this implementation does not use the single-qubit realization of the QFT hence it requires $4n+2$ qubits)