algorithm - 量子计算 Grover 算法

Question

问题：-

利用量子计算实际上可以加速计算多少？（我们知道它有一些效果，因为 Grover 的算法，但是有多少？BQP=P 吗？）

我知道的

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

Grover 算法的来源：-

https://en.m.wikipedia.org/wiki/Grover%27s_algorithm

有没有办法解决这个问题？

Answer 1

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

故事没有说明的是登记册的准备是昂贵的。每次调用 Grover 算法时，都会“消耗”整个寄存器。因此，格罗弗算法的实际成本将是 N * 的平方根（准备寄存器的成本）。遗憾的是，量子寄存器的准备（寄存器中所有条目的状态叠加）与 N 成比例。因此，Grover 的算法可能无法为经典搜索算法提供实际增益！

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

Answer 2

@Exeko 对基于 Grover 算法的搜索操作的计算成本的观察在开箱即用时是非常有效且重要的关注点。然而，通过引入具有可验证随机函数的量子布隆过滤器，可以最小化准备成本和从量子寄存器中检索信息的成本。Quantum Bloom Filter 将帮助我们消除寄存器中的误报。因此我们不需要每次都消耗整个寄存器。去年，我们在 IBM Q 中实现了 Grover 算法，增加了一个带有全加器电路的 Quantum Bloom Filter。这可以帮助我们实现端到端搜索性能的二次加速。