量子计算Grover算法

Question

问题：-

量子计算的开发究竟有多大程度上加快了计算速度？(我们知道它有一些类似的效果，因为Grover的算法，但是有多少呢？BQP=P会吗？)

我所知道的

我理解Grover的算法，但解决这个问题似乎很困难。

Grover算法的来源：-

algorithm

有什么办法解决这个问题吗？

Answer 1

好吧，使用一个经典的朴素搜索算法，你在一个寄存器中一个接一个地查看一个条目，在你找到你想要的结果之前，它会平均接收N/2调用。Grover的算法，假设你有一个已经准备好的叠加状态的所有条目的寄存器，平均只取N个调用的平方根。对于大型寄存器来说，这是一个巨大的收益。

但这个故事并没有告诉我们，编制登记册的成本是很高的。每次调用Grover的算法时，都会“消耗”整个寄存器。因此，Grover算法的实际代价将是N*(寄存器的准备费用)的平方根。遗憾的是，量子寄存器(寄存器中所有条目的状态叠加)的准备与N一起放大，因此Grover的算法可能无法为经典搜索算法提供实际的增益！

是否有有效的方法来准备量子寄存器还有待观察。如果你能找到一种O(sqrt(N))的方法来准备它，它至少会和经典的搜索算法一样有效。

Answer 2

@Exeko对Grover基于算法的搜索操作的计算成本的观察是非常有效和重要的关注，当它是实现的盒子。然而，通过引入具有可验证随机函数的量子布卢姆滤波器，可以将从量子寄存器中获取信息的成本和成本降到最低。量子Bloom滤波器将帮助我们消除寄存器中的假阳性。因此，我们不需要每次消耗整个寄存器。去年，我们在IBM中实现了Grover的算法，增加了一个带全加器电路的量子Bloom滤波器。这可以帮助我们实现二次加速在端到端的搜索性能。