Simon's Algorithm

學習完Bernstein-Vazarni後，接下來學習知名且相似的Simon's algorithm

問題

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

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

這次，我們保證存在字串 ss ，當 ss 為非 00 字串，並且

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

若且唯若

x=y⊕sx=y\oplus s

請求出 ss

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

f(000)=5    f(100)=1f(001)=4    f(101)=0f(010)=1    f(110)=5f(011)=0    f(111)=4(1)\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}

000000 和 110110 經過 ff 後的質會相同，因為 000=s⊕110000 = s \oplus110 ​。

量子算法(Simon's algorithm)

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

12n∑x∈{0,1}n∣x⟩∣f(x)⟩→∣i⟩+∣j⟩2,where i⊕j=s(2)\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⟩∣000⟩|000\rangle|000\rangle

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

∣000⟩∣000⟩→18(∣000⟩+∣001⟩+∣010⟩+∣011⟩+∣100⟩+∣101⟩+∣110⟩+∣111⟩)∣000⟩|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，我們可以得到以下 :

18∑x∈{0,1}3∣x⟩∣000⟩→f18∑x∈{0,1}3∣x⟩∣f(x)⟩\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)展開，也就是以下幾種可能的量子態 :

18(∣000⟩∣5⟩+∣001⟩∣4⟩+∣010⟩∣1⟩+∣011⟩∣0⟩+∣100⟩∣1⟩+∣101⟩∣0⟩+∣110⟩∣5⟩+∣111⟩∣4⟩)\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⟩|5\rangle ，那我們就立刻能知道register 1 中只有可能是 ∣000⟩|000\rangle 或是 ∣110⟩|110\rangle 兩種可能。

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

H⊕n∣i⟩+H⊕n∣j⟩2→12(12n(∑z∈{0,1}n(−1)i⋅z∣z⟩+∑z∈{0,1}n(−1)j⋅z∣z⟩))(3)\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)化簡

12n+1∑z∈{0,1}n[(−1)i⋅z+(−1)j⋅z]∣z⟩\frac{1}{\sqrt{2^{n+1}}}\sum_{z\in{\left\{0,1\right\}^n}}[(-1)^{i\cdot z}+(-1)^{j\cdot z}]|z\rangle

再化簡

12n+1∑z∈{0,1}n(−1)i⋅z(1−1s⊕z)∣z⟩\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⊕z=1s\oplus z=1 ，則整個等於 00 不合，所以 s⊕z=0s \oplus z = 0 ，或許我們無法直接得到s，但是藉由高斯消去法能在 O(n)O(n) 中找到 ss ，因此算法的時間複雜度是 :

O(n)O(n)
PreviousBernstein-VazaraniNextGover's algorithm

Last updated

Was this helpful?