Quantum Computers’ Role in Shor’s Algorithm

Today widely used asymmetric cryptographic schemes are based on ideas that appear in two fundamental and very important papers from the 1970s, namely Diffie-Hellman [DH76] and RSA [RSA78]. The (difficult to solve) mathematical problems on which these schemes are based are:

• the computation of discrete logarithm;
• the factorization of large numbers.

The difficulty in solving the above problems is that the known ways to do that are computationally infeasible; namely, their cost, as measured by either the amount of memory used or the runtime, is finite but impossibly large.

In 1994, Peter Shor published a paper [Sho94] in which he explained how to solve both problems in a computationally feasible way by using a quantum computer. Thus, with just one blow, Shor showed how to break the asymmetric cryptography schemes developed in the 1970s and also their elliptic curve analogs developed in the 1980s.

The common thing shared by the above math problems is that you can solve them if you can efficiently compute the period $p$ of periodic functions, i.e., $f(x+p)=f(x)$ for all $x$.

Then, the role of the quantum computer in Shor’s algorithm is to compute the period of periodic functions. More precisely, you are going to pass a periodic function $f(x)$ as input to a quantum computer, and you are going to get as output the period $p$ of $f(x)$.

The mathematical link between factorization and periods was already understood by Gauss and developed in his famous “Disquisitiones Arithmeticae”. Here are the main observations:

• (a) fast computation of periods of periodic functions implies fast computation of non-trivial square roots of 1 modulo $n$;
• (b) fast computation of non-trivial square roots of 1 implies fast computation of non-trivial divisors of $n$.

To understand claim (b), recall that a non-trivial square root of 1 modulo $n$ is a natural number $x$, $1<x<n-1$, such that

$$x^2=1(\mathrm{mod}n).$$

Take for example $n=15$. Then $4$ and $11$ are non-trivial square roots of 1.

So assume you have such an $x$. Then, moving $1$ to the left-hand side of the equation, you have

$$x^2-1=(x-1)(x+1)=0(\mathrm{mod}n).$$

So by computing $\gcd (x-1,n)$ and $\gcd (x+1,n)$, you get a non-trivial divisor of $n$. Computing $\gcd$ is known to be computationally feasible since Euclid’s times. Notice that for $n=15$ the two non trivial square roots $4,11$ gave the divisors $\gcd (4+1,15)=5$ and $\gcd (4-1,15)=3$.

Now, to understand claim (a), pick some natural number $a$ and consider the function $f:\mathbb{Z}\to \{0,1,\dots ,n-1\}$ defined as:

$$f(z):=a^z(\mathrm{mod}n)$$

where $a^z(\mathrm{mod}n)$ is the remainder of the division of $a^z$ by $n$. It is quite easy to see that for most choices of $a$, the function $f$ is a periodic function. So if you have a fast way to compute the period $p$ of $f$, then you have

$$a^p=1(\mathrm{mod}n).$$

Now if $p=2k$ is even, then $x=a^k$ is a non-trivial square root of $1$, and you can use it to factorize $n$ as explained above. If the period $p$ is odd, then you try with another $a$, i.e., you change the periodic function and it is not an issue since there are almost the same number of odd and even periods.

To give an example, consider $a=7$ and $n=15$. Then the period of $f(z)=7^z(\mathrm{mod}15)$ is $p=4$. You can check that $7^4=1(\mathrm{mod}15)$. Then $7^2=4(\mathrm{mod}15)$ is a non trivial square root of 1 modulo 15.

To get some insight into what is going on inside a quantum computer, we need to recall some facts about Fourier analysis.

It is well known that periodic functions are strongly related to Fourier analysis. But in almost all lectures on Fourier analysis, the period of the functions is well-known and fixed, usually to $2\pi$, which is the length of the unit circle. Actually, the functions $f$ you are going to learn how to compute their Fourier transforms $\widehat{f}$ or Fourier coefficients are functions from the unit circle to complex numbers. So it is not so clear or obvious how to use Fourier analysis to compute periods of periodic functions. Things are more clear if you know the abstract theory called commutative harmonic analysis. In such a setting, it is straightforward to notice that the support of the Fourier transform $\widehat{f}$ consists of multiples of the period $p$. The setting of commutative harmonic analysis involves a commutative group $G$, an invariant measure $\mu$, the dual group $Ĝ$ of characters $\chi$’s, and the Fourier transform given by the integral:

$$\widehat{f}(\chi ):={\int \; <!--\; nolimits\; -->}_{G}f\cdot \chi d\mu .$$

So $\widehat{f}$ has as domain the dual group of characters, and basic facts of harmonic analysis imply that the support of $\widehat{f}$ are multiples of the periods of $f$.

To understand the above in the case of the periodic function $f(z)=a^z$, the above integral becomes a sum, but I still use the integral symbol:

$$\widehat{f}(z)={\int \; <!--\; nolimits\; -->}_{\mathbb{Z}}f(x)\cdot e^{x\cdot z}\mathit{dx}$$

and if $p$ is the period of $f$, a straightforward computation yields to

$$(e^{z\cdot p}-1){\int \; <!--\; nolimits\; -->}_{\mathbb{Z}}f(x)\cdot e^{x\cdot z}\mathit{dx}=0.$$

Hence the support of $\widehat{f}$ consists of those characters corresponding to complex numbers $z=\frac{i2\pi }{p}s$ for an integer $s\in \mathbb{Z}$.

Summing up, if you have an efficient black box to compute the support of the Fourier coefficients of a periodic function, then you can compute its period $p$.

In his paper, Shor explained how to use a quantum computer to compute the Fourier transform, hence the period. Such a quantum computer consists of a register and the operators that change the state of the register.

The register is made up of a certain number of so-called qubits, which are the quantum analog of flip-flops. The mathematical model of one qubit is the 2-dimensional complex vector space $V$ generated by two perpendicular unit vectors $e_0$ and $e_1$. The states of the qubit are the vectors of length one. A register of $n$ qubits is modeled as the tensor product $V^n=V\otimes \cdots \otimes V$. Notice that the dimension is $2^n$. The states of the register are the unit vectors of $V^n$. The operators that can be used to change the state of the register are the unitary transformations of $V^n$, namely, complex linear maps of $V^n$ that preserve the length of the vectors. At some point, to get the solution to your problem, you should read (or better yet, measure) the register. The output of such a measurement is going to be one of the $2^n$ unit vectors forming the basis of tensor products. These $2^n$ unit vectors can be regarded as the classical possible $2^n$ states of a register with $n$ flip-flops.

To illustrate the situation, imagine a register with 2 qubits. The state of such a register is a linear combination of the $2^2=4$ tensor products:

$$e_0\otimes e_0,e_0\otimes e_1,e_1\otimes e_0,e_1\otimes e_1.$$

Assume that before the measurement, the state of the register is the linear combination:

$$a{e}_0\otimes e_0+b{e}_0\otimes e_1+c{e}_1\otimes e_0+d{e}_1\otimes e_1$$

where $a$, $b$, $c$, and $d$ are complex numbers such that $|a{|}^2+|b{|}^2+|c{|}^2+|d{|}^2=1$. If you measure the register, you can obtain $e_0\otimes e_0$ with probability $|a{|}^2$, $e_0\otimes e_1$ with probability $|b{|}^2$, and so on. Namely, the coefficients of the linear combination give you, in advance, the probabilities of the result of the measurement. Finally, after the measurement, the state of the register becomes the output of the measurement. For example, if you measure $e_1\otimes e_0$, then the state of the register becomes $e_1\otimes e_0$. Somehow after the measurement, the register loses information and is updated, by the laws of quantum physics, to the result of the measurement. So it is important to keep in mind that you are not going to read the register until you are sure, with high probability, that you are going to extract the result you need from the output of the
measurement.

You can think of a quantum program as a sequence of unitary operators that take the register from an initial state to a final state ending with a measurement. The interesting thing is that you can put the register in a state in which all $2^n$ outputs are equiprobable. Then you can apply an operator (or a sequence of operators) to such an equiprobable state instead of applying it to just one state, as happens in a classical register of flip-flops. This gives a kind of parallelism. For example, take $n$ as a huge composite number. To compute the Fourier transform of $f(x)=a^x(\mathrm{mod}n)$ you need to compute all powers $a^x(\mathrm{mod}n)$ for too many values of $x$, which is a computationally infeasible task. The fast square-multiply algorithm can be used to compute a power $a^x$ for a given $x$, even if $x$ is huge. In his paper, Shor explains how the square-multiply algorithm can be quantized (i.e., adapted to a quantum computer) and hence applied to the equiprobable state. So you can think that the quantum computer has managed somehow to compute all the powers at once. Remember that you cannot read the register, so you can try to quantize algorithms that are somehow uniform, i.e., the flow of instructions does not depend on reading the data. Here are two examples.
First example: You have two bases of a finite-dimensional vector space. To perform a change of coordinates between them, you use a matrix $M$. Namely, you take the coordinates $x$ of some vector, multiply $\mathit{Mx}=y$, and $y$ are the new coordinates. Notice that the matrix $M$ does not depend on the values of $x$! So the algorithm to change coordinates is uniform.
Second example: You have a matrix $A$, and you want to compute the Echelon reduced form $E$. You apply elementary row reductions, but from the very beginning, to know which reduction you should apply, you need to read data from $A$. Thus the algorithm to reduce a matrix $A$ is not uniform.

The above perhaps gives you some intuition of why the Fourier transform can be expected to be quantized: just recall that Fourier transform is a change of basis of a vector space. Indeed, the function $f(x)$ is a vector of some vector space, and the Fourier coefficients are its coordinates w.r.t. the basis of exponential functions. Thus the Fourier transform is indeed a change of coordinates.

So roughly speaking, Shor’s algorithm implements the Fourier transform of $f(x)=a^x(\mathrm{mod}n)$ in the setting of the quantum computer and then reads the register to obtain the support of its Fourier transform $\widehat{f}$, hence it computes the period $p$ of $f(x)$. Actually, when you read the register to extract the period from the measurement, it is necessary to use a classical computer to get the period $p$.

Summing up, you can regard the quantum computer as an accelerator that performs a specific computation very efficiently (e.g., periods of periodic functions). You can also regard the quantum computer on top of a classical computer as explained in Richard Borcherds’ [Bor21] YouTube post “The teapot test for quantum computers”.

References