如何在量子计算中模拟Grover算法？

Question

如果我想写一个程序来模拟Grover算法，我该如何为它写神谕呢？如果我已经知道结果了，为什么还要使用搜索呢？

Answer 1

Grover搜索实现的许多示例使用具有硬编码答案的oracle，这确实不是很有启发性。在一般情况下，Grover搜索的重点当然是在您不知道答案的情况下执行搜索。要为此编写一个oracle，您不需要一个检查输入是否等于某个硬编码值的oracle，而需要一个检查输入的某个属性的oracle。实现oracle是解决问题最困难的部分。

这类问题最简单的例子是SAT problem。您可以将公式中的变量映射到输入的量子位，并编写一个oracle，它可以相对容易地计算f(x)，并且可以应用Grover搜索来找到满足给定公式的解释，但仅仅看一眼oracle并不知道答案。您可以在SolveSATWithGrover教程中看到实现oracle来解决SAT问题的示例。

附注:在Quantum Computing StackExchange上有很多关于Grover搜索算法的很好的答案。