量子搜索算法的工作原理（2）：量子搜索算法的组成部分—第一步

本教程其他文章，请参看此链接：

在引言中，我对量子搜索算法的实现进行了非正式描述。为了使搜索算法更具体，让我们考虑一下，使用搜索来解决旅行推销员问题（TSP）的特殊情况。当然，有比搜索更好的TSP方法，但是本节的目的是，展示搜索算法中涉及的总体构造块。为此，TSP是一个有用的具体示例。在下一节中，我们将了解，有关这些组成部分如何工作的详细信息。

考虑一下TSP的变体会有所帮助，即搜索比指定的阈值距离TT短的路线。换句话说，我们将使用搜索来解决以下问题：

“以下是城市列表-霍比屯，米纳斯提力斯，埃多拉斯，布雷，戴尔，…–以及它们之间的距离（我不会尝试指定，但您可以想象！）是否有一条穿过所有城市的路线？长度小于2,000公里（或等值的英里）？”

这与最小路径查找并不完全相同，但是事实证明，这种变化更容易连接到量子搜索算法。注意到各种变化，这就是量子搜索算法的样子：

搜索寄存器包含候选解∣x⟩ = | x_1，x_2, …，x_n ⟩。在这种情况下，我们的搜索寄存器将包含穿过城市的潜在路线，并写为位字符串x = x_1，x_2，…。我不会明确涉及位字符串表示-有很多方法可以进行这种表示，而细节并没有多大关系。关键是您应该将搜索寄存器视为叠加∑_x α_x∣x⟩个穿过城市的不同可能路径，而x是路径的某种位字符串表示。

为了明确起见，我还将假设搜索寄存器以全∣0⟩ 的状态开始。那只是一个约定：我们需要从某个地方开始。

量子搜索算法的第1步将是由标准量子门组成的固定量子电路—如你“最好奇的量子计算”一文（链接请参看文章开始）所讨论的，像Hadamard和CNOT门。当然，最终我们需要弄清楚这些门应该是什么。我们将在后面的部分中进行说明。但是目前，我们只是停留在广义的概念层面，试图弄清楚量子搜索算法的外观。

下一步是检查搜索寄存器状态∣x⟩是否对应于我们所说的穿过城市的短路线，即距离短于阈值T的路线。为此，我们引入一个检查量子位来存储此步骤的结果，并在状态∣0⟩中对其进行了初始化。因此，我们从∣x⟩∣0⟩状态开始，如果x代表通过城市的短途路线，则更改为∣x⟩∣1⟩。当x表示短路径时，将保留为∣x⟩∣0⟩。我们可以紧凑地写为∣x⟩∣0⟩→∣x⟩∣s(x)⟩，其中搜索函数s（如果x是问题的解决方案（即，长度小于T的路由），则s(x)等于1；如果x不是解决方案，则s(x)等于0。

当然，通常，搜索寄存器位于∑_x α_x∣x⟩的叠加中。我们将假设（并在稍后说明）该“如果检查短距离路线”步骤是线性发生的，取∑_x α_x∣x⟩∣0⟩到∑_x α_x∣x⟩ ∣s(x)⟩。

如何执行“如果短路检查”步骤？当然，从原理上讲，构造一个能解决问题的传统经典电路很容易—电路只需检查位串x = x_1 x_2 ...是通过所有城市的有效路线，如果这样，则将相加相应的距离，并将其与阈值T进行比较。我们可以采用该经典电路—无论它是什么—并将其转换为等效的量子电路。在你最好奇的量子计算的文章中，我解释了如何使用Toffoli和NOT 门进行此类翻译，在此不再赘述。当然，我们仍然需要找出经典电路的确切细节，但是: (a)这是经典计算的一部分，而不是量子计算; (b)在任何情况下都是与进行搜索工作无关的细节。稍作说明（稍后讨论），我们将理所当然地拥有一个可以完成这项工作的量子电路。