量子计算机上的经典计算
1.简介
拥有一组通用量子门的一个作用是能够重现任何经典计算。我们只需要将经典计算编译到我们在计算的原子中看到的布尔逻辑门中，然后在量子计算机上重现这些计算。
这证明了关于量子计算机的一个重要事实:它们可以做经典计算机可以做的任何事情，而且它们可以以至少相同的计算复杂度做到这一点。虽然它的目的不是将量子计算机用于经典计算机已经擅长的任务，但这仍然是一个很好的证明，量子计算机可以解决一般范围的问题。
此外，需要量子解决方案的问题通常涉及可以使用经典算法解决的组件。在某些情况下，这些经典的部件可以在经典的硬件上完成。然而，在许多情况下，经典的算法必须在处于叠加状态的输入上运行。这就要求经典算法必须在量子硬件上运行。在本节中，我们将介绍这样做时用到的一些想法。
2.咨询Oracle
许多量子算法都是基于一些函数 f(x) 的分析。通常这些算法只是假设这个函数存在某种“黑盒”实现，我们可以给出输入 x ，并接收相应的输出 f(x) 。这就是所谓的Oracle。
以这种抽象方式思考Oracle的优势使我们能够专注于我们用来分析函数的量子技术，而不是函数本身。
为了理解oracle如何在量子算法中工作，我们需要明确它们是如何定义的。oracle的主要形式之一是布尔型oracle。这些可以通过以下的酉演化来描述，
这里 \left|x， \bar 0 \right\rangle = \left|x \right\rangle \otimes \left|\bar 0 \right\rangle 用于表示由两个寄存器组成的多量子比特状态。第一个寄存器的状态是 \left|x\right\rangle ，其中 x 是函数输入的二进制表示。这个寄存器中的量子比特数就是表示输入所需的比特数。
第二个寄存器的工作是对输出进行类似的编码。具体来说，在应用 U_f 之后，这个寄存器的状态将是输出 \left|f(x)\right\rangle 的二进制表示，这个寄存器将由所需的数量的量子位组成。这个寄存器的初始状态 \left|\bar 0 \right \rangle 表示所有量子比特都是 \left|0 \right \rangle 的状态。对于其他初始状态，应用 U_f 将导致不同的结果。产生的具体结果将取决于我们如何定义酉 U_f 。
oracle的另一种形式是阶段oracle，定义如下:
其中输出 f(x) 通常是一个简单的位值 0 或 1 。
尽管它在形式上与布尔预言有很大的不同，但它在很大程度上是相同基本思想的另一种表达。事实上，它可以使用上一节中描述的相同的相位反冲机制来实现。
要理解这一点，请考虑布尔oracle U_f ,这就相当于同一个函数。这可以实现为本质上是受控非的一般化形式。它在输入寄存器上进行控制，使输出位保持状态 \left|0 \right \rangle for f(x)=0 ，并应用 x 将其翻转为 \left|1 \right \rangle if f(x)=1 。 如果输出寄存器的初始状态是 \left|- \right \rangle ，而不是 \left|0 \right \rangle ，那么 U_f 的作用就是精确地推导出 (-1)^{f(x)} 所需要的阶段。
由于输出量子比特的 \left|- \right\rangle 状态在整个过程中保持不变，因此可以安全地忽略它。最终的效果是相位oracle被相应的布尔oracle简单地实现。
3.倒垃圾
oracle计算的函数通常是那些可以在经典计算机上高效计算的函数。然而，将其实现为上述形式之一的幺正函数意味着它必须使用量子门来实现。然而，这并不像将可以实现经典算法的布尔门替换为对应的量子门那么简单。
我们必须注意的一个问题是可逆性。一元形式 U = \sum_x \left| f(x) \right\rangle \left\langle x \right| 只有在每个唯一的输入 x 导致唯一的输出 f(x) 时才可能，但一般情况下这是不正确的。然而，我们可以通过简单地在输出中包含输入的副本来强制它为true。正如我们之前看到的那样，正是这一点将我们引向了布尔oracle的形式
通过将计算写成酉的形式，我们可以考虑将其应用于叠加态的影响。例如，让我们对所有可能的输入进行叠加 x (为简单起见，未归一化)。这将导致所有可能的输入/输出对的叠加，
在调整经典算法时，我们还需要注意这些叠加态的行为是否符合我们的需要。经典算法通常不仅计算所需的输出，还会在此过程中创建额外的信息。一般来说，这种额外的计算残余不会造成严重的问题，而且它们占用的内存可以通过删除它们很容易恢复。然而，从量子的角度来看，事情并没有那么容易。
例如，考虑一个经典算法执行以下过程的情况，
这里我们看到第三个寄存器，它被用作经典算法的“暂存器”。我们将计算结束时留在寄存器中的信息称为‘garbage’， g(x) 。我们使用 V_f 来表示实现上述功能的一元函数。
量子算法通常建立在干扰效应之上。最简单的效果是用某个酉创建一个叠加，然后用那个酉的逆来移除它。当然，整个效果是微不足道的。然而，我们必须确保我们的量子计算机至少能够做这些琐碎的事情。
例如，假设我们的量子计算中的某个过程给了我们叠加态 \sum_x \left|x,f(x)\right\rangle ，我们需要将其返回到状态 \sum_x \left|x,0\right\rangle 。为此，我们可以简单地应用 U_f^\dagger 。应用这个的能力直接来自于知道一个将应用 U_f 的电路，因为我们只需要用它的逆函数替换电路中的每个门并颠倒顺序。
然而，假设我们不知道如何应用 U_f ，但知道如何应用 V_f 。这意味着我们不能在这里应用 U_f^\dagger ，而可以使用 V_f^\dagger 。不幸的是，垃圾的存在意味着它不会有同样的效果。
我们可以举一个非常简单的例子。我们将 x ， f(x) 和 g(x) 限制为只有一个比特位。我们还将使用 f(x) = x 和 g(x) = x ，每个都可以通过在输入寄存器上控制一个cx门来实现。
具体来说，实现 U_f 的电路就是输入和输出寄存器的单个位之间的以下单个cx。
from qiskit import QuantumCircuit, QuantumRegister
input_bit = QuantumRegister(1, 'input')
output_bit = QuantumRegister(1, 'output')
garbage_bit = QuantumRegister(1, 'garbage')
Uf = QuantumCircuit(input_bit, output_bit, garbage_bit)
Uf.cx(input_bit[0], output_bit[0])
Uf.draw()
对于 V_f ，我们还需要为垃圾创建输入的副本，我们可以使用以下两个cx门。
Vf = QuantumCircuit(input_bit, output_bit, garbage_bit)
Vf.cx(input_bit[0], garbage_bit[0])
Vf.cx(input_bit[0], output_bit[0])
Vf.draw()
现在我们来看看首先应用 U_f ，然后应用 V_f^{\dagger} 的效果。净效果如下所示。
qc = Uf + Vf.inverse()
qc.draw()
这个电路由两个相同的cx门开始，它们的影响相互抵消。剩下的就是输入寄存器和垃圾寄存器之间的最终cx。从数学上讲，这意味着
在这里，我们看到 V_f^\dagger 的操作并不是简单地将我们返回到初始状态，而是使第一个量子比特与不想要的垃圾纠缠在一起。因此，算法中的任何后续步骤都不会按预期运行，因为状态不是我们需要的状态。
因此，我们需要一种方法从量子算法中移除经典垃圾。这可以通过一个称为 'uncomputation’的方法来完成。我们只需要接受另一个空白变量并应用 V_f
然后，我们应用一组受控非门，每个门被控制在用于编码输出的一个量子比特上，并以额外的空白变量中的相应量子比特为目标。
这是使用单量子比特寄存器为我们的示例实现此操作的电路。
final_output_bit = QuantumRegister(1, 'final-output')
copy = QuantumCircuit(output_bit, final_output_bit)
copy.cx(output_bit, final_output_bit)
copy.draw()
这样做的效果是复制信息(如果你听说过不可克隆定理，请注意，这不是同一个过程)。具体来说，它以以下方式转换状态。
最后，我们应用 V_f^\dagger 来撤销原始的计算。
复制的输出仍然存在。最终效果是在没有垃圾的情况下执行计算，从而实现了所需的 U_f 。
对于我们使用单量子比特寄存器的示例，对于 f(x) ，整个过程对应于以下电路。
(Vf + copy + Vf.inverse()).draw()
利用到目前为止所知道的cx门的工作原理，您应该能够看到应用到垃圾寄存器的两个门将相互抵消。因此，我们成功地清除了垃圾。
快速练习
1.说明当‘output’寄存器初始化为 |0\rangle 时，输出被正确地写入‘final output’寄存器(且仅写入此寄存器)。
2.确定当‘output’寄存器初始化为 |1\rangle 时发生了什么。
有了这种方法，以及本章介绍的所有其他方法，我们现在已经拥有了创建量子算法所需的所有工具。现在我们来看看这些算法的实际效果。
import qiskit.tools.jupyter
%qiskit_version_table
Version Information
| Qiskit Software | Version |
|---|---|
| Qiskit | 0.27.0 |
| Terra | 0.17.4 |
| Aer | 0.8.2 |
| Ignis | 0.6.0 |
| Aqua | 0.9.2 |
| IBM Q Provider | 0.14.0 |
| System information | |
| Python | 3.7.7 (default, May 6 2020, 04:59:01) [Clang 4.0.1 (tags/RELEASE_401/final)] |
| OS | Darwin |
| CPUs | 8 |
| Memory(Gb) | 32.0 |