skip to content
Ivan's wiki
Site Tools
Search
Tools
Show pagesource
Backlinks
Recent Changes
Media Manager
Sitemap
>
Recent Changes
Media Manager
Sitemap
shor
This page is read only. You can view the source, but not change it.
# Shor's algorithm **Shor's algorithm** is a quantum algorithm that factors large integers in polynomial time. It was invented by Peter Shor in 1994 and is one of the most consequential results in quantum computing, because it would break the RSA public-key cryptosystem if run on a sufficiently large fault-tolerant quantum computer. Classically, the best known factoring algorithm (the general number field sieve) runs in sub-exponential time $O(e^{O(n^{1/3}\log^{2/3} n)})$ for an $n$-bit integer. Shor's algorithm runs in polynomial time $O(n^3)$ on a quantum computer with $O(n)$ qubits, an exponential speedup. ## Structure Shor's algorithm reduces the factoring problem to the **order-finding** problem. Given $N$ to factor and a randomly chosen coprime $a$ (with $\gcd(a, N) = 1$), find the smallest $r$ such that $a^r \equiv 1 \pmod{N}$. If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then $\gcd(a^{r/2} \pm 1, N)$ yields a non-trivial factor of $N$ with probability at least $1/2$. ## Quantum subroutine The quantum part of Shor's algorithm is order-finding via [quantum phase estimation](/qpe). First, prepare a uniform superposition over $x \in \{0, \ldots, 2^n-1\}$ and query the modular exponentiation function to get: $$\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\lvert x\rangle\lvert a^x \bmod N\rangle$$ Measuring the second register collapses the first to a superposition of all $x$ giving the same remainder. Applying the inverse [QFT](/qft) then concentrates the probability at multiples of $2^n/r$, allowing $r$ to be recovered by continued fractions. The classical part then computes $\gcd(a^{r/2}\pm 1, N)$.
Page Tools
Show pagesource
Backlinks
Back to top