diff options
Diffstat (limited to 'source/know/concept/bernstein-vazirani-algorithm')
| -rw-r--r-- | source/know/concept/bernstein-vazirani-algorithm/index.md | 34 |
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$$. |