Expand knowledge base

6 files changed, 301 insertions, 2 deletions

diff --git a/content/know/concept/bernstein-vazirani-algorithm/bernstein-vazirani-circuit.png b/content/know/concept/bernstein-vazirani-algorithm/bernstein-vazirani-circuit.png
new file mode 100644
index 0000000..fdeabf5
--- /dev/null
+++ b/content/know/concept/bernstein-vazirani-algorithm/bernstein-vazirani-circuit.png
diff --git a/content/know/concept/bernstein-vazirani-algorithm/index.pdc b/content/know/concept/bernstein-vazirani-algorithm/index.pdc
new file mode 100644
index 0000000..22de51a
--- /dev/null
+++ b/content/know/concept/bernstein-vazirani-algorithm/index.pdc
@@ -0,0 +1,107 @@
+---
+title: "Bernstein-Vazirani algorithm"
+firstLetter: "B"
+publishDate: 2021-05-01
+categories:
+- Quantum information
+- Algorithms
+
+date: 2021-04-13T10:28:44+02:00
+draft: false
+markup: pandoc
+---
+
+# Bernstein-Vazirani algorithm
+
+In quantum information,
+the **Bernstein-Vazirani algorithm** proves
+the supremacy of quantum computers
+over classical deterministic or probabilistic computers.
+It is extremely similar to the
+[Deutsch-Jozsa algorithm](/know/concept/deutsch-jozsa-algorithm/),
+and even uses the same circuit.
+
+It solves a very artificial problem:
+we are given a "black box" function $f(x)$
+that takes an $N$-bit $x$ and returns a single bit,
+which we are promised is the lowest bit of the bitwise dot product
+of $x$ with an unknown $N$-bit string $s$:
+
+$$\begin{aligned}
+    f(x)
+    = s \cdot x \:\:(\bmod 2)
+    = (s_1 x_1 + s_2 x_2 + \:...\: + s_N x_N) \:\:(\bmod 2)
+\end{aligned}$$
+
+The goal is to find $s$.
+To solve this problem,
+a classical computer would need to call $f(x)$ exactly $N$ times
+with $x = 2^n$  for $n \in \{ 0, ..., N \!-\! 1\}$.
+However, the Bernstein-Vazirani algorithm
+allows a quantum computer to do it with only a single query.
+It uses the following circuit:
+
+<a href="bernstein-vazirani-circuit.png">
+<img src="bernstein-vazirani-circuit.png" style="width:52%;display:block;margin:auto;">
+</a>
+
+Where $U_f$ is a phase oracle,
+whose action is defined as follows,
+where $\ket{x} = \ket{x_1} \cdots \ket{x_N}$:
+
+$$\begin{aligned}
+    \ket{x}
+    \quad \to \boxed{U_f} \to \quad
+    (-1)^{f(x)} \ket{x}
+    = (-1)^{s \cdot x} \ket{x}
+\end{aligned}$$
+
+That is, it introduces a phase flip based on the value of $f(x)$.
+For an example implementation of such an oracle,
+see the Deutsch-Jozsa algorithm:
+its circuit is identical to this one,
+but describes $U_f$ in a different (but equivalent) way.
+
+Starting from the state $\ket{0}^{\otimes N}$,
+applying the [Hadamard gate](/know/concept/hadamard-gate/) $H$
+to all qubits yields:
+
+$$\begin{aligned}
+    \ket{0}^{\otimes N}
+    \quad \to \boxed{H^{\otimes N}} \to \quad
+    \ket{+}^{\otimes N}
+    = \frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} \ket{x}
+\end{aligned}$$
+
+This is an equal superposition of all candidates $\ket{x}$,
+which we feed to the oracle:
+
+$$\begin{aligned}
+    \frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} \ket{x}
+    \quad \to \boxed{U_f} \to \quad
+    \frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} (-1)^{s \cdot x} \ket{x}
+\end{aligned}$$
+
+Then, thanks to the definition of the Hadamard transform,
+a final set of $H$-gates leads us to:
+
+$$\begin{aligned}
+    \frac{1}{\sqrt{2^N}} \sum_{x = 0}^{2^N - 1} (-1)^{s \cdot x} \ket{x}
+    \quad \to \boxed{H^{\otimes N}} \to \quad
+    \ket{s}
+    = \ket{s_1} \cdots \ket{s_N}
+\end{aligned}$$
+
+Which, upon measurement, gives us the desired binary representation of $s$.
+For comparison, the Deutsch-Jozsa algorithm only cares whether $s = 0$ or $s \neq 0$,
+whereas this algorithm is interested in the exact value of $s$.
+
+
+
+## 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/deutsch-jozsa-algorithm/deutsch-jozsa-circuit.png b/content/know/concept/deutsch-jozsa-algorithm/deutsch-jozsa-circuit.png
index a43ae6a..70bdf3e 100644
--- a/content/know/concept/deutsch-jozsa-algorithm/deutsch-jozsa-circuit.png
+++ b/content/know/concept/deutsch-jozsa-algorithm/deutsch-jozsa-circuit.png
diff --git a/content/know/concept/deutsch-jozsa-algorithm/index.pdc b/content/know/concept/deutsch-jozsa-algorithm/index.pdc
index a891dd1..a3acaf4 100644
--- a/content/know/concept/deutsch-jozsa-algorithm/index.pdc
+++ b/content/know/concept/deutsch-jozsa-algorithm/index.pdc
@@ -46,7 +46,7 @@ To do this, we use the following quantum circuit,
 where $U_f$ is the oracle we query:
 
 <a href="deutsch-circuit.png">
-<img src="deutsch-circuit.png" style="width:50%;display:block;margin:auto;">
+<img src="deutsch-circuit.png" style="width:48%;display:block;margin:auto;">
 </a>
 
 Due to unitarity constraints,
@@ -147,7 +147,7 @@ other possibilities are assumed to be impossible.
 This algorithm is then implemented by the following quantum circuit:
 
 <a href="deutsch-jozsa-circuit.png">
-<img src="deutsch-jozsa-circuit.png" style="width:50%;display:block;margin:auto;">
+<img src="deutsch-jozsa-circuit.png" style="width:52%;display:block;margin:auto;">
 </a>
 
 There are $N$ qubits in initial state $\ket{0}$, and one in $\ket{1}$.
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