diff options
author | Prefetch | 2021-05-01 17:23:45 +0200 |
---|---|---|
committer | Prefetch | 2021-05-01 17:23:45 +0200 |
commit | e394d6c45bcc1e5650bcbeff5a3246316f6842f0 (patch) | |
tree | 28e00f180c222cb316894e25030609862c73aadf | |
parent | 8f883023e6354648727479aec029f418b30ef2dc (diff) |
Expand knowledge base
-rw-r--r-- | content/know/concept/bernstein-vazirani-algorithm/bernstein-vazirani-circuit.png | bin | 0 -> 20485 bytes | |||
-rw-r--r-- | content/know/concept/bernstein-vazirani-algorithm/index.pdc | 107 | ||||
-rw-r--r-- | content/know/concept/deutsch-jozsa-algorithm/deutsch-jozsa-circuit.png | bin | 18613 -> 19180 bytes | |||
-rw-r--r-- | content/know/concept/deutsch-jozsa-algorithm/index.pdc | 4 | ||||
-rw-r--r-- | content/know/concept/simons-algorithm/index.pdc | 192 | ||||
-rw-r--r-- | content/know/concept/simons-algorithm/simons-circuit.png | bin | 0 -> 33688 bytes | |||
-rw-r--r-- | sources/know/concept/bernstein-vazirani-algorithm/circuit.tex | 37 | ||||
-rw-r--r-- | sources/know/concept/deutsch-jozsa-algorithm/circuit.tex | 2 | ||||
-rw-r--r-- | sources/know/concept/simons-algorithm/circuit.tex | 51 |
9 files changed, 390 insertions, 3 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 Binary files differnew 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 Binary files differindex 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 Binary files differnew file mode 100644 index 0000000..8652ffe --- /dev/null +++ b/content/know/concept/simons-algorithm/simons-circuit.png diff --git a/sources/know/concept/bernstein-vazirani-algorithm/circuit.tex b/sources/know/concept/bernstein-vazirani-algorithm/circuit.tex new file mode 100644 index 0000000..95bae6b --- /dev/null +++ b/sources/know/concept/bernstein-vazirani-algorithm/circuit.tex @@ -0,0 +1,37 @@ +\documentclass[11pt]{article} +\usepackage[utf8]{inputenc} +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{physics} +\usepackage{yquant} + + +\begin{document} + +\section{Spacer} + +\yquantdefinebox{dots}[inner sep=0pt]{$\vdots$} +\begin{tikzpicture} + \begin{yquant}[operator/separation=5mm] + qubit {$\ket{0}_1$} a1; + qubit {$\ket{0}_2$} a2; + nobit ellipsis; + qubit {$\ket{0}_{\!N\!}$} aN; + + h a1; + h a2; + dots ellipsis; + h aN; + box {$U_f$} (a1, a2, ellipsis, aN); + h a1; + h a2; + dots ellipsis; + h aN; + measure a1; + measure a2; + dots ellipsis; + measure aN; + \end{yquant} +\end{tikzpicture} + +\end{document} diff --git a/sources/know/concept/deutsch-jozsa-algorithm/circuit.tex b/sources/know/concept/deutsch-jozsa-algorithm/circuit.tex index ad0dff3..6c82e9f 100644 --- a/sources/know/concept/deutsch-jozsa-algorithm/circuit.tex +++ b/sources/know/concept/deutsch-jozsa-algorithm/circuit.tex @@ -25,7 +25,7 @@ \section{Spacer} -\yquantdefinebox{dots}[inner sep=0pt]{$\dots$} +\yquantdefinebox{dots}[inner sep=0pt]{$\vdots$} \begin{tikzpicture} \begin{yquant}[operator/separation=5mm] qubit {$\ket{0}$} a[2]; diff --git a/sources/know/concept/simons-algorithm/circuit.tex b/sources/know/concept/simons-algorithm/circuit.tex new file mode 100644 index 0000000..54583ca --- /dev/null +++ b/sources/know/concept/simons-algorithm/circuit.tex @@ -0,0 +1,51 @@ +\documentclass[11pt]{article} +\usepackage[utf8]{inputenc} +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{physics} +\usepackage{yquant} + + +\begin{document} + +\section{Spacer} + +\yquantdefinebox{dots}[inner sep=0pt]{$\vdots$} +\begin{tikzpicture} + \begin{yquant}[operator/separation=5mm, register/separation=0mm] + qubit {$\ket{0}_1$} a1; + qubit {$\ket{0}_2$} a2; + nobit adots; + qubit {$\ket{0}_{n\!}$} aN; + + nobit sep; + + qubit {$\ket{0}_1$} b1; + qubit {$\ket{0}_2$} b2; + nobit bdots; + qubit {$\ket{0}_{n\!}$} bN; + + h a1; + h a2; + dots adots; + h aN; + dots bdots; + box {$U_f$} (a1, a2, adots, aN, sep, b1, b2, bdots, bN); + h a1; + h a2; + dots adots; + h aN; + dots bdots; + align a1, a2, adots, aN, b1, b2, bdots, bN; + measure a1; + measure a2; + dots adots; + measure aN; + measure b1; + measure b2; + dots bdots; + measure bN; + \end{yquant} +\end{tikzpicture} + +\end{document} |