# Shor's factoring algorithm Shor's algorithm computes the period of periodic functions. This can be reduced to factoring. For example $f(x)=a^x\bmod N$ satisfies $f(x)=f(x+r)$ for $r$ the order of $a$ modulo $N$ i.e., $a^r\equiv 1\bmod N$. $f$ has period $r$ and this algorithm computes it efficiently. The goal is to find a factor of $N$. steps: 1) Pick random $a<N$ 2) if $\gcd(a,N)>1$ then we have a factor of $N$ otherwise continue 3) find the order $r$ of $a\bmod N$ i.e., $a^r\equiv 1\bmod N$ with Shor's algorithm. 4) If $r$ is odd, stop and start for new $a$ 5) If $r$ is even, we have $a^r-1=(a^{r/2}-1)(a^{r/2}+1)$ and $N|(a^r-1)$ i.e., $N \mid (a^{r/2}-1)(a^{r/2}+1)$. compute $\gcd(a^{r/2}-1,N)$ and $\gcd(a^{r/2}+1,N)$. note that we need smaller value than $a^r$ because $\gcd(a^r,N)=N$ and so give no information on factors. ## How DFT can find period of function Let $f(x):\mathbb{Z}_N\mapsto\mathbb{Z}_N$ (e.g., Discrete log function) with period $r$ i.e., $f(x)=f(x+r)=f(x+2r)=\cdots$ for every $x$. The case that $r | N$. The DFT of $f(x)$ , $\hat f(k)=\sum_{x=0}^Nf(x)e^{-2\pi i kx/N}$ . writing $x=jr+s$ we get $ \begin{align} \hat f(k)&=\sum_{s=0}^{r-1}\sum_{j=0}^{N/r-1}f(jr+s)e^{-2\pi i k (jr+s)/N} \\ &=\sum_{s=0}^{r-1}\sum_{j=0}^{N/r-1}f(s)e^{-2\pi i k jr/N} e^{-2\pi i ks/N} \\ &=\bigg[\sum_{s=0}^{r-1}f(s)e^{-2\pi i ks/N}\bigg]\bigg[\sum_{j=0}^{N/r-1}e^{-2\pi i k jr/N} \bigg] \end{align} $ The right side can be written as $\sum_{j=0}^{N/r-1}\big(e^{\frac{-2\pi i}{(N/rk)}}\big)^j$ . if $rk/N\not\in\mathbb{Z}$ then this is a geometric series with $q\not=1$ and so $ \sum_{j=0}^{N/r-1}\big(e^{\frac{-2\pi i}{(N/rk)}}\big)^j= 1\frac{\big(e^{\frac{-2\pi i}{(N/rk)}}\big)^{N/r}-1}{e^{\frac{-2\pi i}{(N/rk)}}-1}=\frac{e^{-2\pi i k}-1}{e^{\frac{-2\pi i}{(N/rk)}}-1}=0 $ i.e., for every index $k$ s.t. $k\ne mN/r$ for $m\in\mathbb{Z}$ , $\hat f(k)=0$. But if $rk/N\in\mathbb{Z}$ we get $\sum_{j=0}^{N/r-1}\big(e^{\frac{-2\pi i}{(N/rk)}}\big)^j=\sum_{j=0}^{N/r-1}1^j=N/r$ and this happens for $k=mN/r$ for $m=0,...,r-1$. So $\{\hat f(k)\}_{k=0}^{N-1}$ contains non zeros values at indices $0, N/r,2N/r,...,(r-1)N/r$ and $N/r$ zero's in between those values. This means that from the size of consecutive zeros $\Delta k$ , we can compute the period $r=N/\Delta k$. ## How to find the period r of a function efficiently? Let $Q$ be a power 2 s.t. $N^2\le Q<2N^2$ . Using Hadamard gates prepare superposition of computation basis up to $Q$ then clone them to 2nd register and compute the gate of $|x\rangle\mapsto|a^x\bmod N\rangle$ , measure the 2nd register containing the powers to get $a^{j_0}\bmod N$ and the . The first register collapses to $\frac{1}{\sqrt L}\sum_{\ell=0}^{L-1}|j_0+\ell r\rangle$ where $L\approx Q/r$. Next, we apply $QFT_Q$ to $\frac{1}{\sqrt L}\sum_{\ell=0}^{L-1}|j_0+\ell r\rangle$ . A reminder, $QFT_Q|j\rangle=\frac{1}{\sqrt Q}\sum_{c=0}^{Q-1}e^{2\pi i jc/Q}|c\rangle$ .So, $ \begin{align} QFT_Q\bigg(\frac{1}{\sqrt L}\sum_{\ell=0}^{L-1}|j_0+\ell r\rangle\bigg)&=\frac{1}{\sqrt {LQ}}\sum_{\ell=0}^{L-1}\bigg(\sum_{c=0}^{Q-1}e^{2\pi i (j_0+\ell r)c/Q}|c\rangle\bigg) \\ & =\frac{1}{\sqrt {LQ}}\sum_{c=0}^{Q-1}\bigg(\sum_{\ell=0}^{L-1}e^{2\pi i (j_0+\ell r)c/Q}|c\rangle\bigg) \end{align} $ the amplitude of $|c\rangle$ becomes $\sum_{\ell=0}^{L-1}e^{2\pi i (j_0+\ell r)c/Q}$ and $e^{2\pi i j_0c/Q}$ does not affect the amplitude of $|c\rangle$ and so get be ignored. The amplitude which are large are those that the terms $e^{2\pi i \ell rc/Q}$ for $\ell=0,1,..,Q$ points to the same direction so they accumulate and not cancel each other. if all points in the direction of 1 then, $e^{2\pi i \ell rc/Q}=1$ and $rc/Q\approx k$ for $k$ integer i.e., $c\approx Qk/r$. The $QFT_Q$ amplifies the amplitudes of $\frac{Q}{r},\frac{2Q}{r},..$ The register containing the QFT is measured and we get $c\approx Qk/r$ . We can then compute $\frac{c}{Q}$ as $\frac{c}{Q}\approx \frac{k}{r}$ and if we reduce it by dividing the gcd we get that the denominator is equal to some divisor of $r$. repeating this computation will provide all divisors of $r$ and so $r$ can be constructed by computing their LCM (least common multiplier). The expectation of getting all divisors after 5 attempts is very high 0.964 (why?). Looking at the result of QFT, the amplitude $S(c)$ of $\ket c$ is equal to $S(c)=\sum_{\ell=0}^{L-1}e^{2\pi i (j_0+\ell r)c/Q}|c\rangle$ . $|S|=|\frac{\sin(L\delta/2)}{\sin\delta/2}|$ where $\delta=2\pi(rc/Q-s)$ for the nearest integer $s$. The $|S|$ formula make sense as $S=\sum_{j=0}^{L-1} (e^{i\theta})^j=\frac{1-e^{i\theta L}}{1-e^{i\theta}}$ and $|1-e^{i\alpha}|=|e^{i\alpha/2}(e^{-i\alpha/2}- e^{i\alpha/2})|=|-2ie^{i\alpha/2}\sin(\alpha/2)|=2|\sin(\alpha/2)|$ . if $\delta$ close to zero, $|S|\approx|\frac{L\delta/2}{\delta/2}|=L$ i.e., the amplitude is almost maximum. If $\delta$ is large i.e., close to integer multiplication of $\pi$ and $\sin(\delta/2)$ is close to $\pm 1$, $|\sin(L\delta/2)|<1$ and $|S|<\frac{1}{\sin(\delta/2)}$ . This means that $\frac{|S|}{|L|}<\frac{1}{L}$ i.e., the ratio of $|S|$ and $|L$| is very small as $L>N$ is very large. $L>N$ because $Q$ is chosen s.t., $N^2<Q$ and the period $r$ satisfies $r<N$ , we get $L\approx Q/r>N^2/N=N$ and $N$ is large. Intuitively, it acts as the small "hills" in the plot below. Plot for $y=|\frac{\sin(10x)}{\sin(x)}|$ . ![[Pasted image 20260826175350.png|263]] By choosing value for $Q$ (at beginning) and the fact that $r<N$ we can reconstruct the fraction $Qk/r$ and from there compute efficiently $r$ classically using [[Continued Fractions]]. ## Extensions to Shor's algorithm The Shor's algorithm can seen as an instance of [[The hidden subgroup problem (HSP)]] for the cyclic subgroup case. It can be used to solve also the abelian HSP. Reference: - [Quantum Algorithms forthe Discrete LogarithmProblem (MA Thesis)](https://repositum.tuwien.at/handle/20.500.12708/18830) - [[@Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer]] ## Created 2026-06-09 12:20