quantum-computing - 一种在 4 比 1 函数上具有高概率的量子算法

Answer 1

好吧，选择x为 0 给出f(0) = f(a) = f(b) = f(a xor b). 并且没有其他匹配的输入f(0)。所以我们只是在寻找v令人满意的v != 0, f(v) = f(0)。因此，制作一个电路，v当它满足时采用 a 并反转相位，否则什么也不做。然后应用 Grover 算法。运行时间将是O(sqrt(N))找到第一个值。然后你也重复它。

另一方面，只是经典地随机采样直到你发现碰撞也有预期O(sqrt(N))的时间，所以你可能会做一些更聪明的事情。