Shor's algorithm

For example: Given ${\displaystyle N=15}$, ${\displaystyle a=7}$, and ${\displaystyle r=4}$, i.e.,${\displaystyle {\bmod {(}}1,15)={\bmod {(}}7^{4},15)={\bmod {(}}7^{8},15),}$ we have ${\displaystyle \gcd(7^{2}\pm 1,15)=\gcd(49\pm 1,15)}$, where ${\displaystyle \gcd(48,15)=3}$ and ${\displaystyle \gcd(50,15)=5}$. For ${\displaystyle N}$ that is a product of two distinct primes, ${\displaystyle p}$ and ${\displaystyle q}$, ${\displaystyle \varphi (N)=(p-1)(q-1)}$, which for ${\displaystyle N=15}$ is ${\displaystyle 8}$, and ${\displaystyle r}$ divides ${\displaystyle 8}$.

Quantum subroutine in Shor's algorithm

The quantum circuits used for this algorithm are custom designed for each choice of ${\displaystyle N}$ and each choice of the random ${\displaystyle a}$ used in ${\displaystyle f(x)=a^{x}{\bmod {N}}}$. Given ${\displaystyle N}$, find ${\displaystyle Q=2^{q}}$ such that ${\displaystyle N^{2}\leq Q<2N^{2}}$, which implies that ${\displaystyle {\dfrac {Q}{r}}>N}$. The input and output qubit registers need to hold superpositions of values from ${\displaystyle 0}$ to ${\displaystyle Q-1}$, and so have ${\displaystyle q}$ qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least ${\displaystyle N}$ different values of ${\displaystyle x}$ that produce the same ${\displaystyle f(x)}$, even as the period ${\displaystyle r}$ approaches ${\displaystyle {\dfrac {N}{2}}}$.

Proceed as follows:

Shor's algorithm hinges on finding a non-trivial square root of ${\displaystyle 1}$ modulo ${\displaystyle N}$; That is, a solution to

${\displaystyle b^{2}\equiv 1{\bmod {N}}}$

where ${\displaystyle b\not \equiv \pm 1{\bmod {N}}}$.

If such ${\displaystyle b}$ exists, we claim that ${\displaystyle d=\gcd(b-1,N)}$ is a proper factor of ${\displaystyle N}$, i.e., ${\displaystyle d\neq 1,N}$. In fact, if

${\displaystyle d=N}$, then ${\displaystyle N}$ divides ${\displaystyle b-1}$, so that ${\displaystyle b\equiv 1{\bmod {N}}}$, which goes against the construction of ${\displaystyle b}$. If, on the other hand, ${\displaystyle d=\gcd(b-1,N)=1}$, then by Bézout's identity, there are integers ${\displaystyle u,v}$ such that

${\displaystyle (b-1)u+Nv=1.}$

Multiplying both sides by ${\displaystyle b+1}$, we obtain

${\displaystyle (b^{2}-1)u+N(b+1)v=b+1.}$

As ${\displaystyle N}$ divides ${\displaystyle b^{2}-1}$, we find that ${\displaystyle N}$ divides ${\displaystyle b+1}$, so that ${\displaystyle b\equiv -1{\bmod {N}}}$, again contradicting the construction of ${\displaystyle b}$.

Therefore, ${\displaystyle d}$ is the required proper factor of ${\displaystyle N}$. Similarly, it can be proven that ${\displaystyle \gcd(b+1,N)}$ is also a proper factor of ${\displaystyle N}$.

For such a non-trivial square root of ${\displaystyle 1}$ modulo ${\displaystyle N}$ to exist, notice that ${\displaystyle -1\equiv 1{\bmod {2}}}$, and for any power of an odd prime ${\displaystyle N=p^{n}}$, there is no non-trivial square root of ${\displaystyle 1}$ modulo ${\displaystyle N}$: For any ${\displaystyle (b+1)(b-1)=mp^{n},}$ either ${\displaystyle b-1}$ or ${\displaystyle b+1}$ has to be a multiple of ${\displaystyle N=p^{n}}$.

Therefore, for Shor's algorithm to work, we need ${\displaystyle N}$ to be odd (otherwise ${\displaystyle 2}$ is a divisor) and not to be any power of an odd prime (otherwise that prime is a divisor). We can check that there are no integer roots ${\displaystyle {\sqrt[{k}]{N}}}$ for ${\displaystyle 2\leq k\leq {\log _{3}}(N)}$, and if ${\displaystyle N}$ is not a power of any integer, it is not a power of any odd prime. Here, the upper bound for the integer ${\displaystyle k}$ that we need to check is determined by ${\displaystyle {\sqrt[{k}]{N}}\geq 3}$, since for ${\displaystyle N}$ to be odd, ${\displaystyle {\sqrt[{k}]{N}}}$ cannot be ${\displaystyle 2}$. This check, however, cannot rule out that ${\displaystyle N}$ may be an odd prime itself, which can only be ruled out by primality-testing algorithms.

Given that ${\displaystyle N}$ is odd and not any power of an odd prime, based on the fundamental theorem of arithmetic, we may assume that ${\displaystyle N}$ is the product of two coprime integers greater than ${\displaystyle 2}$ (${\displaystyle N=n_{1}n_{2}}$ and ${\displaystyle n_{1},n_{2}>2,\,\gcd(n_{1},n_{2})=1}$). From the four combinations of choosing plus sign and minus sign in the integer equations ${\displaystyle x=m_{1}n_{1}\pm 1=m_{2}n_{2}\pm 1}$, based on the Chinese remainder theorem and ${\displaystyle n_{1},n_{2}>2}$, there are at least four distinct square roots of ${\displaystyle 1}$ modulo ${\displaystyle N}$, and therefore at least two distinct non-trivial square roots exist. In fact, they are the solutions to ${\displaystyle b'=m_{1}n_{1}+1=m_{2}n_{2}-1}$ and ${\displaystyle b''=m_{1}n_{1}-1=m_{2}n_{2}+1}$.

The integers less than ${\displaystyle N}$ and coprime with ${\displaystyle N}$ form the multiplicative group of integers modulo ${\displaystyle N}$, which is a finite abelian group ${\displaystyle G}$. The size of this group is given by ${\displaystyle \varphi (N)}$. By the end of step 3, we have an integer ${\displaystyle a}$ in this group. As the group is finite, ${\displaystyle a}$ must have a finite order ${\displaystyle r}$, which is the smallest positive integer such that

${\displaystyle a^{r}\equiv 1{\bmod {N}}.}$

This is the order ${\displaystyle r}$ of the finite cyclic subgroup ⟨a⟩ of the group ${\displaystyle (\mathbb {Z} _{N})^{\times }}$, which is the smallest positive integer ${\displaystyle r}$ for which ${\displaystyle a^{x+r}{\bmod {N}}\equiv a^{x}{\bmod {N}}}$. Since ${\displaystyle a}$ and ${\displaystyle N}$ are coprime, by Euler's totient theorem, ${\displaystyle r}$ must exist, and divides ${\displaystyle \varphi (N)}$, where ${\displaystyle \varphi }$ denotes Euler's totient function.

Therefore, ${\displaystyle N}$ divides ${\displaystyle a^{r}-1}$ (also written ${\displaystyle N\mid a^{r}-1}$). Suppose that we are able to obtain ${\displaystyle r}$ and that it is even. (If ${\displaystyle r}$ is odd, then by step 5, we have to restart the algorithm with a different random number ${\displaystyle a}$) Now ${\displaystyle b\equiv a^{r/2}{\bmod {N}}}$ is a square root of ${\displaystyle 1}$ modulo ${\displaystyle N}$ that is different from ${\displaystyle 1}$. This is because ${\displaystyle r}$ is the order of ${\displaystyle a}$ modulo ${\displaystyle N}$, so ${\displaystyle a^{r/2}\not \equiv 1{\bmod {N}}}$, or else the order of ${\displaystyle a}$ in this group would be ${\displaystyle {\dfrac {r}{2}}}$. If ${\displaystyle a^{r/2}\equiv -1{\bmod {N}}}$, then by step 6, we have to restart the algorithm with a different random number ${\displaystyle a}$.

Eventually, we must hit an ${\displaystyle a}$ of order ${\displaystyle r}$ in ${\displaystyle G}$ such that ${\displaystyle b\equiv a^{r/2}\not \equiv \pm 1{\bmod {N}}}$. This is because such a ${\displaystyle b}$ is a square root of ${\displaystyle 1}$ modulo ${\displaystyle N}$ other than ${\displaystyle 1}$ and ${\displaystyle -1}$, whose existence is guaranteed by the Chinese remainder theorem, as the odd number ${\displaystyle N}$ is not a prime power.

Shor's period-finding algorithm relies heavily on the ability of a quantum computer to be in many states simultaneously.

Physicists call this behavior a "superposition" of states. To compute the period of a function ${\displaystyle f}$, we evaluate the function at all points simultaneously.

Quantum physics does not allow us to access all this information directly, however. A measurement will yield only one of all possible values, destroying all others. If not for the no-cloning theorem, we could first measure ${\displaystyle f(x)}$ without measuring ${\displaystyle x}$, and then make a few copies of the resulting state (which is a superposition of states all having the same ${\displaystyle f(x)}$). Measuring ${\displaystyle x}$ on these states would provide different ${\displaystyle x}$ values which give the same ${\displaystyle f(x)}$, leading to the period. Because we cannot make exact copies of a quantum state, this method does not work. Therefore, we have to carefully transform the superposition to another state that will return the correct answer with high probability. This is achieved by the quantum Fourier transform.

Shor thus had to solve three "implementation" problems. All of them had to be implemented "fast", which means that they can be implemented with a number of quantum gates that is polynomial in ${\displaystyle \log N}$.

1. Create a superposition of states. This can be done by applying Hadamard gates to all qubits in the input register. Another approach would be to use the quantum Fourier transform (see below).
2. Implement the function ${\displaystyle f}$ as a quantum transform. To achieve this, Shor used repeated squaring for his modular exponentiation transformation. It is important to note that this step is more difficult to implement than the quantum Fourier transform, in that it requires ancillary qubits and substantially more gates to accomplish.
3. Perform a quantum Fourier transform. By using controlled rotation gates and Hadamard gates, Shor designed a circuit for the quantum Fourier transform (with ${\displaystyle Q=2^{q}}$) that uses just ${\displaystyle {\dfrac {q(q-1)}{2}}=O\!\left((\log Q)^{2}\right)}$ gates.[17]

After all these transformations, a measurement will yield an approximation to the period ${\displaystyle r}$. For simplicity assume that there is a ${\displaystyle y}$ such that ${\displaystyle {\dfrac {yr}{Q}}}$ is an integer. Then the probability to measure ${\displaystyle y}$ is ${\displaystyle 1}$. To see this, we notice that then

${\displaystyle e^{-{\frac {2\pi ibyr}{Q}}}=1}$

for all integers ${\displaystyle b}$. Therefore, the sum whose square gives us the probability to measure ${\displaystyle y}$ will be ${\displaystyle {\dfrac {Q}{r}}}$, as ${\displaystyle b}$ takes roughly ${\displaystyle {\dfrac {Q}{r}}}$ values and thus the probability is ${\displaystyle {\dfrac {1}{r^{2}}}}$. There are ${\displaystyle r}$ possible values of ${\displaystyle y}$ such that ${\displaystyle {\dfrac {yr}{Q}}}$ is an integer, and also ${\displaystyle r}$ possibilities for ${\displaystyle f(x_{0})}$, so the probabilities sum to ${\displaystyle 1}$.

The period-finding routine can be considered a variation of the more general quantum phase estimation algorithm to determine the eigenvalue of a unitary corresponding to an eigenvector. In the case of the period-finding routine used in Shor's Algorithm, the unitary in question is modular multiplication by the chosen base mod ${\displaystyle N}$. While the computational basis ${\displaystyle |1\rangle }$ is not an eigenvector of this unitary, it is a uniform superposition of its ${\displaystyle r}$ eigenvectors and thus the measurement will give the eigenvalue's phase for one of the eigenvectors. Since not all such phases can be used to extract the period, the retries of the subroutine may be necessary. [18]

The runtime bottleneck of Shor's algorithm is quantum modular exponentiation, which is by far slower than the quantum Fourier transform and classical pre-/post-processing. There are several approaches to constructing and optimizing circuits for modular exponentiation. The simplest and (currently) most practical approach is to mimic conventional arithmetic circuits with reversible gates, starting with ripple-carry adders. Knowing the base and the modulus of exponentiation facilitates further optimizations.[19][20] Reversible circuits typically use on the order of ${\displaystyle n^{3}}$ gates for ${\displaystyle n}$ qubits. Alternative techniques asymptotically improve gate counts by using quantum Fourier transforms, but are not competitive with fewer than 600 qubits owing to high constants.