第6章 Grover 搜尋演算法#

章前言#

在 \(N\) 筆無序資料中找一筆目標，古典方法必須逐一檢查，平均 \(N/2\) 次、最壞 \(N\) 次。1996 年 Lov Grover 證明量子電腦只需 \(O(\sqrt{N})\) 次黑箱查詢——把 \(2^{20}\) 筆資料的搜尋從一百萬次縮減到一千次，這是平方加速，也是至今對最一般化搜尋問題最好的量子結果。

6.1 節說明演算法的兩個積木：均勻疊加（一次「摸到」所有資料）與相位反轉 oracle（把答案的符號翻負）；6.2 節介紹 Grover 迭代的另一半——擴散算子（對平均值的反射），並證明兩個反射合成一次旋轉，每轉一次目標振幅就增大；6.3 節給出迭代次數 \(r \approx \frac{\pi}{4}\sqrt{N/M}\) 的幾何證明，討論多重解、最優性（BBBV 下界）與實際應用（資料庫、SAT、密碼學金鑰搜尋）。

本章所有電路都會用第 3 章的模擬器實作，讀者可以親眼看著振幅像鐘擺一樣擺向答案。

學習目標

1. 實作 Grover 的相位反轉 oracle 與擴散算子。
2. 推導迭代次數公式並解釋為什麼是 \(\pi/4\sqrt N\) 。
3. 說明 Grover 的最優性下界與它在密碼學中的影響（如對稱金鑰長度減半）。