python - 什么是大简化的 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 搜索的实际应用。

更正确的做法是将神谕视为识别答案的工具，而不是找到答案的工具。例如，如果您要解决 SAT problem ，oracle 电路将为您要解决的问题的特定实例编码 bool 公式。

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

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