From 16555851b6514a736c5c9d8e73de7da7fc9b6288 Mon Sep 17 00:00:00 2001 From: Prefetch Date: Thu, 20 Oct 2022 18:25:31 +0200 Subject: Migrate from 'jekyll-katex' to 'kramdown-math-sskatex' --- source/know/concept/simons-algorithm/index.md | 96 +++++++++++++-------------- 1 file changed, 48 insertions(+), 48 deletions(-) (limited to 'source/know/concept/simons-algorithm') diff --git a/source/know/concept/simons-algorithm/index.md b/source/know/concept/simons-algorithm/index.md index fef10b9..5502837 100644 --- a/source/know/concept/simons-algorithm/index.md +++ b/source/know/concept/simons-algorithm/index.md @@ -19,10 +19,10 @@ 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$: +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) @@ -31,24 +31,24 @@ $$\begin{aligned} 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$. +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. +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$. +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 +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, +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: @@ -56,8 +56,8 @@ It uses the following circuit: -The XOR oracle $U_f$ implements $f$, -and has the following action for $n$-bit $a$ and $b$: +The XOR oracle $$U_f$$ implements $$f$$, +and has the following action for $$n$$-bit $$a$$ and $$b$$: $$\begin{aligned} \Ket{a} \Ket{b} @@ -65,9 +65,9 @@ $$\begin{aligned} \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: +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} @@ -76,10 +76,10 @@ $$\begin{aligned} = \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$: +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} @@ -87,10 +87,10 @@ $$\begin{aligned} \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, +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: +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)} @@ -101,10 +101,10 @@ $$\begin{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$: +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 @@ -114,18 +114,18 @@ $$\begin{alignedat}{2} &&\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 = 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: +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, +Since $$x_2 = s \oplus x_1$$ by definition, we can rewrite this as follows: $$\begin{aligned} @@ -134,21 +134,21 @@ $$\begin{aligned} \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. +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: +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$, +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} @@ -162,10 +162,10 @@ $$\begin{aligned} \end{aligned}$$ This can be solved efficiently by a classical computer. -In the best-case scenario, all those $y$-values would be linearly independent +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)$. +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, -- cgit v1.2.3