Grover 的算法可以在 N/2 中執行搜尋，以在雜湊函式原像的特定子集中進行匹配嗎？

假設我首先定義了某個函式 f(x)，其中 x 是某個無符號的 256 位整數，並且該函式的輸出是一組任意長度的不同字元串，因此輸出集將是 2^256 個唯一字元串，即x 的指定域。

範例f(x) = 0xAA || x || 0xBB(||表示字節連接)，但它也可能更複雜，例如f(x) = 0xAA || g(x) || 0xBB.

然後，如果我將該函式插入到某個 Hash_256 函式中，如下所示：Hash_256(f(x))量子電腦能否揭示f(x)複合函式的某些已知輸出的匹配，並且在 2^128 次嘗試中？通過將復合函式視為“黑匣子”函式並在 x 上進行量子搜尋，這行得通嗎？

背景：比特幣地址，試圖在這裡回答我自己的問題。這實際上是針對我所追求的 160 位雜湊的消息模板搜尋。

是的，但請注意，這些操作必須連續執行，因為 Grover 的算法是高度不可並行的。即使我們建構的量子電腦可以在一個週期內評估功能並且時鐘速率與現代電腦相當（兩者都是非常先進的），這將接管 $ 2^{80} $ -年。如果你想花 1/10 的時間，那麼你將不得不購買這台高端量子電腦的 100 倍。

引用自：https://crypto.stackexchange.com/questions/102574