Expand knowledge base

1 files changed, 107 insertions, 0 deletions

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.