📗
白話文量子演算法
  • 量子世界的基本數學
  • Deutsch-Jozsa
    • oracle and query
    • 經典 vs Deutsh-Jozsa
  • Bernstein-Vazarani
  • Simon's Algorithm
  • Gover's algorithm
    • 經典 vs Grover
    • 演算法解釋
    • 演算法解釋 2
  • 參考資料
Powered by GitBook
On this page
  • 問題
  • 量子算法(Simon's algorithm)

Was this helpful?

Simon's Algorithm

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

PreviousBernstein-VazaraniNextGover's algorithm

Last updated 5 years ago

Was this helpful?

問題

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

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

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

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

若且唯若

x=y⊕sx=y\oplus sx=y⊕s

請求出 sss

舉個例子，免得我敘述太差，如果 s=110s=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}​f(000)=5    f(100)=1f(001)=4    f(101)=0f(010)=1    f(110)=5f(011)=0    f(111)=4​(1)

量子算法(Simon's algorithm)

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

一開始的兩個register :

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

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

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

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

將(3)化簡

再化簡

000000000 和 110110110 經過 fff 後的質會相同，因為 000=s⊕110000 = s \oplus110000=s⊕110 ​。

先準備兩個register，第一個經過Hadamard gate，並且同時query fff ，並且馬上觀測第二個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}2n​1​x∈{0,1}n∑​∣x⟩∣f(x)⟩→2​∣i⟩+∣j⟩​,where i⊕j=s(2)
∣000⟩∣000⟩|000\rangle|000\rangle∣000⟩∣000⟩
∣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∣000⟩∣000⟩→8​1​(∣000⟩+∣001⟩+∣010⟩+∣011⟩+∣100⟩+∣101⟩+∣110⟩+∣111⟩)∣000⟩
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 8​1​x∈{0,1}3∑​∣x⟩∣000⟩f​8​1​x∈{0,1}3∑​∣x⟩∣f(x)⟩
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)8​1​(∣000⟩∣5⟩+∣001⟩∣4⟩+∣010⟩∣1⟩+∣011⟩∣0⟩+∣100⟩∣1⟩+∣101⟩∣0⟩+∣110⟩∣5⟩+∣111⟩∣4⟩)

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

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}2​H⊕n∣i⟩+H⊕n∣j⟩​→2​1​(2n​1​(z∈{0,1}n∑​(−1)i⋅z∣z⟩+z∈{0,1}n∑​(−1)j⋅z∣z⟩))(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\rangle2n+1​1​z∈{0,1}n∑​[(−1)i⋅z+(−1)j⋅z]∣z⟩
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\rangle2n+1​1​z∈{0,1}n∑​(−1)i⋅z(1−1s⊕z)∣z⟩

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

O(n)O(n)O(n)
Simon's algorithm