Grover 演算法（量子搜尋演算法）

想像一本完全沒有按姓名排序的電話簿——只是 N 條記錄亂堆在一起——而你想找出與某個已知名字相符的那一條。在經典做法裡，你別無選擇，只能一條一條地查，平均要翻過其中大約一半，所以工作量隨 N 增長。Grover 演算法是一種量子方法，它只需大約 N 的平方根那麼多步，就能找到這條被標記的記錄。對一份一百萬條的列表來說，大約是一千次檢查，而不是五十萬次。它需要一個「預言機（oracle）」：一種在看到正確答案時能認出它的辦法，哪怕它沒法直接指出答案在哪裡。

下面說說它真實的運作機制，因為這一點很容易被聽岔。這個演算法並不是「一次性把所有答案都試一遍」，然後把勝出者讀出來。它一開始讓所有可能性共享相等的振幅，然後重複一個兩步操作——預言機把被標記答案的振幅翻轉符號，第二步操作再把所有振幅相對於它們的平均值做一次反射。每一輪都把多一點點振幅推向正確答案、推離其餘答案，這個過程稱為振幅放大（amplitude amplification）。大約 sqrt(N) 輪之後，正確結果就有很高的機率被測量到。輪數跑得太多，振幅會衝過頭、然後又開始縮小，所以迭代次數其實很要緊。