Peter Shor
在 1994 年，丹尼爾·西蒙（Daniel Simon）提出了一個看似古怪的數學問題。當時沒人想到，這個關於尋找隱藏字串 s 的演算法，竟成為後來震撼全球資安界的 Shor 演算法 最重要的靈感來源。
要看懂 Simon 演算法，我們必須先回答兩個最根本的疑問：為什麼要找 s？這個 s 與現實世界的加密有什麼關係？
什麼是s？ 位元世界的秘密週期
在古典電腦的二進位運算中，加法就是 ⊕（XOR）。
如果一個函數 f(x) 滿足：對於不同的輸入 x 與 y，只要它們噴出的結果相同（f(x) = f(y)），就代表這兩個輸入之間存在一個固定的位元關係：
x ⊕ y = s
這意味著 f(x) = f( x ⊕ s)。在數學視角下，這就是位元世界裡的週期函數。這把隱藏的鑰匙 s，就是該函數的秘密週期。
為什麼這很重要？ 在密碼學中，如果你想隱藏一份資訊，最有效的方法就是把它藏在一個看起來隨機、實則具備隱藏對稱性的函數背後。如果你能比別人更快抓出這個 s，你就掌握了破解加密的指紋。
古典電腦：大海撈針的生日攻擊
在古典邏輯下，要找出 s 只能靠硬碰硬。你必須不斷嘗試不同的 x，直到運氣好撞到兩組輸入 x 和 y，發現它們的輸出結果竟然一樣。
- 代價：根據機率論，為了找到這組碰撞，你需要嘗試大約 2n/2 次（這就是著名的生日攻擊 Birthday Attack）。
- 困境：當位元數 n 增加時，嘗試次數呈指數級爆炸，這正是現代加密演算法賴以維生的安全防線。
量子電腦：不找碰撞，直接抓取「對稱性」
Simon 演算法的神奇之處在於，它並不試圖透過窮舉來碰運氣，而是利用量子干涉直接過濾出關於 s 的資訊。
- 創造疊加態：利用 H 閘讓所有可能的 x 同時進入黑箱。
- 量子坍縮：當我們測量黑箱輸出 f(x) 的瞬間，輸入端的狀態會瞬間坍縮成一對具備 s 關係的疊加態。雖然我們不知道 x 是多少，但我們確信這兩個態之間隔著一個 s。
- H 閘干涉：再次施加 H 閘。這次干涉會產生一個奇妙的效果：所有與 s 不相干的機率幅都會互相抵消，最後我們測量到的是一個與 s 正交的向量 y（滿足 y ⋅ s = 0 ）。
一擊必殺變成了線性方程組：
量子電腦只需要運行大約 n 次程序，我們就能得到一組線性方程式。剩下的工作，交給古典電腦解方程，隱藏的 s 就無所遁形。
