Expand knowledge base

2 files changed, 192 insertions, 0 deletions

diff --git a/content/know/concept/simons-algorithm/index.pdc b/content/know/concept/simons-algorithm/index.pdc
new file mode 100644
index 0000000..a65b3f0
--- /dev/null
+++ b/content/know/concept/simons-algorithm/index.pdc
@@ -0,0 +1,192 @@
+---
+title: "Simon's algorithm"
+firstLetter: "S"
+publishDate: 2021-05-01
+categories:
+- Quantum information
+- Algorithms
+
+date: 2021-04-13T10:29:02+02:00
+draft: false
+markup: pandoc
+---
+
+# Simon's algorithm
+
+**Simon's algorithm** was the first proof that quantum computers
+are able to solve some problems *exponentially* faster
+than classical computers.
+In the same spirit as
+the [Deutsch-Jozsa algorithm](/know/concept/deutsch-jozsa-algorithm/)
+and the [Bernstein-Vazirani algorithm](/know/concept/bernstein-vazirani-algorithm/),
+the problem it solves, known as **Simon's problem**,
+is of no practical use,
+but nevertheless Simon's algorithm is an important landmark.
+
+Simon's problem is this:
+we are given a "black box" function $f(x)$
+that takes an $n$-bit input $x$
+and returns an $n$-bit output.
+We are promised that there exists an $s$ such that for all $x_1$ and $x_2$:
+
+$$\begin{aligned}
+    f(x_1)
+    = f(x_2)
+    \quad \Leftrightarrow \quad
+    x_2 = s \oplus x_1
+\end{aligned}$$
+
+In other words, regardless of what $f(x)$ does behind the scenes,
+its output is the same for inputs $x_1$ and $x_2$
+if and only if $x_2 = s \oplus x_1$,
+or, equivalently, $x_1 = s \oplus x_2$.
+
+The goal is to find the $n$-bit number $s$, using as few calls to $f$ as possible.
+There are two cases:
+if $s = 0$, then $f$ is one-to-one, since $x_2 = 0 \oplus x_1 = x_1$.
+Otherwise, if $s \neq 0$, then $f$ is two-to-one by definition:
+for every $x_1$ there exists exactly one $x_2$ such that $x_2 = s \oplus x_1$.
+
+A classical computer solves this by randomly guessing inputs,
+until it finds two that give the same output,
+and then $s = x_1 \oplus x_2$.
+For $n$-bit numbers, this takes $\mathcal{O}(\sqrt{2^n})$ guesses
+(the square root is due to the birthday paradox).
+
+A quantum computer needs to query $f$ only $\mathcal{O}(n)$ times,
+although the exact number varies due to the algorithm's probabilistic nature.
+It uses the following circuit:
+
+<a href="simons-circuit.png" style="width:52%;display:block;margin:auto;">
+<img src="simons-circuit.png">
+</a>
+
+The XOR oracle $U_f$ implements $f$,
+and has the following action for $n$-bit $a$ and $b$:
+
+$$\begin{aligned}
+    \ket{a} \ket{b}
+    \quad \to \boxed{U_f} \to \quad
+    \ket{a} \ket{b \oplus f(a)}
+\end{aligned}$$
+
+Starting from the state $\ket{0}^{\otimes 2 n}$,
+we apply the [Hadamard gate](/know/concept/quantum-gate/) $H$
+to each of the first $n$ qubits:
+
+$$\begin{aligned}
+    \ket{0}^{\otimes n} \ket{0}^{\otimes n}
+    \quad \to \boxed{H^{\otimes n}} \to \quad
+    \ket{+}^{\otimes n} \ket{0}^{\otimes n}
+    = \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \ket{x} \ket{0}^{\otimes n}
+\end{aligned}$$
+
+Where $\ket{x}$ is shorthand for $\ket{x}_1 \cdots \ket{x}_n$.
+In other words, we now have an equal superposition of all possible inputs $x$,
+with a constant $\ket{0}^{\otimes n}$ beside it.
+We give this to the oracle $U_f$:
+
+$$\begin{aligned}
+    \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \ket{x} \ket{0}^{\otimes n}
+    \quad \to \boxed{U_f} \to \quad
+    \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \ket{x} \ket{f(x)}
+\end{aligned}$$
+
+Then we apply $H^{\otimes n}$ to the first $n$ qubits again,
+which, thanks to the definition of the Hadamard transform,
+yields the following,
+where $x \cdot y$ is the bitwise dot product:
+
+$$\begin{aligned}
+    \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \ket{x} \ket{f(x)}
+    \quad \to \boxed{H^{\otimes n}} \to \quad
+    &\frac{1}{2^n} \sum_{x = 0}^{2^n - 1} \bigg( \sum_{y = 0}^{2^n - 1} (-1)^{x \cdot y} \ket{y} \bigg) \ket{f(x)}
+%    \\
+%    = &\sum_{y = 0}^{2^n - 1} \ket{y} \bigg( \frac{1}{2^n} \sum_{x = 0}^{2^n - 1} (-1)^{x \cdot y} \ket{f(x)} \bigg)
+\end{aligned}$$
+
+
+Next, we measure all qubits.
+The order in which we do this does not matter,
+but, for clarity, let us measure the last $n$ qubits first,
+yielding $\ket{f(x_1)}$ for some $x_1$.
+Doing this leaves the $2n$ qubits in the following state,
+where $f(x_1) = f(x_2)$ and $x_2 = s \oplus x_1$:
+
+$$\begin{alignedat}{2}
+    &\mathrm{if} \: s = 0: \qquad
+    &&\frac{1}{\sqrt{2^{n}}} \sum_{y = 0}^{2^n - 1} (-1)^{x_1 \cdot y} \ket{y} \ket{f(x_1)}
+    \\
+    &\mathrm{if} \: s \neq 0: \qquad
+    &&\frac{1}{\sqrt{2^{n+1}}} \sum_{y = 0}^{2^n - 1} \Big( (-1)^{x_1 \cdot y} + (-1)^{x_2 \cdot y} \Big) \ket{y} \ket{f(x_1)}
+\end{alignedat}$$
+
+If $s = 0$, we get an equiprobable superposition of all $y$.
+So, when we measure the first $n$ qubits, the result is a uniformly random number,
+regardless of the phase $(-1)^{x_1 \cdot y}$.
+
+If $s \neq 0$, the situation is more interesting,
+because we can only measure $y$-values where:
+
+$$\begin{aligned}
+    (-1)^{x_1 \cdot y} + (-1)^{x_2 \cdot y} \neq 0
+\end{aligned}$$
+
+Since $x_2 = s \oplus x_1$ by definition,
+we can rewrite this as follows:
+
+$$\begin{aligned}
+    (-1)^{x_1 \cdot y} + (-1)^{x_1 \cdot y \oplus s \cdot y}
+    = (-1)^{x_1 \cdot y} + (-1)^{x_1 \cdot y} (-1)^{s \cdot y}
+    \neq 0
+\end{aligned}$$
+
+Clearly, the expression can only be nonzero if $s \cdot y$ is even.
+In other words, when we measure the first $n$ qubits,
+we get a random $y$-value,
+for which $s \cdot y$ is guaranteed to be even.
+
+In both cases $s = 0$ and $s \neq 0$,
+we measure a $y$-value that satisfies the equation:
+
+$$\begin{aligned}
+    s \cdot y = 0 \:\:(\bmod 2)
+\end{aligned}$$
+
+This tells us something about $s$, albeit not much.
+But if we run Simon's algorithm $N$ times,
+we get various $y$-values $y_1, ..., y_N$,
+from which we can build a system of linear equations:
+
+$$\begin{aligned}
+    s \cdot y_1 &= 0 \:\:(\bmod 2)
+    \\
+    s \cdot y_2 &= 0 \:\:(\bmod 2)
+    \\
+    &\:\:\vdots
+    \\
+    s \cdot y_N &= 0 \:\:(\bmod 2)
+\end{aligned}$$
+
+This can be solved efficiently by a classical computer.
+In the best-case scenario, all those $y$-values would be linearly independent
+(when regarded as vectors of bits),
+in which case only $N = n - 1$ equations would be necessary.
+Simon's algorithm is therefore $\mathcal{O}(n)$.
+
+It may feel like "cheating" to use a classical computer at the end.
+Remember that the point of this algorithm is to limit the number of oracle queries,
+which we did successfully.
+Querying an oracle might be a very expensive operation,
+so that is a big improvement!
+That said, Simon's algorithm currently has no known practical uses.
+
+
+
+## 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/simons-algorithm/simons-circuit.png b/content/know/concept/simons-algorithm/simons-circuit.png
new file mode 100644
index 0000000..8652ffe
--- /dev/null
+++ b/content/know/concept/simons-algorithm/simons-circuit.png