Simon's Algorithm

學習完Bernstein-Vazarni後，接下來學習知名且相似的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

先準備兩個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)$$