Grover 的算法可以並行化嗎？
Grover 算法可以搜尋長度的無序列表 $ N $ 及時 $ \sqrt{N} $ 在量子電腦上。應用於密碼學，這意味著它可以恢復 n 位密鑰並找到 n 位雜湊的原像，成本為 $ 2^{n/2} $ .
但是格羅弗算法的基本版本是順序的。每次迭代都使用前一次迭代的輸出作為輸入。我沒有看到一種明顯的方法來並行化算法。減少迭代次數比線性減少成功機率顯著降低。
如果算法本質上是順序的，那麼建構更大的電腦不會加速攻擊，從而限制其影響。 $ 2^{80} $ 對我來說，順序密碼呼叫看起來很難實現。另一方面， $ 2^{80} $ 今天，使用經典電腦，並行密碼呼叫已經處於可行性的邊緣。
假設使用量子電腦的攻擊者僅限於 $ T $ 時間步長 $ T<\sqrt{N} $ ，因此他們無法以最佳順序步驟數執行 Grover 算法。查找原像/恢復密鑰的成本是多少？如果他們有多個目標，每次中斷的平均成本是多少？
我們最近與一些同事討論了這個問題，這是我們提出的（不保證）：
Grover 算法僅在輸入一組輸入時輸出正確答案，使得目標函式對於單個輸入的評估為 1，否則為 0。然後算法迭代一個子程序 $ \sqrt{N} $ 次（在哪裡 $ N $ 是輸入集的大小）來推動評估為 1 的輸入的幅度。這樣一來，正確的輸入就會以足夠高的機率被測量（抱歉在這一點上含糊不清）。
要使用 Grover 算法來攻擊雜湊函式的原像抗性，您選擇輸入的一個隨機子集，並希望有一個輸入實際上是目標值的原像（我猜少量原像也應該可以，因為所有它們的幅度應該被推高並最終測量其中之一）。現在，格羅弗算法的執行時間取決於輸入集的大小 $ N $ . 所以，我們想保留這個 $ N $ 小的。另一方面，我們必須選擇 $ N $ 使得在這個集合中很有可能存在原像。一般來說，假設我們需要採取 $ N $ 按照雜湊函式的輸出大小的順序來獲得足夠高的機率。
如果我們想並行化它，它應該如下工作。假設我們得到一台量子電腦，其量子比特數是執行 Grover 所需的兩倍大小的輸入集 $ N $ . 在這種情況下，我們可以在兩個大小的輸入集上執行它 $ N $ 雖然仍然只需要時間 $ \sqrt{N} $ . 然而，好處也只是線性的，找到原像的機率（或者更確切地說，找到包含原像的輸入集的機率）只是加倍。
當然，我們也可以使用一組大小的輸入來執行它 $ N^2 $ ，成倍地增加我們的成功機率，但這也成倍地增加了執行時間。
這是一個較老的問題，但最近對我來說已經出現了幾次，我想補充一些說明。
如果你想加快 Grover 的算法，你可以把搜尋空間分成 $ k $ 塊並執行獨立搜尋 $ k $ 機器。由於您的搜尋空間是 $ \frac {N} k $ ，每次搜尋將在 $ O(\sqrt{ \frac {N} k}) $ . 您只能獲得平方根加速，因為您在分割搜尋空間時會失去量子並行化。更詳細的解釋可以在這裡找到。
並行化問題與多個目標的問題是分開的。與mephisto 的回答相反，格羅弗的算法在包含 $ k $ 正確的索引/輸入，前提是您將迭代次數修改為 $ \frac {\pi} 4 \sqrt{\frac {N} k} $ . 什麼時候 $ k $ 是未知的（通常情況下），您可能需要運用一些技巧來保持它 $ O(\sqrt{\frac {N} k}) $ （見本文第 4 節）。重要的， $ N $ 不需要“保持小”來適應這一點。主要製約因素 $ N $ 是底層硬體能力。