From 075683cdf4588fe16f41d9f7b46b9720b42b2553 Mon Sep 17 00:00:00 2001
From: Prefetch
Date: Wed, 17 Jul 2024 10:01:43 +0200
Subject: Improve knowledge base

---
 source/know/concept/simons-algorithm/index.md | 46 ++++++++++++++++-----------
 1 file changed, 28 insertions(+), 18 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 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.
-- 
cgit v1.2.3