# Simon's Algorithm

### 問題

和Bernstein-Vazarni相似，Simon也是和字串相關的問題，一樣給訂一個函數：

$$
f:\left{0,1\right}^n\to\left{0,1\right}^n
$$

這次，我們保證存在字串 $$s$$ ，當 $$s$$ 為非 $$0$$ 字串，並且

$$
f(x)=f(y)
$$

若且唯若

$$
x=y\oplus s
$$

請求出 $$s$$ 

舉個例子，免得我敘述太差，如果 $$s=110$$ 

$$
\begin{aligned}
\&f(000)=5 \ \ \ \ f(100)=1\\
\&f(001)=4 \ \ \ \ f(101)=0\\
\&f(010)=1 \ \ \ \  f(110)=5\\
\&f(011)=0\ \ \ \ f(111)=4
\end{aligned}
\tag{1}
$$

$$000$$ 和 $$110$$ 經過 $$f$$ 後的質會相同，因為 $$000 = s \oplus110$$ ​。

### 量子算法(Simon's algorithm)

![Simon's algorithm ](https://3865886813-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LpMm0E0vvjg46Qr8IPS%2F-LprozThqpvVphJ9ZKeY%2F-Lps0kQHhMYsQHx52Tb-%2Fimage.png?alt=media\&token=a5a89aea-949e-4f87-90d0-b9b0d5ce735e)

先準備兩個register，第一個經過Hadamard gate，並且同時query $$f$$ ，並且馬上觀測第二個register，再觀察完register 之後，第一個 register 只會剩下只有兩種可能 :

$$
\frac{1}{\sqrt{2^n}}\sum\_{x\in\left{0,1\right}^n}|x\rangle|f(x)\rangle\rightarrow \frac{|i\rangle+|j\rangle}{\sqrt{2}},where\ i \oplus j= s\tag{2}
$$

或許上述可能有些難懂，我們以(1)作為延伸，來舉個例子 :

一開始的兩個register :

$$
|000\rangle|000\rangle
$$

register 1 經過Hadamard gate， 成為以下 :

$$
|000\rangle|000\rangle\rightarrow \frac{1}{\sqrt{8}}(|000\rangle+|001\rangle+|010\rangle+|011\rangle+|100\rangle+|101\rangle+|110\rangle+|111\rangle)|000\rangle
$$

同時query兩個register，我們可以得到以下 :

$$
\frac{1}{\sqrt{8}}\sum\_{x\in\left{0,1\right}^{3}}|x\rangle|000\rangle \xrightarrow{f}{}\frac{1}{\sqrt{8}}\sum\_{x\in\left{0,1\right}^{3}}|x\rangle|f(x)\rangle
$$

 將(2)展開，也就是以下幾種可能的量子態 :

$$
\frac{1}{\sqrt{8}}(|000\rangle|5\rangle+|001\rangle|4\rangle+|010\rangle|1\rangle+|011\rangle|0\rangle+|100\rangle|1\rangle+|101\rangle|0\rangle+|110\rangle|5\rangle+|111\rangle|4\rangle)
$$

所以，如果我們立刻觀測第二個register，觀測到 $$|5\rangle$$ ，那我們就立刻能知道register 1 中只有可能是 $$|000\rangle$$ 或是 $$|110\rangle$$ 兩種可能。

舉例完畢，接下來，讓register 1再經過一次Hadamard gate :

$$
\frac{H^{\oplus n}|i\rangle+H^{\oplus n}|j\rangle}{\sqrt{2}}\rightarrow\frac{1}{\sqrt{2}}(\frac{1}{\sqrt{2^n}}(\sum\_{z\in{\left{0,1\right}^n}}(-1)^{i\cdot z}|z\rangle+\sum\_{z\in{\left{0,1\right}^n}}(-1)^{j\cdot z}|z\rangle))\tag{3}
$$

將(3)化簡

$$
\frac{1}{\sqrt{2^{n+1}}}\sum\_{z\in{\left{0,1\right}^n}}\[(-1)^{i\cdot z}+(-1)^{j\cdot z}]|z\rangle
$$

再化簡

$$
\frac{1}{\sqrt{2^{n+1}}}\sum\_{z\in{\left{0,1\right}^n}}(-1)^{i\cdot z}(1-1^{s\oplus z})|z\rangle
$$

如果 $$s\oplus z=1$$ ，則整個等於 $$0$$ 不合，所以 $$s \oplus z = 0$$ ，或許我們無法直接得到s，但是藉由高斯消去法能在 $$O(n)$$ 中找到 $$s$$ ，因此算法的時間複雜度是 :

$$
O(n)
$$