题：-
利用量子计算实际上加速了多少计算？ （我们知道它有很好的效果，因为Grover的算法，但是多少？BQP = P？）
我知道的
我理解Grover的算法，但解决这个问题似乎很难。
Grover算法的来源： -
https://en.m.wikipedia.org/wiki/Grover%27s_algorithm
有什么方法可以解决这个问题吗？
好吧，使用经典的天真搜索算法，你可以在一个寄存器中一个接一个地查看一个条目，它会在你找到你想要的结果之前进行平均N / 2个调用。假设您已经准备好了处于叠加状态的所有条目的寄存器，Grover的算法将仅取平均N个调用的平方根。对于大型寄存器，这是一个巨大的收获。
这个故事没有说明的是，登记册的编制成本很高。每次调用Grover算法时，都会“消耗”整个寄存器。因此，Grover算法的实际成本将是N *的平方根（编写寄存器的成本）。遗憾的是，量子寄存器的准备（寄存器中所有条目的状态的叠加）与N成比例。因此，Grover的算法可能无法为经典搜索算法提供实际增益！
如果有有效的方法来准备量子寄存器，还有待观察。如果可以找到O（sqrt（N））方法来准备它，它至少会像经典搜索算法一样有效。