summaryrefslogtreecommitdiff
path: root/source/know/concept/bernstein-vazirani-algorithm
diff options
context:
space:
mode:
authorPrefetch2022-10-20 18:25:31 +0200
committerPrefetch2022-10-20 18:25:31 +0200
commit16555851b6514a736c5c9d8e73de7da7fc9b6288 (patch)
tree76b8bfd30f8941d0d85365990bcdbc5d0643cabc /source/know/concept/bernstein-vazirani-algorithm
parente5b9bce79b68a68ddd2e51daa16d2fea73b84fdb (diff)
Migrate from 'jekyll-katex' to 'kramdown-math-sskatex'
Diffstat (limited to 'source/know/concept/bernstein-vazirani-algorithm')
-rw-r--r--source/know/concept/bernstein-vazirani-algorithm/index.md34
1 files changed, 17 insertions, 17 deletions
diff --git a/source/know/concept/bernstein-vazirani-algorithm/index.md b/source/know/concept/bernstein-vazirani-algorithm/index.md
index af49841..f91c0ba 100644
--- a/source/know/concept/bernstein-vazirani-algorithm/index.md
+++ b/source/know/concept/bernstein-vazirani-algorithm/index.md
@@ -17,10 +17,10 @@ It is extremely similar to the
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,
+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$:
+of $$x$$ with an unknown $$N$$-bit string $$s$$:
$$\begin{aligned}
f(x)
@@ -28,10 +28,10 @@ $$\begin{aligned}
= (s_1 x_1 + s_2 x_2 + \:...\: + s_N x_N) \:\:(\bmod \: 2)
\end{aligned}$$
-The goal is to find $s$.
+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\}$.
+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:
@@ -40,9 +40,9 @@ It uses the following circuit:
<img src="bernstein-vazirani-circuit.png" style="width:52%">
</a>
-Where $U_f$ is a phase oracle,
+Where $$U_f$$ is a phase oracle,
whose action is defined as follows,
-where $\Ket{x} = \Ket{x_1} \cdots \Ket{x_N}$:
+where $$\Ket{x} = \Ket{x_1} \cdots \Ket{x_N}$$:
$$\begin{aligned}
\Ket{x}
@@ -51,14 +51,14 @@ $$\begin{aligned}
= (-1)^{s \cdot x} \Ket{x}
\end{aligned}$$
-That is, it introduces a phase flip based on the value of $f(x)$.
+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.
+but describes $$U_f$$ in a different (but equivalent) way.
-Starting from the state $\Ket{0}^{\otimes N}$,
-applying the [Hadamard gate](/know/concept/quantum-gate/) $H$
+Starting from the state $$\Ket{0}^{\otimes N}$$,
+applying the [Hadamard gate](/know/concept/quantum-gate/) $$H$$
to all qubits yields:
$$\begin{aligned}
@@ -68,7 +68,7 @@ $$\begin{aligned}
= \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}$,
+This is an equal superposition of all candidates $$\Ket{x}$$,
which we feed to the oracle:
$$\begin{aligned}
@@ -78,7 +78,7 @@ $$\begin{aligned}
\end{aligned}$$
Then, thanks to the definition of the Hadamard transform,
-a final set of $H$-gates leads us to:
+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}
@@ -87,9 +87,9 @@ $$\begin{aligned}
= \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$.
+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$$.