首先考虑经典解决方案。由于我们对F一无所知，因此我们能做的最好的就是按随机输入进行评估。如果我们很幸运地找到x和x 0，以便f（x）= f（x 0），那么我们有答案，r = x⊕x 0。测试M值后，您将消除大约M（M -1） / 2可能的R向量（即，对于每对M向量的每对X X 0）。当m2⇡2n时，您将完成。因此，平均而言，您需要进行2 n/ 2个功能评估，这在输入的大小上是指数的。对于n = 100，它需要大约2 50⇡1015评估。“以每秒1000万个电话为单位，大约需要三年的时间”（Mermin，2007年，第55页）。我们将看到，量子计算机可以在大约120个评估中以高概率（> 1-10-6）确定R。以每秒1000万个电话，这将需要大约12微秒！