机构名称：
¥ 1.0
2 n 次旋转，我们可以近似地翻转 | x 0 ⟩ 和 | φ ′ ⟩ 。如果我们最初从 | ψ ⟩ 开始，那么在这次旋转之后，我们将很有可能获得 | x 0 ⟩ 。我们并没有在这里给概率加点，也没有越过界限，但只要稍加努力就可以做到。值得注意的是，与传统情况相比，搜索所需的查询数量加快了二次方。Grover 算法的电路成本呢？查询成本我们已经计算过了。然后是 W 。我们如何有效地实现 W = 2 | ψ ⟩⟨ ψ |− I ？请注意，这是 W = H ⊗ n (2 | 0 ⟩⟨ 0 |− I ) H ⊗ n，其中 H 是我们的朋友 Hadamard 门。因此，我们需要知道如何有效地实现 (2 | 0 ⟩⟨ 0 | − I 。这个幺正将所有状态映射到自身，其中 | 0 ⟩⟨ 0 | 不获取任何相位，而所有其他计算基础状态都获取 − 1 相位。引入一个反转此相位的全局相位很有用：− 2 | 0 ⟩⟨ 0 | + I 。实现此门的一种方法如下。首先请注意，您可以使用 Tofolli 门、单个受控门和一些初始化为 | 0 ⟩ 的额外辅助工作区量子位构造多个受控操作（它们最终也会是 | 0 ⟩ 。）为此，对于您想要条件化的量子位，计算前两个量子位的 AND 并使用 Tofolli 将其放入辅助工作区量子位，然后计算这个量子位和第三个量子位的 AND 放入第二个工作区量子位使用 Tofolli。继续这样做，你会看到在 n 个量子位中，你可以获得在某些辅助寄存器中计算的所有控制位的 AND。以此量子位为条件，在目标量子位上执行所需的受控门。然后反向运行你已经执行的 Tofolli 电路，从而擦除辅助量子位中的垃圾。现在要实现 − 2 | 0 ⟩⟨ 0 | + I ，请注意，如果你执行 − 1 量子位控制的 Z（Z 是 Pauli 相位运算符），那么这个门就是 − 2 | 1 n ⟩⟨ 1 n | + I 。只需在这个门之前和之后应用 X ⊗ n 即可将其变成所需的门（直到全局相位。）因此，我们看到我们可以使用 O（2 n）个基本门实现 W 。请注意，此操作 W 有时称为“关于均值反转”操作。我让你来决定它为什么有这个名字。
CSE 599d - 量子计算 Grover 算法
主要关键词
相关文件推荐
