Initial commit after migration from Hugo

1 files changed, 198 insertions, 0 deletions

diff --git a/source/know/concept/quantum-fourier-transform/index.md b/source/know/concept/quantum-fourier-transform/index.md
new file mode 100644
index 0000000..1ebf1d1
--- /dev/null
+++ b/source/know/concept/quantum-fourier-transform/index.md
@@ -0,0 +1,198 @@
+---
+title: "Quantum Fourier transform"
+date: 2021-05-01
+categories:
+- Algorithms
+- Quantum information
+layout: "concept"
+---
+
+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( 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%">
+</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%">
+</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.
+