Grover算法的实际性能(仍属理论)

Question

Grover算法是一种用于搜索“黑匣子”函数的量子算法，可以将对称密码和散列之类的搜索空间减少一半(二次加速比)。这将有效地减少例如SHA-256到128位或AES-128到64位。

..。理论上，当然。还没有人能建立一个可以运行Grover算法的QC，而且我怀疑在很长一段时间里，除了玩具问题之外，还会有一个这样的QC。

话虽如此，我对Grover的算法是如何工作的有一个疑问。

我的理解是，在Grover的算法中，有一个经典的步骤，在这个步骤中，必须对给定点的经典函数进行求值，以检验该点是否是正确的答案。

如果是这样的话，你是否可以通过设计一种代价高昂且效率低下的算法来限制量子后搜索的性能呢？我正在考虑一些内存硬复合散列异常，如CryptoNight，它们在加密货币世界中用作块散列/挖掘函数。一个缓慢而复杂的内存硬算法会有效地限制Grover算法在现实世界中的性能，使每次迭代都非常慢吗？因此，即使你得到二次加速比，2^64或2^128的搜索，对于花费250 an经典计算时间的搜索，仍然需要相当长的时间。

有什么想法？

Answer 1

你是正确的。实际上，Grover的算法必须评估在每次迭代中受到攻击的函数(实际上，获得平方根速度的算法复杂性度量是查询复杂性)。当然，如果你让这个功能变得更昂贵，你也会让攻击变得更昂贵--古典的和量子的。然而，在这里，我们将从渐近语句切换到精确语句。这往往取决于设备的确切结构。例如，即使时钟速度相同，许多功能在不同的CPU上也会有不同的速度。问题是，我们还不知道未来的量子计算机将采用哪种架构。

在研究论文中，常见的问题是用T门深度来测量量子算法的精确复杂度。然而，这作出了两个假设。首先，使用的门集将是CNOT、T，其次，T门控制执行时间(在此设置中很有可能)。这使得很难确定哪种函数在量子计算机上会特别慢。

此外，对于量子计算机来说，内存成本与执行时间成本之间的关系仍然是开放的。因此，还不清楚一个内存硬函数是否比一个独立于可用内存的缓慢函数更好。存在量子比特的体系结构，其中保持状态比操纵状态容易得多。在这种情况下，瓶颈可能是速度，而不是内存。然而，这一切只是看水晶球.，最多只能猜测一下。