Shor’s Quantum Algorithm

29 Mar 2022

Introduction

Among the many applications of the quantum computing model, the most significant in the field of cryptography is the work of the American computer scientist Peter W. Shor. Assuming the availability of a suitable quantum computer, Shor presented to the scientific community, with his 1995 paper “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, a quantum algorithm capable of breaking the RSA scheme and the Diffie–Hellman protocol, which form the foundation of modern public-key cryptography and of most secure communication systems in use today. In fact, all current public-key cryptographic standards (e.g., NIST SP 800-56 A/B, FIPS 186) would be vulnerable to this algorithm. In what follows, the discussion focuses on the RSA scheme, whose security relies on the assumption that the mathematical problem of factoring suitably chosen large integers is computationally intractable for current computers. Even when leveraging the most advanced classical computing technologies, it is estimated that factoring a 2048-bit RSA modulus—which would break the scheme—would require trillions of years. Conversely, if a quantum computer with the required memory and computational capabilities were built, the implementation of Shor’s algorithm could complete the same factorization in a matter of hours. Shor’s result is a concrete example of the exponential speed-up offered by the quantum computing model compared to its classical counterpart. The theoretical analysis of the best classical algorithm currently known [1] for factoring an $n$ -bit integer estimates a computational cost of $O\Big(e^{c\sqrt[3]{n\log^2{n}}}\Big)$ operations [2] in asymptotic terms, whereas Shor’s quantum algorithm has complexity $O(n^2\log{n}\log{\log{n}})$ . More precisely, the classical algorithm is said to have subexponential complexity in the parameter $n$ , while the quantum algorithm achieves polynomial complexity in $n$ . Similar considerations apply to the Diffie–Hellman protocol with respect to the discrete logarithm problem. The following sections present the technical details of the quantum factoring algorithm, placing it within a broader class of problems. In order to better approach the discussion, readers are encouraged to review the concepts introduced in the article on qubits. For those interested in exploring the topic further, a seminar hosted by the De Cifris association in collaboration with Telsy and the Politecnico di Torino is also recommended.

Quantum Fourier Transform

A fundamental ingredient for the construction of Shor’s algorithm is the Quantum Fourier Transform, the quantum analogue of the discrete Fourier transform. Given $x\in\{0,\dots,2^n-1\}$ , the Quantum Fourier Transform of the $n$ -qubit $|x\rangle$ is defined as

$QFT(|x\rangle)=\frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1}e^{\frac{2\pi xy}{2^n}}|y\rangle.$

This definition can be extended by linearity to all $n$ -qubits. The quantum Fourier transform can be seen as the information $x$ encoded in a superposition of all basis $n$ -qubits. In the following, it is useful to observe that given $x$ , $y\in\{0,\dots,2^{n-1}\}$ , with $\sum_{j=0}^{n-1} 2^{j}y_{j}$ binary expansion of $y$ , and $w_{l}:=e^{\frac{2\pi i}{2^l}}$ , then

$e^{\frac{2\pi i xy}{2^n}}=w_{n}^{xy}=w_{1}^{xy_{n-1}}w_{2}^{xy_{n-2}}\cdots w_{n}^{xy_{0}}.$

In these terms, the quantum Fourier transform can be rewritten by considering its action on each qubit.

$\begin{align*} QFT(|x\rangle) & = \frac{1}{\sqrt{2^{n}}}\sum_{y_{0},\dots y_{n-1}\in\{0,1\}}w_{1}^{xy_{n-1}}\cdots w_{n}^{xy_{0}}|y_{n-1}\dots y_{0}\rangle\\ & = \frac{|0\rangle+w_{1}^{x}|1\rangle}{\sqrt{2}}\frac{|0\rangle+w_{2}^{x}|1\rangle}{\sqrt{2}}\cdots\frac{|0\rangle+w_{n}^{x}|1\rangle}{\sqrt{2}} \end{align*}$

The quantum circuit to construct QFT is built starting from the previous remark and the usage of Hadamard gates $H$ and controlled Phase Shifts $R_j$ , with respect to the previous article $R_j$ denotes $R_{2^j}$ for simplicity.

Notice that at the end of the quantum circuit, the qubit order is reversed and so it has to be fixed via SWAP gates.

Quantum Phase Estimation

The problems solved by Shor’s quantum algorithm belong to a broad class known as Quantum Phase Estimation (QPE). The general formulation of QPE is as follows. Given a unitary transform $U$ and an its eigenstate $|\psi\rangle$ , find the phase $\theta\in[0,1)$ describing the corresponding eigenvalue.

$U|\psi\rangle=e^{2\pi i \theta}|\psi\rangle$

(Notice that the eigenvalue must have this form since $U$ is unitary.) Before proceeding with the analysis of the circuit that solves Quantum Phase Estimation, we introduce two key ingredients necessary to understand the subsequent discussion. 1. Consider the gate $cU$ acting as $U$ in the case the controlled bit is $1$ and as the the identity otherwise.

$\begin{align*} cU \frac{|0\rangle+|1\rangle}{\sqrt{2}}|\psi\rangle & = \frac{1}{\sqrt{2}}\Big(|0\rangle|\psi\rangle + |1\rangle U|\psi\rangle \Big)\\ & = \frac{1}{\sqrt{2}}\Big(|0\rangle|\psi\rangle+ w_{n}^{2^{n}\theta}|1\rangle|\psi\rangle\Big) \\ & = \frac{|0\rangle + w_{n}^{2^{n}\theta}|1\rangle}{\sqrt{2}} |\psi\rangle \end{align*}$

In this way, the $cU$ gate can be interpreted as a gate acting just on the first qubit since $\ket{\psi}$ is fixed. 2. Observe also that

$U^{2^{j}}|\psi\rangle = e^{2\pi i 2^j \theta}|\psi\rangle = w_{l-j}^{2^l \theta}|\psi\rangle, \qquad 0\leq j \leq l-1.$

The quantum circuit describing $U$ QPE is the following.

The $V_U$ gate in the middle maps $\sum_{x=0}^{2^n-1}|x\rangle|\psi\rangle$ to $\sum_{x=0}^{2^n-1}|x\rangle U^{x}|\psi\rangle$ . It is built starting from $2^{j}$ $U$ gates acting on the $|\psi\rangle$ register and controlled by the $j$ -th qubit for any $j$ . As an example, for $n=2$ and the fixed register $|10\rangle$

Applying $cU^{2^{j}}$ for $0\leq j \leq n-1$ and exploiting the previous remark, the entire state in $1$ is

$\frac{1}{\sqrt{2^{n}}}\underbrace{(|0\rangle+|1\rangle)}_{n \text{ volte}}|\psi\rangle\longmapsto \frac{|0\rangle+w_{1}^{2^n\theta}|1\rangle}{\sqrt{2}}\frac{|0\rangle+w_{2}^{2^n\theta}|1\rangle}{\sqrt{2}}\cdots\frac{|0\rangle+w_{n}^{2^n\theta}|1\rangle}{\sqrt{2}}|\psi\rangle.$

Substituting $2^n\theta$ with $x$ in the above expression, the Quantum Fourier Transform of $|x\rangle$ is obtained according to the previous section. Therefore, it remains to apply the inverse QFT to reobtain $2^n\theta$ . The result of the final measure is exactly

$|2^{n}\theta\rangle.$

Observe that the reasoning works well if $2^{n}\theta$ is an integer. In the general case, the quantum circuit returns just an estimate of $\theta$ that can be used to reconstruct the precise value via a continued fraction-based algorithm.

Shor’s Algorithm

Let $N$ be a positive integer and let $b$ be an integer coprime with $N$ , the objective of Shor’s algorithm is to find the period of the function

$f:\,x\mapsto b^{x}\mod N,$

through a number of steps polynomial in $\log_{2}{N}$ . In the following, the main ingredients to interpret the algorithm in the context of QPE are introduced. Let $a$ be an invertible modulo $N$ , the considered unitary transform is

$U|y\rangle = |ay \mod N\rangle$

where $U$ act on the $m$ -qubit space with

$m = \lceil \log_{2}{N} \rceil,\qquad n=2m.$

A possible set of eigenstates is given by

$|u_{s}\rangle =\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-\frac{2\pi i sk}{r}}|a^{k} \mod{N}\rangle\qquad s =0,\dots, r-1$

where $r$ is the multiplicative order of $a$ , since

$U|u_{s}\rangle=e^{\frac{2\pi is}{r}}|u_{s}\rangle.$

Clearly, if one were able to obtain $|u_{s}\rangle$ for some $s$ , this would imply knowing $r$ , but that is precisely the goal of the algorithm. To circumvent this issue, note that

$|1\rangle=\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|u_{s}\rangle.$

Therefore, proceeding with QPE of $U$ using $|1\rangle$ (superposition of $r$ eigenstates), the measured outcome will be

$\frac{2^{n}s}{r},$

with $s$ a random integer between $0$ and $r-1$ by linearity. Again, if $r$ does not divide $2^n s$ , the outcome of the measure will be just an estimate of the desired value that can be recovered via a continued fraction strategy.

Solving the factoring problem

In the RSA cryptographic scheme, the considered integer is the product of two big prime numbers, so $N=pq$ . It can be proved that with good probability the resulting period $r$ is even. In this case

$a^{r}\equiv 1\mod pq,\qquad a^{\frac{r}{2}}\not\equiv 1\mod pq.$

Moreover, with good probability

$a^{\frac{r}{2}}\not\equiv -1\mod pq.$

At this stage, since

$(a^{\frac{r}{2}}-1)(a^{\frac{r}{2}}+1)\equiv 0\mod{pq}$

the factorization of $N$ is obtained as

$\{p,q\} = \{\gcd(a^{\frac{r}{2}}-1,N), \gcd(a^{\frac{r}{2}}+1,N)\}.$

[ 1 ] General Number Field Sieve (GNFS) [ 2 ] $c$ is a positive constant

Sources:

[1] General Number Field Sieve (GNFS)

[2] $c$ is a positive constant

This article is part of a series of contributions by the Telsy Cryptography Research Group dedicated to quantum computing and its implications for cryptography. For other articles, please refer to the index of the section.

For other articles related to quantum and cryptography, please refer to the relevant categories in the blog.

The authors

Edoardo Signorini, graduated in Mathematics with a curriculum in cryptography at the University of Trento, in 2020 carried out the Master’s thesis in the field of Post-Quantum Cryptography (PQC) at Telsy. He currently holds the role of cryptographer within the Telsy research group and carries out an industrial research doctorate in Pure and Applied Mathematics at the Politecnico di Torino. His activity focuses on PQC research and on the analysis and development of cryptographic protocols.

Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at end of 2020 focusing in particular on issues related to quantum technologies.