量子计算（二）

作为说明，让我们假设我们有两个量子位可供使用。一对量子位有四种计算基础状态：{|00⟩，|01⟩，|10⟩，|11⟩}。如果这些是经典位，它们将代表系统的四种物理可能状态。但一对量子位也可以存在于这四种基本状态的叠加中，每个基本状态都有自己的复系数（其模平方，被解释为概率，被归一化）。只要量子系统统一演化并且无法测量，就可以想象它会“存储”那么多位（规范）信息。然而，困难的任务是根据国家可访问信息的限制有效地使用这些信息。

2.2 量子门

经典计算门是操纵以位存储的信息的布尔逻辑门。在量子计算中，此类门由矩阵表示，并且可以可视化为布洛赫球体上的旋转。这种可视化表示量子门是酉算子的事实，即它们保留量子态的范数（即 U†U=I，其中 U 是代表量子门的线性算子，U† 是其伴随物）。在经典计算中，一些门是“通用的”。例如，两个输入 A 和 B 之间的所有可能的逻辑连接都可以使用一些 NAND 门串来实现（每个 NAND 门都评估函数“不同时 A 和 B”）。另一种通用门是“或非”门。在量子计算的背景下，有人证明（DiVincenzo 1995）两个量子位门（即转换两个量子位）足以实现任何量子电路，从某种意义上说，电路仅由（一小组）一个组成两个量子位门可以以任意精度逼近 n 个量子位的任何酉变换。巴伦科等。等人。 （1995）特别表明，在这个意义上，任何多量子位逻辑门都可以由单量子位门和双量子位受控非（CNOT）门的组合组成，后者翻转或保留其“目标”输入位取决于其“控制”输入位的状态（具体来说：在 CNOT 门中，目标量子位的输出状态是类似于输入上的经典异或 (XOR) 门的运算结果）。量子门与经典门的区别在于它们总是可逆的：酉矩阵的逆也是酉矩阵，因此一个量子门总是可以被另一个量子门反转。

CNOT=[

1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0

]。

两条水平线；上面的线中间有一个实心的黑色圆圈；最左边标记为 ket(x)，最右边标记为 ket(x)；下线中间有一个空心圆；最左边标记为 ket(y)，最右边标记为 ket(x 圆加 y)；有一条垂直线从封闭的黑色圆圈一直到开放圆圈的底部。

CNOT 门

酉门操纵存储在“量子寄存器”（量子系统）中的信息，从这个意义上说，普通（酉）量子演化可以被视为一种计算。然而，为了读取该计算的结果，必须测量量子寄存器。测量被表示为一个非酉门，它将寄存器中的量子叠加“折叠”到其中一项上，其概率对应于该项的复系数。通常这是相对于计算基础来描述的，但原则上可以在无限多个可能的正交基中的任何一个中进行测量，相对于给定状态 |ψ⟩ 可以表示为基状态的线性组合。碰巧的是，某些此类测量比其他测量更难实施。

2.3 量子电路

量子电路与经典计算机电路类似，由逻辑线和门组成。电线用于携带信息，而门则操纵信息（请注意，电线是抽象的，不一定对应于物理电线；它们可能对应于物理粒子，例如光子，在空间中从一个位置移动到另一个位置，甚至时间演化）。传统上，量子电路的输入被假设为多个量子位，每个量子位都初始化为计算基础状态（通常为 |0⟩）。然后以某种正交基础（通常是计算基础）测量电路的输出状态。

第一个量子算法（即 Deutsch-Jozsa、Simon、Shor 和 Grover）就是在这种范式中构建的。目前存在的其他量子计算范例在许多有趣的方面与电路模型不同。然而，到目前为止，它们都已被证明在计算上与电路模型等效（见下文），从某种意义上说，可以通过电路模型解决的任何计算问题都可以通过这些新模型来解决，而只需多项式开销在计算资源中。我们注意到这里与各种经典计算模型的相似之处，任何“合理”的此类模型都可以由任何其他模型有效地模拟（有关讨论，请参见 Cuffaro 2018b，274）。

3 量子算法

算法设计是一项高度复杂的任务，而在量子计算中，巧妙地利用量子力学的特性来使算法更加高效，使得任务变得更加复杂。但在讨论量子算法设计的这一方面之前，让我们首先说服自己，量子计算机实际上可以模拟经典计算。从某种意义上说，这是显而易见的，因为我们相信量子力学的普遍特征，并且观察到任何在计算基础上是对角的量子计算，即不涉及量子位之间的干扰，实际上都是经典的。然而，量子电路可用于模拟经典电路的演示并不简单（回想一下，前者总是可逆的，而后者使用的门通常是不可逆的）。事实上，量子电路不能直接用来模拟经典计算，但后者仍然可以使用中间门（即Toffoli门）在量子计算机上进行模拟。该通用经典门具有三个输入位和三个输出位。其中两个输入位是控制位，不受门操作的影响。第三个输入位是目标位，如果两个控制位都设置为 1，则翻转该位，否则保持不变。该门是可逆的（其逆是其本身），但是通过将多个这样的门串在一起，可以模拟任何经典电路。因此，使用 Toffoli 门的量子版本（根据定义，它与经典 Toffoli 门类似地排列计算基础状态），可以用量子可逆逻辑门来模拟不可逆经典逻辑门，尽管相当乏味。因此，量子计算机能够执行经典确定性计算机可以执行的任何计算。

概率计算怎么样？毫不奇怪，量子计算机也可以通过使用另一个著名的量子门来模拟这种类型的计算，即哈达玛门，这是一种单量子位门，它将输入状态|0⟩

|0⟩+|1⟩

√

2

和输入状态 |1⟩ 到

|0⟩−|1⟩

√

2

。测量这些输出状态中的任何一个都会以 50/50 的概率产生 |0⟩ 或 |1⟩，这可用于模拟公平的抛硬币。

H=

1

√

2

[

1 1

1 −1

]

x-y 平面上显示一个圆；在正 x 轴上，圆点标记为 ket(0)；在正 y 轴上，圆点标记为 ket(1)；虚线从原点向右向上 45 度，向右向下 45 度；上面的虚线与圆相交的点标记为 (ket(0) + ket(1))/sqrt(2)，下面的虚线与圆相交的点标记为 (ket(0) - ket(1) ))/sqrt(2)。

哈达玛门

显然，如果量子算法只能用于模拟经典算法，那么人们对它们的兴趣将比目前更加有限。但是，虽然可能总是存在一些阻碍量子加速的计算问题（参见 Myers 1997 和 Linden & Popescu 1998 [其他互联网资源]），但社区普遍相信量子算法不仅可以模拟经典算法，而且可以模拟经典算法。在某些情况下，它们实际上会优于后者，这对我们易处理和难处理的抽象概念的影响存在争议（Cuffaro 2018b；Hagar 2007）。

3.1 基于量子电路的算法

3.1.1 预言机

第一个量子算法旨在解决本质上涉及使用“预言机”的问题，所以让我们首先解释一下这个术语。预言机是一种概念设备，已被证明在计算问题的复杂性理论分析中非常有用，人们可以将其视为一种想象中的神奇黑匣子（Arora & Barak 2009, 72–73; Aaronson 2013a, 29ff.）就像德尔福著名的神谕一样，人们提出（是或否）问题。与古代的神谕不同，计算机科学中考虑的神谕总是在单个时间步长内返回答案。例如，我们可以想象一个预言机来确定给定的布尔公式是否可满足：给定特定命题公式的描述作为输入，预言机在单个时间步中输出一个位，指示是否存在满足该公式的真值分配。显然这样的机器并不真正存在——SAT（可满足性的缩写）是一个 NP 完全问题——但这不是重点。使用此类想象设备的目的是从某些“实现细节”中抽象出来，这些细节无论出于何种原因被认为对于回答给定的复杂性理论问题并不重要。例如，Simon 的问题（Simon 1994）是确定给定函数 f 的周期，该函数在按位模 2 加法下是周期性的。相对于西蒙的问题，我们认为 f 的内部复杂性并不重要，因此通过想象我们有一个预言机可以一步评估它来抽象它。尽管这些概念装置很有用，但它们的用途也有局限性。举个例子，有 P = NP 的预言机，也有 P ≠ NP 的预言机。这个（以及许多其他）问题并没有被预言机澄清（参见 Fortnow 1994）。

3.1.2 Deutsch算法

Deutsch (1989) 提出了以下问题：假设我们有一个函数 f，它可以是常数，即这样它就可以为每个可能的输入产生相同的输出值，或者是平衡的——即使得其可能输入的一半的输出与另一半的输出相反。所考虑的特定示例是函数 f:{0,1}→{0,1}，如果 f(0) =f(1)，则该函数为常数；如果 f(0) ≠ f(1)，则该函数为平衡函数。传统上，需要对该函数进行两次评估才能判断它是其中之一。从量子力学的角度来看，我们可以通过一次评估来回答这个问题。

显示两条水平平行线；左边每一个都标记为 ket(0)；从左到右，每个顶部都有一个标有“X”的框，然后是一个标有“H”的框；继续向左走，有一个框覆盖了标记为“U_f”的两行；此后，下面的行没有标签，上面的行有一个标记为“H”的框，并以一个标记有对角线交叉的圆弧的框结束。

Deutsch 算法的示意图

在最初准备好（Mermin 2007，第 2 章）状态 |0⟩|0⟩ 的计算机的第一个和第二个量子位后，然后使用“非”门（即泡利门）“翻转”这两个量子位（参见上图） X 变换）到 |1⟩，然后使每个量子位服从哈达玛门。然后，通过一个预言机或“黑匣子”发送这两个量子位，将其想象为一个单一门 Uf，代表我们希望确定其特征（恒定或平衡）的函数，我们在其中定义 Uf，以便它接受 |x,y⟩ 等输入到 |x,y⊕f(x)⟩，使得 ⊕ 是模 2 的加法（即异或）。然后，第一个量子位被输入另一个哈达玛门，算法的最终输出（测量之前）是状态：

1

2

|1⟩(|f(0)⟩−|

^

f

(0)⟩)

每当 f 是常数时，并且状态：

1

2

|0⟩(|f(0)⟩−|

^

f

(0)⟩)

每当 f 平衡时，其中

^

f

(x)=1⊕f(x)。由于计算基础状态彼此正交，因此对第一个量子位的单个测量足以检索我们关于函数性质的原始问题的答案。由于 f:{0,1}→{0,1} 存在两个可能的常量函数和两个可能的平衡函数，因此我们可以将该算法描述为仅使用一次预言机调用即可区分两个量子析取，而无需找出析取函数本身的真值，即无需确定 f 是哪个平衡函数或哪个常量函数（Bub 2010）。

Deutsch 问题的推广，称为 Deutsch-Jozsa 问题 (Deutsch & Jozsa 1992)，扩大了所考虑的函数类别，以包括所有函数 f:{0,1}n→{0,1}，即，而不是只考虑n=1。用于确定给定此类函数是否恒定或平衡的最佳确定性经典算法需要

2n

2

+1 对预言机的查询。然而，在量子计算机中，我们可以使用一个预言机调用来回答这个问题。与 Deutsch 的算法一样，一项分析表明，量子计算机只需要一次调用预言机来评估相关函数的全局属性的原因是，计算机的输出状态是平衡状态和恒定状态的叠加，例如平衡状态都位于系统希尔伯特空间的子空间中，该子空间与恒定状态正交，因此可以在一次测量中与后者区分开来（Bub 2006a）。

3.1.3 西蒙算法

假设我们有一个 n 位的布尔函数 f，它是 2 比 1，即，它需要 n 位到 n−1 位，这样对于每个 n 位整数 x1 都有一个 n 位整数 x2，其中f(x1)=f(x2)。此外，该函数是周期性的，因为 f(x1) = f(x2) 当且仅当 x1=x2⊕a，其中 ⊕ 表示按位模 2 加法，a 是一个 n 位非零数，称为周期f.西蒙的问题是找到给定的 f 的问题。相对于单步计算 f 的预言机 Uf，Simon 的量子算法（Simon 1994）在多次预言机调用中找到 f 的周期，该周期仅随 n 的长度线性增长，而最著名的经典算法则需要指数函数预言机调用次数更多。当 n=2 时，Simon 算法简化为 Deutsch 算法，并且可以被视为后者的扩展，因为在这两种情况下，函数的全局属性都在不超过预言机的（子）多项式数中进行评估。调用，因为计算机在最终测量之前的输出状态被分解为正交子空间，其中只有一个子空间包含问题的解决方案。请注意，Deutsch 算法和 Simon 算法之间的一个重要区别是，前者产生确定性的解，而后者仅产生概率非常接近 1 的解。有关这些第一个基于量子电路的算法的逻辑分析的更多信息，请参阅 Bub （2006a）和布布（2010）。

3.1.4 Shor算法

刚刚描述的算法虽然展示了量子相对于经典计算的潜在优越性，但处理的是明显不重要的计算问题。此外，它们每个的加速仅与它们各自的预言机相关。因此，如果肖尔没有意识到西蒙的算法可以用来解决一个更有趣和关键的问题，即因式分解，它是广泛使用的量子计算的核心，那么量子计算的研究是否会在 20 世纪 90 年代引起如此多的关注值得怀疑。加密协议，例如 RSA（Rivest、Shamir 和 Adleman 1978）。肖尔的算法将量子计算变成了量子力学中最令人兴奋的研究领域之一。

Shor 算法利用了巧妙的数论论证，即对于任何不存在任何 y

r

2

≠−1 mod N。这将是联合情况，概率大于

1

2

对于随机选择的任何 y（否则选择 y 的另一个值并重试）。 N 的因子是 y 的最大公约数

r

2

±1 和 N，可以使用众所周知的欧几里德算法在多项式时间内找到。换句话说，肖尔的显着成果在于发现因式分解问题可以简化为求某个周期函数的周期的问题。 Simon 算法暗示了这个问题可以通过量子计算机有效解决，该算法考虑按位模 2 加法下周期函数的更受限制的情况，而不是这里考虑的普通加法下的周期函数。

尽管因式分解被认为只适用于 NP 而不是 NP 完全的（参见 Aaronson 2013a, 64-66），Shor 的结果可以说是已知量子加速的最引人注目的例子。验证 n 是否为素数需要执行 log2n 多项式的多个步骤（自然数 n 的二进制编码需要 log2n 资源）。但没有人知道如何在多项式时间内经典地将数字因式分解为素数，而我们针对此问题拥有的最佳经典算法是次指数算法。许多广泛使用的现代密码协议都是基于这些事实（Giblin 1993），并且量子计算机可以在多项式时间内解决因式分解的发现因此产生了巨大的影响。因此，在可扩展架构上实施该算法将产生经济和科学后果（Alléaume et al. 2014）。

3.1.5 格罗弗算法

在一次出色的卧底行动中，13 号特工成功获得了关于大恶棍齐格弗里德下落的两条关键信息：他打算开始执行 KAOS 统治世界计划的秘密藏身处的电话号码，以及事实上，该号码已列出（显然是齐格弗里德的疏忽）。不幸的是，除此之外，您和您在 CONTROL 的同事没有其他信息。仅使用这个号码和电话簿你能找到齐格弗里德的藏身之处吗？在理论计算机科学中，此任务称为非结构化搜索。在最坏的情况下，如果目录中有 n 个条目，则查找该条目所需的计算资源将与 n 呈线性关系。 Grover (1996) 展示了如何使用量子算法来完成这项任务，使用的计算资源仅为

√

n

。同意，这种加速比 Shor 的加速要小一些，因为非结构化搜索属于 P 类，但与 Shor 的情况相反，分解的经典复杂性仍然未知，这里量子算法的优越性，无论多么小，都是绝对可以证明的。 Bennett、Bernstein、Brassard 和 Vazirani (1997) 证明了这种二次加速也是该问题可能的最佳量子加速。

尽管 Grover 算法的目的通常被描述为“搜索数据库”，但将其描述为“反转函数”可能更准确。粗略地说，如果我们有一个可以在量子计算机上计算的函数 y=f(x)，格罗弗算法允许我们计算给定 y 的 x。函数求逆与搜索数据库有关，因为我们可以想出一个函数，如果 x 与数据库中的所需条目匹配，则生成特定的 y 值，并为 x 的其他值生成另一个 y 值。格罗弗算法的应用影响深远（甚至比挫败齐格弗里德统治世界的计划还要深远）。例如，它可用于有效地确定 N 项搜索问题的解的数量，从而对 NP 完全问题的一类解执行穷举搜索，并显着减少解决该问题所需的计算资源。

3.2 绝热算法

自第一个量子算法被发现以来已经过去了几十年，但迄今为止，在用量子电路解决 NP 完全问题的“圣杯”方面几乎没有取得任何进展。 2000 年，来自麻省理工学院和东北大学的一组物理学家（Farhi 等人，2000 [其他互联网资源]）提出了一种新颖的量子计算范式，该范式在几个有趣的方面不同于电路模型。他们的目标是尝试用该算法来决定最著名的 NP 完全问题之一的实例：可满足性。根据绝热定理（例如，参见 Messiah 1961）并给定某些特定条件，量子系统沿着绝热变换保持在其最低能量状态（称为基态），在绝热变换中系统缓慢而平稳地从初始哈密顿量到最终哈密顿量（例如，考虑将摇篮中熟睡的婴儿从客厅移到卧室。如果过渡足够缓慢且顺利，并且婴儿是声音sleeper，那么它将在整个转换过程中保持睡眠状态）。这个定理中最重要的条件是基态和下一个激发态之间的能隙（在我们的类比中，这个间隙反映了婴儿睡得有多熟）。该间隙与演化时间 T 成反比，控制后者。如果在整个演化过程中存在这种间隙（即系统的能态之间没有能级交叉），则该定理表明在绝热极限（当 T → ∞ 时）系统将保持在基态。当然，在实践中，T总是有限的，但它越长，系统在时间演化过程中偏离基态的可能性就越小。