diff options
Diffstat (limited to 'content/know/concept/shors-algorithm/index.pdc')
| -rw-r--r-- | content/know/concept/shors-algorithm/index.pdc | 309 |
1 files changed, 309 insertions, 0 deletions
diff --git a/content/know/concept/shors-algorithm/index.pdc b/content/know/concept/shors-algorithm/index.pdc new file mode 100644 index 0000000..0700408 --- /dev/null +++ b/content/know/concept/shors-algorithm/index.pdc @@ -0,0 +1,309 @@ +--- +title: "Shor's algorithm" +firstLetter: "S" +publishDate: 2021-04-13 +categories: +- Quantum information +- Cryptography +- Algorithms + +date: 2021-04-13T10:29:07+02:00 +draft: false +markup: pandoc +--- + +# Shor's algorithm + +**Shor's algorithms** was the first truly useful quantum algorithm. +It can solve important problems, +most notably integer factorization, +much more efficiently than any classical algorithm. +It weakens widely-used cryptographic schemes, +such as RSA and [Diffie-Hellman](/know/concept/diffie-hellman-key-exchange/). + +In essence, Shor's algorithm's revolutionary achievement +is that it can efficiently find the periods $s_1, ..., s_A$ +of a function $f(x_1, ..., x_A)$ on a discrete finite field, where: + +$$\begin{aligned} + f(x_1, ..., x_A) + = f(x_1 + s_1, ..., x_A + s_A) +\end{aligned}$$ + +This is a so-called *hidden subgroup problem* for a *finite Abelian group*. +With minimal modifications, +Shor's algorithm can solve practically every such problem. + + +## Integer factorization + +Originally, Shor's algorithm was designed to factorize an integer $N$, +in which case the goal is to find the period $s$ of +the modular exponentiation function $f$ (for reasons explained later): + +$$\begin{aligned} + f(x) + = a^x \bmod N +\end{aligned}$$ + +For a given $a$ and $N$. +The period $s$ is the smallest integer satisfying $f(x) = f(x+s)$. +To do this, the following $2q$-qubit quantum circuit is used, +with $q$ chosen so that $N^2 \le 2^q < 2 N^2$: + +<a href="shors-circuit.png"> +<img src="shors-circuit.png" style="width:70%;display:block;margin:auto;"> +</a> + +Here, $\mathrm{QFT}_q$ refers to the $q$-qubit +[quantum Fourier transform](/know/concept/quantum-fourier-transform/), +and the oracle $U_f$ calculates $f(x)$ for predetermined values of $a$ and $N$. +It is an XOR oracle, working as follows: + +$$\begin{aligned} + \ket{x} \ket{y} + \quad \to \boxed{U_f(a, N)} \to \quad + \ket{x} \ket{y \oplus f(x)} +\end{aligned}$$ + +Execution starts by applying the [Hadamard gate](/know/concept/quantum-gate/) $H$ +to the first $q$ qubits, yielding: + +$$\begin{aligned} + \ket{0}^{\otimes q} \ket{0}^{\otimes q} + \quad \to \boxed{H^{\otimes q}} \to \quad + \ket{+}^{\otimes q} \ket{0}^{\otimes q} + = \frac{1}{\sqrt{Q}} \sum_{x = 0}^{Q - 1} \ket{x} \ket{0}^{\otimes q} +\end{aligned}$$ + +Where $Q = 2^q$, and $\ket{x}$ is the computational basis state $\ket{x_1} \cdots \ket{x_q}$. +Moving on to $U_f$: + +$$\begin{aligned} + \frac{1}{\sqrt{Q}} \sum_{x = 0}^{Q - 1} \ket{x} \ket{0}^{\otimes q} + \quad \to \boxed{U_f(a, N)} \to \quad + \frac{1}{\sqrt{Q}} \sum_{x = 0}^{Q - 1} \ket{x} \ket{f(x)} +\end{aligned}$$ + +Then we measure $f(x)$, causing it collapse as follows, +for an unknown arbitrary value of $x_0$: + +$$\begin{aligned} + f(x_0) = f(x_0 + s) = f(x_0 + 2s) = \cdots = f(x_0 + (L-1) s) +\end{aligned}$$ + +Due to [entanglement](/know/concept/quantum-entanglement/), +the unmeasured (top $q$) qubits change state into a superposition: + +$$\begin{aligned} + \frac{1}{\sqrt{L}} \sum_{\ell = 0}^{L - 1} \ket{x_0 + \ell s} +\end{aligned}$$ + +Clearly, there is a periodic structure here, +but we cannot measure it directly, +because we do not know the value of $x_0$, +which, to make matters worse, changes every time we run the algorithm. +This is where the QFT comes in, which outputs the following state: + +$$\begin{aligned} + \frac{1}{\sqrt{QL}} \sum_{k = 0}^{Q - 1} \bigg( \sum_{\ell = 0}^{L - 1} \omega_Q^{(x_0 + \ell s) k} \bigg) \ket{k} +\end{aligned}$$ + +Where $\omega_Q$ is a $Q$th root of unity. +Measuring this state yields a $\ket{k}$, with a probability $P(k)$: + +$$\begin{aligned} + P(k) + = \frac{1}{QL} \bigg| \sum_{\ell = 0}^{L - 1} \omega_Q^{(x_0 + \ell s) k} \bigg|^2 + = \frac{1}{QL} \bigg| \omega_Q^{x_0 k} \sum_{\ell = 0}^{L - 1} \omega_Q^{\ell s k} \bigg|^2 + = \frac{1}{QL} \bigg| \sum_{\ell = 0}^{L - 1} \omega_Q^{\ell s k} \bigg|^2 +\end{aligned}$$ + +The last step holds because $|\omega_Q| = 1$. +Surprisingly, this implies that we did not need +to perform the measurement of $f(x)$ earlier! +This makes sense: the period $s$ does not depend on $x_0$, +so why would we need an implicit $x_0$ to determine $s$? + +So, what does the above probability $P(k)$ work out to? +There are two cases: + +$$\begin{alignedat}{2} + &\mathrm{if} \: \omega_Q^{sk} = 1: \qquad + &&P(k) = \frac{1}{QL} |L|^2 = \frac{L}{Q} + \\ + &\mathrm{if} \: \omega_Q^{sk} \neq 1: \qquad + &&P(k) = \frac{1}{QL} \Bigg| \frac{1 - \omega_Q^{sk L}}{1 - \omega_Q^{sk}} \Bigg|^2 +\end{alignedat}$$ + +Where the latter case was evaluated as a geometric series. +The condition $\omega_Q^{sk}\!=\!1$ is equivalent to asking +if $sk$ is a multiple of $Q$, i.e. if $sk = cQ$, for an integer $c$. + +Recall that $L$ is the number of times that $s$ fits in $Q$, +so $L\!=\!\lfloor Q / s \rfloor$. +Assuming $Q/s$ is an integer, then $L\!=\!Q/s$ and $Q\!=\!s L$, +which tells us that +$\omega_Q^{sk}\!=\!\omega_{s L}^{s k}\!=\!\omega_L^k$. +This implies that if $k$ is a multiple of $L$ (i.e. $k\!=\!c L$), +then $\omega_L^k\!=\!1$, so $P(k) = L / Q$, +which is exactly what we got earlier! + +In other words, the condition $\omega_Q^{sk}\!=\!1$ +is equivalent to $Q/s$ being an integer. +In that case, we have that $Q\!=\!sL$, +which we substitute into $P(k)$ from earlier: + +$$\begin{aligned} + %\mathrm{if} \: \omega_Q^{sk} = \omega_L^k = 1: \qquad + \mathrm{if} \: (Q/s) \in \mathbb{N}: \qquad + P(k) + = \frac{L}{Q} + = \frac{1}{s} +\end{aligned}$$ + +And because $k$ is a multiple of $L$, +and $L$ fits $s$ times in $Q$, +there must be exactly $s$ values of $k$ that satisfy $P(k) = 1/s$. +Therefore the probability of all other $k$-values is zero! +This becomes clearer when you look at the sum used to calculate $P(k)$: +if $Q\!=\!sL$, then it sums $\omega_L^{\ell k}$ over $\ell$, +leading to perfect destructive interference for the "bad" $k$-values, +leaving only the "good" ones. + +**So, to summarize: if** $Q/s$ **is an integer**, +then measuring only yields $k$-values that are multiples of $L\!=\!Q/s$. +Running Shor's algorithm several times then gives +several $k$-values separated by $L$. +That tells us what $L$ is, and we already know $Q$, +so we *finally* find the period $s = Q/L$. + +That begs the question: what if $Q/s$ is not an integer? +We cannot *check* this, since $s$ is unknown! +Instead, we rewrite the probability $P(k)$ as follows: + +$$\begin{aligned} + \mathrm{if} \: (Q/s) \not\in \mathbb{N}: \qquad + P(k) + = \frac{1}{QL} \Bigg| \frac{1 - \omega_Q^{sk L}}{1 - \omega_Q^{sk}} \Bigg|^2 + = \frac{1}{QL} \Bigg| \frac{\sin(\pi s k L / Q)}{\sin(\pi s k / Q)} \Bigg|^2 +\end{aligned}$$ + +This function peaks if $s k$ is close to a multiple of $Q$, i.e. $s k \approx c Q$, +which we rearrange: + +$$\begin{aligned} + %\mathrm{if} \: (Q/s) \not\in \mathbb{N}: \qquad + \frac{k}{Q} \approx \frac{c}{s} +\end{aligned}$$ + +We know the left-hand side, +and, from the definition of $f(x)$, +clearly $s \le N$. +We chose $Q \sim N^2$, +so $s$ is quite small, +and consequently $c$ is too, since $k < Q$. + +In other words, $c/s$ is a "simple" fraction, +so our goal is to find a "simple" fraction +that is close to the "complicated" fraction $k/Q$. +For example, if $k/Q\!=\!0.332$, +then probably $c/s\!=\!1/3$. + +This can be done rigorously using the **continued fractions algorithm**: +write $k/Q$ as a continued fraction, +until the non-integer part of the denominator becomes small enough. +This part is then neglected, +and we calculate whatever is left, to get an estimate of $c/s$. + +Of course, $P(k)$ is a probability distribution, +so even though the odds are in our favour, +we might occasionally measure a misleading $k$-value. +Running Shor's algorithm several times "fixes" this. + +**So, to summarize: if** $Q/s$ **is not an integer**, +the measured $k$-values are generally close to $c Q / s$ for an integer $c$. +By approximating $k/Q$ using the continued fraction algorithm, +we estimate $c/s$. +Repeating this procedure gives several values of $c/s$, +such that $s$ is easy to deduce +by taking the least common multiple of the denominators. + +In any case, once we think we have $s$, +we can easily verify that $f(x)\!=\!f(x\!+\!s)$. +Whether $s$ is the *smallest* such integer depends on how lucky we are, +but fortunately, for most applications of this algorithm, +that does not actually matter, +and usually we find the smallest $s$ anyway. + +You typically need to repeat the algorithm $\mathcal{O}(\log{q})$ times, +and the QFT is $\mathcal{O}(q^2)$. +The bottleneck is modular exponentiation $f$, +which is $\mathcal{O}(q^2 (\log{q}) \log{\log{q}})$ +and therefore worse than the QFT, +yielding a total complexity of $\mathcal{O}(q^2 (\log{q})^2 \log{\log{q}})$. + +OK, but what does $s$ have to do factorizing integers? +Well, recall that $f$ is given by: + +$$\begin{aligned} + f(x) + = a^x \bmod N +\end{aligned}$$ + +$N$ is the number to factorize, and $a$ is a random integer *coprime* to $N$, +meaning $\gcd(a, N) = 1$. +The fact that $s$ is the period of $f$ for a certain $a$-value, implies that: + +$$\begin{aligned} + a^x + = a^{x + s} \bmod N + \quad \implies \quad + 1 + = a^s \bmod N +\end{aligned}$$ + +Suppose that $s$ is even. In that case, +we can rewrite the above equation as follows: + +$$\begin{aligned} + (a^{s/2})^2 - 1 + = 0 \bmod N +\end{aligned}$$ + +In other words, $(a^{s/2})^2 \!-\! 1$ is a multiple of $N$. +We then use that $(a\!-\!b) (a\!+\!b) = a^2\!-\!b^2$: + +$$\begin{aligned} + \big( a^{s/2} - 1 \big) \big( a^{s/2} + 1 \big) + = 0 \bmod N +\end{aligned}$$ + +Because $s$ is even by assumption, the two factors on the left are integers, +and as just mentioned, their product is a multiple of $N$. +Then we only need to calculate: + +$$\begin{aligned} + \gcd\!\big( a^{s/2}\!-\!1, N \big) > 1 + \quad\:\: \mathrm{and} \quad\:\: + \gcd\!\big( a^{s/2}\!+\!1, N \big) > 1 +\end{aligned}$$ + +And there we have the factors of $N$! +The $\gcd$ can be calculated efficiently in $\mathcal{O}(q^2)$ time. + +But what if $s$ is odd? +No problem, then we just choose a new $a$ coprime to $N$, +and keep repeating Shor's algorithm until we do find an even $s$. +We do the same if $a^{s/2}\!\pm\!1$ is itself a multiple of $N$. + + + +## References +1. J.S. Neergaard-Nielsen, + *Quantum information: lectures notes*, + 2021, unpublished. +2. S. Aaronson, + *Introduction to quantum information science: lecture notes*, + 2018, unpublished. + |