Grover的算法在一个大的简化中是什么？

Question

我是量子计算的新手。我的意思是非常新。我看到有一种叫做Grover搜索算法的算法。我读到它在包含N个元素的数据库中搜索，以便找到特定的元素。我还读到，标准计算机将在许多年内做到这一点，而量子计算机将在几秒钟内做到这一点。这是最让我困惑的。我的理解:假设我们想要搜索包含50.000个不同名字的数据库，我们正在寻找一个名字"Jack“。标准的计算机在几年内都不能做到这一点，对吧？我认为有几秒钟或几分钟的问题，因为在包含姓名的数据库中搜索可能是文本不会花费很长时间……

python中的示例：

names = ["Mark", "Bob", "Katty", "Susan", "Jack"]

for i in range(len(names)):
    if names[i] == "Jack":
        print("It's Jack!")
    else:
        print("It's not Jack :(")

这就是我的理解。假设这个列表包含50.000个名字，我们想要搜索"Jack“。我想不会花太长时间的。

那么Grover的算法是如何工作的呢？我真的搞不懂。

Answer 1

Grover的搜索确实不能很好地替代传统的数据库查找方法。(请注意，经典数据库中将包含经典索引，这将使查找速度大大超过您的实现。)您可以查看this paper，了解Grover search的实际应用。

更正确的做法是将神谕视为识别答案的工具，而不是寻找答案。例如，如果您正在寻找解决SAT problem，oracle电路将对您试图解决的问题的特定实例的布尔公式进行编码。

如果您要使用Grover的算法进行数据库搜索，oracle将必须编码您正在搜索的条件，以及元素是否在数据库中的标准。例如，如果要查找以A开头的名称，oracle需要识别所有以A开头的字符串，但它还需要识别数据库中存在哪些字符串-否则算法将生成一个以A开头的随机字符串，这可能不是您要查找的字符串。

格罗弗算法在推广到amplitude amplification时具有实际应用，它显示为许多其他量子算法的一个组成部分。振幅放大是提高概率量子算法成功可能性的一种方法。