Improve knowledge baseHEADmaster

1 files changed, 36 insertions, 26 deletions

diff --git a/source/know/concept/shors-algorithm/index.md b/source/know/concept/shors-algorithm/index.md
index 678d5d2..bab88a3 100644
--- a/source/know/concept/shors-algorithm/index.md
+++ b/source/know/concept/shors-algorithm/index.md
@@ -29,10 +29,6 @@ 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$$.
 For reasons explained later,
 this means our goal is to find the period $$s$$ of
@@ -40,7 +36,7 @@ the modular exponentiation function $$f$$:
 
 $$\begin{aligned}
     f(x)
-    = a^x \bmod N
+    \equiv a^x \bmod N
 \end{aligned}$$
 
 For a given $$a$$ and $$N$$.
@@ -72,7 +68,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}$$.
+Where $$Q \equiv 2^q$$,
+and $$\Ket{x}$$ is the computational basis state $$\Ket{x_1} \cdots \Ket{x_q}$$.
 Moving on to $$U_f$$:
 
 $$\begin{aligned}
@@ -81,32 +78,41 @@ $$\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
+for an unknown arbitrary value of $$x_0$$.
+Let $$L$$ be number of periods that fit in the available qubits,
+then we know that:
 
 $$\begin{aligned}
-    f(x_0) = f(x_0 + s) = f(x_0 + 2s) = \cdots = f(x_0 + (L-1) s)
+    f(x_0)
+    = f(x_0 + s)
+    = \cdots
+    = f(x_0 + \ell s)
+    = \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, so we now have:
 
 $$\begin{aligned}
-    \frac{1}{\sqrt{L}} \sum_{\ell = 0}^{L - 1} \Ket{x_0 + \ell s}
+    \frac{1}{\sqrt{L}} \sum_{\ell = 0}^{L - 1} \Ket{x_0 + \ell s} \Ket{f(x_0)}
 \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:
+since we do not know the value of $$x_0$$,
+which, to make matters worse, changes every time we run the algorithm!
+But now we apply the QFT, which outputs the state below,
+where $$\omega_Q$$ is a $$Q$$th root of unity.
+From now on, we no longer write the measured qubits $$\Ket{f(x_0)}$$, leaving:
 
 $$\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)$$:
+Measuring this state causes a collapse into some $$\Ket{k}$$
+with a probability $$P(k)$$:
 
 $$\begin{aligned}
     P(k)
@@ -116,9 +122,9 @@ $$\begin{aligned}
 \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$$,
+Surprisingly, $$x_0$$ has disappeared,
+implying that we did not need to perform the measurement of $$f(x)$$ earlier!
+This makes some 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?
@@ -134,12 +140,13 @@ $$\begin{alignedat}{2}
 
 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$$.
+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
+For now, let us assume that $$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$$,
@@ -245,9 +252,11 @@ $$\begin{aligned}
     = a^x \bmod N
 \end{aligned}$$
 
-$$N$$ is the number to factorize, and $$a$$ is a random integer *coprime* to $$N$$,
+$$N$$ is the number to factorize, and $$a$$ is an integer that we can choose.
+For this to work, we should pick an $$a$$ that is *coprime* to $$N$$,
 meaning $$\gcd(a, N) = 1$$.
-The fact that $$s$$ is the period of $$f$$ for a certain $$a$$-value, implies that:
+Then the fact that $$s$$ is the period of $$f$$
+for a certain $$a$$-value implies that:
 
 $$\begin{aligned}
     a^x
@@ -257,7 +266,7 @@ $$\begin{aligned}
     = a^s \bmod N
 \end{aligned}$$
 
-Suppose that $$s$$ is even. In that case,
+For now, suppose that $$s$$ is even. In that case,
 we can rewrite the above equation as follows:
 
 $$\begin{aligned}
@@ -273,7 +282,8 @@ $$\begin{aligned}
     = 0 \bmod N
 \end{aligned}$$
 
-Because $$s$$ is even by assumption, the two factors on the left are integers,
+Because $$s$$ is even by assumption (for now),
+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: