diff options
Diffstat (limited to 'source/know/concept/simons-algorithm/index.md')
| -rw-r--r-- | source/know/concept/simons-algorithm/index.md | 46 |
1 files changed, 28 insertions, 18 deletions
diff --git a/source/know/concept/simons-algorithm/index.md b/source/know/concept/simons-algorithm/index.md index 63bb808..6404ab0 100644 --- a/source/know/concept/simons-algorithm/index.md +++ b/source/know/concept/simons-algorithm/index.md @@ -16,7 +16,7 @@ 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. +but nevertheless Simon's algorithm is an important milestone. Simon's problem is this: we are given a "black box" function $$f(x)$$ @@ -27,8 +27,9 @@ 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 + \qquad \Leftrightarrow \qquad + x_2 + = s \oplus x_1 \end{aligned}$$ In other words, regardless of what $$f(x)$$ does behind the scenes, @@ -94,7 +95,8 @@ 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)} + &\frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} + \bigg( \frac{1}{\sqrt{2^n}} \sum_{y = 0}^{2^n - 1} (-1)^{x \cdot y} \Ket{y} \bigg) \Ket{f(x)} \end{aligned}$$ Next, we measure all qubits. @@ -106,42 +108,47 @@ 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)} + &&\bigg( \frac{1}{\sqrt{2^{n}}} \sum_{y = 0}^{2^n - 1} (-1)^{x_1 \cdot y} \Ket{y} \bigg) \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)} + &&\bigg( \frac{1}{\sqrt{2^n}} \sum_{y = 0}^{2^n - 1} \frac{1}{\sqrt{2}} \Big( (-1)^{x_1 \cdot y} + (-1)^{x_2 \cdot y} \Big) \Ket{y} \bigg) \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, +If $$s = 0$$, we get an equal 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, +If $$s \neq 0$$, we get an "extra superposition", +since $$x_1 \neq x_2$$ but both are candidate inputs. +This is a more interesting situation, because we can only measure $$y$$-values where: $$\begin{aligned} - (-1)^{x_1 \cdot y} + (-1)^{x_2 \cdot y} \neq 0 + 0 + \neq (-1)^{x_1 \cdot y} + (-1)^{x_2 \cdot y} \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} + 0 + \neq (-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. +Clearly, this 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: +measuring the first $$n$$ qubits gives a $$y$$-value satisfying: $$\begin{aligned} - s \cdot y = 0 \:\:(\bmod 2) + s \cdot y + = 0 \:\bmod 2 \end{aligned}$$ This tells us something about $$s$$, albeit not much. @@ -150,13 +157,16 @@ 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_1 + &= 0 \:\bmod 2 \\ - s \cdot y_2 &= 0 \:\:(\bmod 2) + s \cdot y_2 + &= 0 \:\bmod 2 \\ &\:\:\vdots \\ - s \cdot y_N &= 0 \:\:(\bmod 2) + s \cdot y_N + &= 0 \:\bmod 2 \end{aligned}$$ This can be solved efficiently by a classical computer. |