Expand knowledge base

7 files changed, 677 insertions, 4 deletions

diff --git a/content/know/concept/euler-equations/index.pdc b/content/know/concept/euler-equations/index.pdc
index cedfd93..0088d4f 100644
--- a/content/know/concept/euler-equations/index.pdc
+++ b/content/know/concept/euler-equations/index.pdc
@@ -21,7 +21,7 @@ There exist several forms, depending on
 the surrounding assumptions about the fluid.
 
 
-## Incompressible fluid, uniform density
+## Incompressible fluid
 
 In a fluid moving according to the velocity vield $\va{v}(\va{r}, t)$,
 the acceleration felt by a particle is given by
@@ -123,9 +123,6 @@ $$\begin{aligned}
     }
 \end{aligned}$$
 
-
-## Incompressible fluid, variable density
-
 The above form is straightforward to generalize to incompressible fluids
 with non-uniform spatial densities $\rho(\va{r}, t)$.
 In other words, these fluids are "lumpy" (variable density),
@@ -179,6 +176,10 @@ $$\begin{aligned}
     }
 \end{aligned}$$
 
+Usually, however, when discussing incompressible fluids,
+$\rho$ is assumed to be spatially uniform,
+in which case the latter equation is trivially satisfied.
+
 
 
 ## References
diff --git a/content/know/concept/quantum-fourier-transform/index.pdc b/content/know/concept/quantum-fourier-transform/index.pdc
new file mode 100644
index 0000000..627f2de
--- /dev/null
+++ b/content/know/concept/quantum-fourier-transform/index.pdc
@@ -0,0 +1,206 @@
+---
+title: "Quantum Fourier transform"
+firstLetter: "Q"
+publishDate: 2021-05-01
+categories:
+- Algorithms
+- Quantum information
+
+date: 2021-05-01T11:30:00+02:00
+draft: false
+markup: pandoc
+---
+
+# Quantum Fourier transform
+
+The **quantum Fourier transform (QFT)** is a quantum counterpart
+of the classical discrete Fourier transform.
+It is defined like so, where $\ket{x}$
+is an $n$-qubit computational basis state $\ket{x_1} \cdots \ket{x_n}$,
+and $\omega_N$ is an $N$th complex root of unity $\omega_N^N = 1$ with $N = 2^n$:
+
+$$\begin{aligned}
+    \boxed{
+        \ket{x}
+        \:\to\:
+        \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \omega_N^{xk} \ket{k}
+    }
+\end{aligned}$$
+
+Note that $\ket{x}$ and $\ket{k}$ refer to the same basis set;
+we use these names to clarify which "space" we are considering.
+Furthermore, note the sign of the exponent of $\omega_N$,
+which is the opposite of the classical DFT convention.
+In other words, the *forward* QFT corresponds to the *inverse* DFT.
+
+The **inverse quantum Fourier transform (iQFT)** has a different sign in the exponent:
+
+$$\begin{aligned}
+    \boxed{
+        \ket{k}
+        \:\to\:
+        \frac{1}{\sqrt{N}} \sum_{x = 0}^{N - 1} \omega_N^{-xk} \ket{x}
+    }
+\end{aligned}$$
+
+The above definitions of the QFT and iQFT describe
+the effect on a single basis vector $\ket{x}$,
+so the effect on an abitrary superposition follows from linearity,
+e.g. for the QFT:
+
+$$\begin{aligned}
+    \sum_{x = 0}^{N - 1} c_x \ket{x}
+    \:\to\:
+    \sum_{x = 0}^{N - 1} c_x \bigg( \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \omega_N^{xk} \ket{k} \bigg)
+\end{aligned}$$
+
+Classically, such a double sum takes
+$\mathcal{O}(N^2) = \mathcal{O}(2^{2n})$ time to evaluate naively,
+with a potential improvement to $\mathcal{O}(N \log{N}) = \mathcal{O}(n 2^n)$
+for smarter algorithms.
+Quantum computers can do a QFT in $\mathcal{O}(\log^2(N)) = \mathcal{O}(n^2)$ time,
+and approximate it in $\mathcal{O}(n \log{n})$ time.
+
+To find out how, we look at the forward QFT,
+which maps a basis state $\ket{x}$ to another state $\ket{\tilde{x}}$:
+
+$$\begin{aligned}
+    \ket{x}
+    \:\to\:
+    \ket{\tilde{x}}
+    = \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \omega_N^{xk} \ket{k}
+    = \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \exp\!\bigg( \frac{i 2 \pi x k}{N} \bigg) \ket{k}
+\end{aligned}$$
+
+We can decompose $k$ into its binary representation
+$k_1 2^{n-1} + k_2 2^{n-2} + ... + k_n 2^{0}$:
+
+$$\begin{aligned}
+    \ket{\tilde{x}}
+    &= \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} \exp\!\bigg( \frac{i 2 \pi x}{2^n} \sum_{j = 1}^{n} k_j 2^{n-j} \bigg) \ket{k}
+    \\
+    &= \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} \exp\!\bigg( i 2 \pi x \sum_{j = 1}^{n} \frac{k_j}{2^j} \bigg) \ket{k}
+\end{aligned}$$
+
+Expanding the exponential-of-a-sum into a product-of-exponentials then yields:
+
+$$\begin{aligned}
+    \ket{\tilde{x}}
+    &= \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} \prod_{j = 1}^{n} \exp\!\bigg( i 2 \pi x \frac{k_j}{2^j} \bigg) \ket{k}
+\end{aligned}$$
+
+If $k_j = 0$, the exponential is zero.
+We can thus separate this state into its individual qubits:
+
+$$\begin{aligned}
+    \ket{\tilde{x}}
+    &= \bigotimes_{j = 1}^{n} \frac{1}{\sqrt{2}} \bigg( \ket{0} + \exp\!\Big( \frac{i 2 \pi x}{2^j} \Big) \ket{1} \bigg)
+\end{aligned}$$
+
+Next, we use the trick from before:
+decompose $x$ as $x_1 2^{n-1} + x_2 2^{n-2} + ... + x_n 2^{0}$:
+
+$$\begin{aligned}
+    \ket{\tilde{x}}
+%    &= \bigotimes_{j = 1}^{n} \frac{1}{\sqrt{2}} \bigg( \ket{0} + \exp\!\Big( \frac{i 2 \pi}{2^j} \sum_{r = 1}^{n} x_r 2^{r-1} \Big) \ket{1} \bigg)
+%    \\
+    &= \bigotimes_{j = 1}^{n} \frac{1}{\sqrt{2}} \bigg( \ket{0} + \exp\!\Big( i 2 \pi \sum_{r = 1}^{n} x_r 2^{n-r-j} \Big) \ket{1} \bigg)
+\end{aligned}$$
+
+The factor $2^{n-r-j}$ may be smaller or bigger than $1$,
+so it is convenient for us to use the following notation
+for non-integer binary numbers.
+Note the decimal point in the middle:
+
+$$\begin{aligned}
+    \left[ a_1 \cdots a_{d} \:.\: a_{d+1} \cdots a_{n} \right]
+    = \sum_{r = 1}^{n} a_r 2^{d - r}
+\end{aligned}$$
+
+In the above QFT state, the position of the decimal point is $d = n - j$,
+so we write it as:
+
+$$\begin{aligned}
+    \ket{\tilde{x}}
+    &= \bigotimes_{j = 1}^{n} \frac{1}{\sqrt{2}} \bigg( \ket{0}
+    + \exp\!\Big( i 2 \pi \big[ x_1 \cdots x_{n-j} \:.\: x_{n-j+1} \cdots x_n \big] \Big) \ket{1} \bigg)
+\end{aligned}$$
+
+Because $\exp(i 2 \pi m) = 1$ for all integers $m$,
+we can discard bits before the decimal point:
+
+$$\begin{aligned}
+    \ket{\tilde{x}}
+    &= \frac{1}{\sqrt{2^n}} \bigotimes_{j = 1}^{n} \bigg( \ket{0} + \exp\!\Big( i 2 \pi \big[ 0\:.\: x_{n-j+1} \cdots x_n \big] \Big) \ket{1} \bigg)
+    \\
+    &= \frac{1}{\sqrt{2^n}} \bigg( \ket{0} + \exp\!\Big( i 2 \pi \big[ 0. x_n \big] \Big) \ket{1} \bigg)
+    \otimes \bigg( \ket{0} + \exp\!\Big( i 2 \pi \big[ 0. x_{n-1} x_n \big] \Big) \ket{1} \bigg)
+    \otimes \cdots
+\end{aligned}$$
+
+Furthermore, each exponential can be factorized,
+with every factor containing one bit of $x$:
+
+$$\begin{aligned}
+    \exp\!\Big( i 2 \pi \big[ 0\:.\: x_{n-j+1} \cdots x_n \big] \Big)
+    = \exp\!\Big( i 2 \pi \frac{x_{n-j+1}}{2} \Big) \cdots \exp\!\Big( i 2 \pi \frac{x_{n}}{2^{j}} \Big)
+\end{aligned}$$
+
+This suggests a way to implement the QFT using
+[quantum gates](/know/concept/quantum-gate/) in a circuit.
+If the $j$th qubit is in $\ket{+} = (\ket{0} + \ket{1})/\sqrt{2}$,
+then for each bit $x_{n-j+r}$ where $r \in \{1, ..., j\}$:
+
++ If $x_{n-j+r} = 0$, do nothing.
++ If $x_{n-j+r} = 1$, add a relative phase $2 \pi / 2^{r}$.
+
+The full QFT algorithm therefore proceeds as follows,
+for the $(n\!-\!j\!+\!1)$'th input $\ket{x_{n-j+1}}$:
+
+1.  Apply the Hadamard gate $H$.
+    If $x_{n-j+1} = 0$, this puts the qubit in $\ket{+}$.
+    If $x_{n-j+1} = 1$, this puts the qubit in $\ket{+}$,
+    and then adds a phase $\pi$, yielding $\ket{-}$.
+2.  Apply the phase shift gate $R_{\phi}$ controlled by $x_{n-j+2}$,
+    with angle $\phi = 2 \pi / 2^{2}$.
+3.  Apply $R_{\phi}$ controlled by $x_{n-j+3}$,
+    with angle $\phi = 2 \pi / 2^{3}$...
+4.  And so on, until the $n$th bit $x_n$ is reached,
+    and used to control $R_\phi$ with $\phi = 2 \pi / 2^{j}$.
+
+And so on, for each $j \in \{1, ..., n\}$,
+and we reach the above expression for $\ket{\tilde{x}}$.
+We started from the $(n\!-\!j\!+\!1)$'th input qubit,
+i.e. we read the input in reverse order.
+Therefore all the qubits need to be swapped back to front,
+either before or after the above algorithm is run.
+
+The quantum circuit to execute the mentioned steps is illustrated below,
+excluding the swapping part to get the right order.
+Here, $R_m$ means $R_\phi$ with $\phi = 2 \pi / 2^m$:
+
+<a href="qft-circuit-noswap.png">
+<img src="qft-circuit-noswap.png" style="width:100%;display:block;margin:auto;">
+</a>
+
+Again, note how the inputs $\ket{x_j}$ and outputs $\ket{k_j}$ are in the opposite order.
+The complete circuit, including the swapping at the end,
+therefore looks like this:
+
+<a href="qft-circuit-swap.png">
+<img src="qft-circuit-swap.png" style="width:85%;display:block;margin:auto;">
+</a>
+
+For each of the $n$ qubits, $\mathcal{O}(n)$ gates are applied,
+so overall the QFT algorithm is $\mathcal{O}(n^2)$.
+
+
+
+## References
+1.  J.S. Neergaard-Nielsen,
+    *Quantum information: lectures notes*,
+    2021, unpublished.
+2.  S. Aaronson,
+    *Introduction to quantum information science: lecture notes*,
+    2018, unpublished.
+
diff --git a/content/know/concept/quantum-fourier-transform/qft-circuit-noswap.png b/content/know/concept/quantum-fourier-transform/qft-circuit-noswap.png
new file mode 100644
index 0000000..651e1a4
--- /dev/null
+++ b/content/know/concept/quantum-fourier-transform/qft-circuit-noswap.png
diff --git a/content/know/concept/quantum-fourier-transform/qft-circuit-swap.png b/content/know/concept/quantum-fourier-transform/qft-circuit-swap.png
new file mode 100644
index 0000000..8ca7cfe
--- /dev/null
+++ b/content/know/concept/quantum-fourier-transform/qft-circuit-swap.png
diff --git a/content/know/concept/reynolds-number/index.pdc b/content/know/concept/reynolds-number/index.pdc
new file mode 100644
index 0000000..bd18f2f
--- /dev/null
+++ b/content/know/concept/reynolds-number/index.pdc
@@ -0,0 +1,157 @@
+---
+title: "Reynolds number"
+firstLetter: "R"
+publishDate: 2021-05-04
+categories:
+- Physics
+- Fluid mechanics
+- Fluid dynamics
+
+date: 2021-05-04T09:45:22+02:00
+draft: false
+markup: pandoc
+---
+
+# Reynolds number
+
+The [Navier-Stokes equations](/know/concept/navier-stokes-equations/)
+are infamously tricky to solve,
+so we would like a way to qualitatively predict
+the behaviour of a fluid without needing the flow $\va{v}$.
+Consider the main equation:
+
+$$\begin{aligned}
+    \pdv{\va{v}}{t} + (\va{v} \cdot \nabla) \va{v}
+    = - \frac{\nabla p}{\rho} + \nu \nabla^2 \va{v}
+\end{aligned}$$
+
+Let us introduce the dimensionless variables $\va{v}'$, $\va{r}'$, $t'$ and $p'$,
+where $U$ and $L$ are respectively a characteristic velocity and length
+of the system at hand:
+
+$$\begin{aligned}
+    \va{v} = U \va{v}'
+    \qquad
+    \va{r} = L \va{r}'
+    \qquad
+    t = \frac{L}{U} t'
+    \qquad
+    p = \rho U^2 p'
+\end{aligned}$$
+
+In this non-dimenionsalization, the differential operators are scaled as follows:
+
+$$\begin{aligned}
+    \pdv{t}
+    = \frac{U}{L} \pdv{t'}
+    \qquad \quad
+    \nabla
+    = \frac{1}{L} \nabla'
+\end{aligned}$$
+
+Putting everything into the main Navier-Stokes equation then yields:
+
+$$\begin{aligned}
+    \frac{U^2}{L} \pdv{\va{v}'}{t'} + \frac{U^2}{L} (\va{v}' \cdot \nabla') \va{v}'
+    = - \frac{U^2}{L} \nabla' p' + \frac{U \nu}{L^2} \nabla'^2 \va{v}'
+\end{aligned}$$
+
+After dividing out $U^2/L$,
+we arrive at the form of the original equation again:
+
+$$\begin{aligned}
+    \pdv{\va{v}'}{t'} + (\va{v}' \cdot \nabla') \va{v}'
+    = - \nabla' p' + \frac{\nu}{U L} \nabla'^2 \va{v}'
+\end{aligned}$$
+
+The constant factor of the last term
+leads to the definition of the **Reynolds number** $\mathrm{Re}$:
+
+$$\begin{aligned}
+    \boxed{
+        \mathrm{Re}
+        \equiv \frac{U L}{\nu}
+    }
+\end{aligned}$$
+
+If we choose $U$ and $L$ appropriately for a given system,
+the Reynolds number allows us to predict the general trends.
+It can be regarded as the inverse of an "effective viscosity":
+when $\mathrm{Re}$ is large, viscosity only has a minor role,
+but when $\mathrm{Re}$ is small, it dominates the dynamics.
+
+Another way is thus to see the Reynolds number
+as the characteristic ratio between the advective term
+(see [material derivative](/know/concept/material-derivative/))
+to the [viscosity](/know/concept/viscosity/) term,
+since $\va{v} \sim U$:
+
+$$\begin{aligned}
+     \mathrm{Re}
+     \approx \frac{\big| (\va{v} \cdot \nabla) \va{v} \big|}{\big| \nu \nabla^2 \va{v} \big|}
+     \approx \frac{U^2 / L}{\nu U / L^2}
+     = \frac{U L}{\nu}
+\end{aligned}$$
+
+In other words, $\mathrm{Re}$
+describes the relative strength of intertial and viscous forces.
+Returning to the dimensionless Navier-Stokes equation:
+
+$$\begin{aligned}
+    \pdv{\va{v}'}{t'} + (\va{v}' \cdot \nabla') \va{v}'
+    = - \nabla' p' + \frac{1}{\mathrm{Re}} \nabla'^2 \va{v}'
+\end{aligned}$$
+
+For large $\mathrm{Re} \gg 1$,
+we can neglect the latter term,
+such that redimensionalizing yields:
+
+$$\begin{aligned}
+    \pdv{\va{v}}{t} + (\va{v} \cdot \nabla) \va{v}
+    = - \nabla p
+\end{aligned}$$
+
+Which is simply the main [Euler equation](/know/concept/euler-equations/)
+for an ideal fluid, i.e. a fluid without viscosity.
+
+
+
+## Stokes flow
+
+A notable case is so-called **Stokes flow** or **creeping flow**,
+meaning flow at $\mathrm{Re} \ll 1$.
+In this limit, the Navier-Stokes equations can be linearized:
+since $\mathrm{Re}$ is the advective-to-viscous ratio,
+$\mathrm{Re} \ll 1$ implies that we can ignore the advective term, leaving:
+
+$$\begin{aligned}
+    \boxed{
+        \pdv{\va{v}}{t}
+        = - \frac{\nabla p}{\rho} + \nu \nabla^2 \va{v}
+    }
+\end{aligned}$$
+
+This equation is called the **unsteady Stokes equation**.
+Usually, however, such flows are assumed to be steady
+(i.e. time-invariant), leading to the **steady Stokes equation**:
+
+$$\begin{aligned}
+    \boxed{
+        \nabla p
+        = \eta \nabla^2 \va{v}
+    }
+\end{aligned}$$
+
+This equation is much easier to solve than the full Navier-Stokes equation
+thanks to being linear,
+and has some interesting properties, such as time-reversibility.
+
+
+
+## References
+1.  B. Lautrup,
+    *Physics of continuous matter: exotic and everyday phenomena in the macroscopic world*, 2nd edition,
+    CRC Press.
+2.  R. Fitzpatrick,
+    [Dimensionless numbers in incompressible flow](https://farside.ph.utexas.edu/teaching/336L/Fluid/node17.html),
+    University of Texas.
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.
+
diff --git a/content/know/concept/shors-algorithm/shors-circuit.png b/content/know/concept/shors-algorithm/shors-circuit.png
new file mode 100644
index 0000000..724b546
--- /dev/null
+++ b/content/know/concept/shors-algorithm/shors-circuit.png