（仍然是理論上的）格羅弗算法的真實世界表現
Grover 算法是一種用於搜尋“黑盒”函式的量子算法，可用於將對稱密碼和散列等搜尋空間減少一半（二次加速）。這將有效地減少例如 SHA-256 到 128 位或 AES-128 到 64 位。
……當然，理論上。還沒有人建立一個可以執行 Grover 算法的 QC，我懷疑是否會有一個可以在很長一段時間內解決玩具問題以外的任何事情。
話雖如此，我對 Grover 的算法如何工作有疑問。
我的理解是，在 Grover 的算法中有一個經典步驟，其中必須對給定點評估經典函式以測試該點是否是正確答案。
如果是這種情況，您是否可以通過設計一種故意昂貴且低效的算法來限制後量子搜尋的性能？我正在考慮一些像 CryptoNight 這樣的記憶困難的複合雜湊怪物，它們在加密貨幣世界中用作塊雜湊/探勘函式。一個緩慢而復雜的記憶硬算法是否會通過使每次迭代都非常慢來有效地限制 Grover 算法在現實世界中的性能？因此，即使您獲得二次加速，每次搜尋需要 250 毫秒的經典計算時間的 2^64 或 2^128 次搜尋仍然會花費大量時間。
想法？
你說的對。實際上，Grover 的算法必須評估在每次迭代中受到攻擊的函式（實際上，獲得平方根加速的算法複雜度度量是查詢複雜度）。當然，如果你讓這個函式變得更昂貴，你也會讓攻擊變得更昂貴——經典的和量子的。然而，這裡我們正在從漸近語句切換到精確語句。這些往往取決於設備的確切架構。例如，即使時鐘速度相同，許多功能在不同 CPU 上的速度也會不同。問題是我們還不知道未來的量子電腦將採用哪種架構。
研究論文中的共同點是根據 T 門深度來測量量子算法的精確複雜性。然而，這有兩個假設。首先，使用的門集將是 CNOT，T，其次，T 門支配執行時間（在這個設置中很可能）。這使得很難確定哪種函式在量子電腦上會特別慢。
此外，對於量子電腦，記憶體成本與執行時間成本之間的關係仍然是開放的。因此，尚不清楚記憶體硬函式是否優於獨立於可用記憶體的慢速函式。存在用於保持狀態比操縱狀態容易得多的量子位架構。在這些情況下，瓶頸可能是速度，而不是記憶體。然而，這一切都只是對水晶球的一瞥……，最多也只是猜測而已。