From 16555851b6514a736c5c9d8e73de7da7fc9b6288 Mon Sep 17 00:00:00 2001 From: Prefetch Date: Thu, 20 Oct 2022 18:25:31 +0200 Subject: Migrate from 'jekyll-katex' to 'kramdown-math-sskatex' --- source/know/concept/shors-algorithm/index.md | 196 +++++++++++++-------------- 1 file changed, 98 insertions(+), 98 deletions(-) (limited to 'source/know/concept/shors-algorithm/index.md') diff --git a/source/know/concept/shors-algorithm/index.md b/source/know/concept/shors-algorithm/index.md index 0ff35c5..0241f9f 100644 --- a/source/know/concept/shors-algorithm/index.md +++ b/source/know/concept/shors-algorithm/index.md @@ -17,8 +17,8 @@ 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: +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) @@ -32,27 +32,27 @@ 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): +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$: +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$$: -Here, $\mathrm{QFT}_q$ refers to the $q$-qubit +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$. +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} @@ -61,8 +61,8 @@ $$\begin{aligned} \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: +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} @@ -71,8 +71,8 @@ $$\begin{aligned} = \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$: +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} @@ -80,15 +80,15 @@ $$\begin{aligned} \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$: +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: +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} @@ -96,7 +96,7 @@ $$\begin{aligned} Clearly, there is a periodic structure here, but we cannot measure it directly, -because we do not know the value of $x_0$, +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: @@ -104,8 +104,8 @@ $$\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)$: +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) @@ -114,13 +114,13 @@ $$\begin{aligned} = \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$. +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$? +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? +So, what does the above probability $$P(k)$$ work out to? There are two cases: $$\begin{alignedat}{2} @@ -132,22 +132,22 @@ $$\begin{alignedat}{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$. +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$, +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$, +$$\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: +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} \: (Q/s) \in \mathbb{N}: \qquad @@ -156,25 +156,25 @@ $$\begin{aligned} = \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, +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$. +**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$. +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: +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 @@ -183,7 +183,7 @@ $$\begin{aligned} = \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$, +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} @@ -191,62 +191,62 @@ $$\begin{aligned} \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$. +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, +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$. +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, +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$. +and we calculate whatever is left, to get an estimate of $$c/s$$. -Of course, $P(k)$ is a probability distribution, +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. +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 +**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, +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. +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}})$ +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}})$. +yielding a total complexity of $$\mathcal{O}(q^2 (\log{q})^2 \log{\log{q}})$$. -OK, but what does $s$ have to do with factorizing integers? -Well, recall that $f$ is given by: +OK, but what does $$s$$ have to do with 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: +$$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 @@ -256,7 +256,7 @@ $$\begin{aligned} = a^s \bmod N \end{aligned}$$ -Suppose that $s$ is even. In that case, +Suppose that $$s$$ is even. In that case, we can rewrite the above equation as follows: $$\begin{aligned} @@ -264,16 +264,16 @@ $$\begin{aligned} = 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$: +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$. +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} @@ -282,13 +282,13 @@ $$\begin{aligned} \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. +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$. +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$$. -- cgit v1.2.3