量子计算（一）

1. 该领域简史

1.1 物理计算复杂度

1.2 计算的物理“捷径”

1.3 里程碑

2. 基础知识

2.1 量子位

2.2 量子门

2.3 量子电路

3 量子算法

3.1 基于量子电路的算法

3.1.1 预言机

3.1.2 Deutsch算法

3.1.3 西蒙算法

3.1.4 Shor算法

3.1.5 格罗弗算法

3.2 绝热算法

3.3 基于测量的算法

3.4 拓扑量子场论（TQFT）算法

4 实现

5 个哲学问题

5.1 量子计算中的量子是什么？

5.1.1 关于并行性和多世界的争论

5.1.2 加速的难以捉摸的本质

5.2 实验形而上学？

5.3 量子因果关系

5.4 物理科学的（量子）计算视角

5.5 丘奇-图灵论题和多伊奇原理

5.6（量子）计算和科学解释

5.7 有计算类型吗？

参考书目

学术工具

其他互联网资源

相关条目

1. 该领域简史

1.1 物理计算复杂度

通用计算机的数学模型早在量子计算机发明之前就已定义，称为图灵机。它由（a）（在一维）划分为单元的无界磁带组成，（b）一个“读写头”，能够从特定位置的单元读取或向单元写入有限数量的符号之一， (c) 一个指令表（实例化一个转换函数），给定机器的初始“心理状态”（在计算过程中可以访问任意次数的有限数量的这种状态之一）和在该状态下从磁带读取的输入，确定(i) 在当前磁头位置写入磁带的符号，(ii) 磁头随后的位移（向左或向右），以及 (iii) 机器的最终状态。 1936 年图灵 (1936) 表明，由于可以将任何给定图灵机 T 的指令表编码为二进制数 #(T)，因此存在一种通用图灵机 U，在从其磁带读取给定 (T)：后，可以模拟T在任意输入上的操作。

在数学中，一种有效的方法，通俗地说，是一种由有限数量的精确有限长度指令组成的方法，如果人类只使用纸张和数据来精确遵循，则保证在有限数量的步骤中产生一些期望的结果。铅笔（Papayannopoulos 2023）。图灵机模型正式地完整地捕捉了有效可计算性的概念，这是丘奇-图灵论文的精髓。由于该论文既涉及精确的数学概念（即图灵机的概念），又涉及非正式且直观的概念（即有效方法的概念），但严格来说，它不能被证明或反驳，但可以说是最好的考虑作为卡尔纳普意义上的解释（Carnap 1962，第一章）。

简单的基数考虑表明，无论如何，并非所有函数都是图灵可计算的（所有图灵机的集合都是可数的，而从自然数到自然数的所有函数的集合则不是），并且发现了这一点这一事实在 20 世纪 30 年代完全令人惊讶（Davis 1958）。但是，与给定函数是否可以通过图灵机计算的问题（可计算性理论的范围（Boolos、Burgess 和 Jeffrey 2007））一样有趣和重要，这并不是计算机科学家感兴趣的唯一问题。特别是从 20 世纪 60 年代开始（Cobham 1965；Edmonds 1965；Hartmanis & Stearns 1965），计算函数的成本问题也变得非常重要。这种成本也称为计算复杂性，是根据解决当前计算问题所需的物理资源（特别是时间和空间，分别以计算步骤和内存位置给出）来自然衡量的。计算机科学家根据计算问题的成本函数作为输入大小 n（存储输入所需的位数）的函数的方式对计算问题进行分类。可处理的或可有效解决的问题是那些可以在“多项式时间内”解决的问题；即，在由输入大小的多项式函数限制的多个时间步长中，而棘手的问题是那些不能限制的问题，即需要“指数”时间的问题。

对于我们到目前为止讨论的确定性图灵机（DTM）来说，它在任何给定时间的行为完全由它的状态加上它的输入决定。换句话说，此类机器具有独特的转换功能。然而，我们可以通过允许机器同时实例化多个转换函数来推广图灵模型。非确定性图灵机（NTM）在给定状态下提供给定输入时，可以“选择”遵循哪个转换函数，并且我们说，只要给定一些输入，它就解决了给定问题存在至少一条通过其状态空间通向解决方案的路径。 NTM 究竟如何“选择”在给定时刻是否遵循一个转换函数而不是另一个转换函数尚未定义（图灵最初将这些选择视为外部算子的选择）。特别是，我们不假设这些选择附带任何概率。相比之下，在概率图灵机（PTM）中，我们通过将特定概率与其每个可能的转换相关联来描述计算机的选择。

概率图灵机 (DTM) 和确定性图灵机 (DTM) 具有不同的成功标准。针对给定问题的成功的确定性算法保证在给定输入的情况下产生正确的答案。另一方面，对于成功的概率算法，我们只要求它以“高”概率产生正确答案（至少，我们要求它严格大于 1/2）。直到最近，人们普遍认为，对于某些问题（参见 Rabin 1976），概率算法比任何确定性替代方案都更加有效；换句话说，PTM 可有效解决的问题集或“类别”大于 DTM 可有效解决的问题类别。现在普遍认为，事实上，PTM 模型在这个意义上并没有提供比 DTM 模型更好的计算优势（Arora & Barak 2009，第 20 章）。尽管如此，考虑概率（图灵）计算还是很有趣的，因为抽象地讲，量子计算机只是 PTM 的一种变体，它似乎确实比确定性计算提供了计算优势，尽管正如已经提到的，这个猜想仍然有待证明。

P 类（多项式）是包含 DTM 在多项式时间内可以解决的所有计算决策问题的类。 NP 类（非确定性多项式）是包含所有可以通过 NTM 在多项式时间内解决的计算决策问题的类。 [1] NP 中最著名的问题被称为“NP 完全”，其中“完全”指的是这些问题要么都可以处理，要么都不能处理！如果我们知道如何有效地解决 NP 完全问题（即，以多项式成本），我们就可以用它来有效地解决 NP 中的任何其他问题（Cook 1971）。今天，我们知道数百个 NP 完全问题的例子（Garey & Johnson 1979），所有这些问题都可以在不超过多项式减速的情况下彼此简化。由于解决这些问题的最著名的算法都是指数算法，因此人们普遍认为，没有多项式算法可以解决这些问题。显然P⊆NP。然而，证明或反驳 P≠NP 的猜想可能仍然是计算机科学中最重要的悬而未决的问题之一。 BPP（有界概率多项式）类是 PTM 可以在多项式时间内以“高”概率（见上文）解决的问题类。最后，BQP 类是量子计算机可以在多项式时间内以“高”概率解决的问题类。从计算机科学的角度来看，回答量子计算机是否比经典计算机更强大的问题就相当于确定 BPP ⊊ BQP 是否成立（参见 Cuffaro 2018b）。

尽管最初的丘奇-图灵论文涉及可计算性的抽象数学概念，但物理学家和计算机科学家经常将其解释为有关物理计算机器的范围和局限性的说法。 Wolfram (1985) 声称任何物理系统都可以通过通用图灵机来模拟（任何程度的近似），并且图灵机模拟的复杂性界限具有物理意义。例如，如果计算某个由 n 个粒子组成的系统的最小能量至少需要以 n 为指数增加的步数，则该系统实际弛豫到其最小能量状态也将花费指数时间。 Aharonov (1999) 强化了这一论点（在显示其假定的与量子力学不兼容的背景下），她说 PTM 可以以多项式成本模拟任何合理的物理设备。

为了使“物理丘奇-图灵论”有意义，我们必须将物理空间和时间参数与其计算对应参数联系起来：分别是内存容量和计算步骤数。有多种方法可以做到这一点，从而导致论文的不同表述（参见 Copeland 2018；Gandy 1980；Pitowsky 1990；Sieg & Byrnes 1999）。例如，可以将通用图灵机的指令集及其无限磁带的状态编码为单个粒子位置坐标的二进制展开。因此，人们可以在物理上将通用图灵机“实现”为带有双曲镜的台球（Moore 1990；Pitowsky 1996）。

应该强调的是，严格来说，最初的丘奇-图灵论文与其物理版本（Pitowsky & Shagrir 2003）之间没有任何关系，而前者涉及与逻辑相关的计算概念（因为它与逻辑密切相关）需要验证的证明概念），但从分析上来说，它并不意味着所有计算都应该经过验证。事实上，模拟计算有着悠久的历史传统（Dewdney 1984；Maley 2023；Papayannopoulos 2020），并且这些计算的输出通过重复的“运行”或通过验证可能控制模拟行为的物理理论来验证电脑。

1.2 计算的物理“捷径”

是否存在与物理丘奇-图灵理论相矛盾的物理过程？除了模拟计算之外，至少存在两种​​主要的例子，旨在表明递归的概念或图灵可计算性并不是一种自然的物理属性（Hogarth 1994；Pitowsky 1990；Pour-el & Richards 1981）。尽管所涉及的物理系统（分别是三维波动方程的特定初始条件和爱因斯坦场方程的奇异解）有些人为，但“超级计算”学派渴望扩展物理“超级计算机”的有限示例尽管如此，在物理上“计算”非图灵可计算的东西还是出现了（Andréka、Madarász、Németi、Németi 和 Székely） 2018；科普兰 2002，2011；戴维斯 2003）。量子超计算在文献中较少讨论（参见 Adamyan、Calude 和 Pavlov 2004），但可以说，利用量子理论来计算不可计算的最具体尝试是使用量子绝热算法的建议（参见如下）来解决希尔伯特第十问题（Kieu 2002，2004）——一个图灵不可判定问题，相当于停止问题问题——尽管这种所谓的量子绝热超级计算机被批评为非物理的（参见 Hagar & Korolev 2007；Hodges 2005 [其他互联网资源]）。

抛开超级计算机不谈，即使我们仅限于图灵可计算的函数，人们仍然可以在文献中找到许多旨在显示计算资源“捷径”的提议。例如，考虑一下声称可以在多项式时间内解决 NP 完全问题的 DNA 计算模型（Adleman 1994；Lipton 1995）。仔细检查表明，该模型中的计算成本仍然是指数级的，因为物理系统中的分子数量随着问题的规模呈指数级增长。或者使用杆和球的构造对另一个 NP 完全问题采取所谓的瞬时解决方案（Vergis、Steiglitz 和 Dickinson 1986），不幸的是，它忽略了刚性杆中累积的时间延迟，从而导致指数整体减速。看来这些和其他类似的模型不能作为物理丘奇-图灵理论的反例（就复杂性而言），因为它们都需要一些指数级的物理资源。然而请注意，所有这些模型都是使用经典物理学来描述的，因此不可避免的问题是：向量子物理学的转变能否让我们找到计算的捷径？对量子计算机的探索始于对这个问题给出肯定答案的可能性。

1.3 里程碑

早在 1969 年，Steven Wiesner 就提出量子信息处理是更好地完成密码学任务的一种可能方法。但最早发表的四篇关于量子信息的论文（Wiesner 仅于 1983 年发表）属于 Alexander Holevo (1973)、R. P. Poplavskii (1975)、Roman Ingarden (1976) 和 Yuri Manin (1980)。更为人所知的是 IBM Thomas J. Watson 研究中心的 Charles H. Bennett、伊利诺伊州阿贡国家实验室的 Paul A. Benioff、牛津大学的 David Deutsch 和 IBM 的 Richard P. Feynman 在 20 世纪 80 年代初做出的贡献。加州理工学院。当科学家们研究计算的基本物理极限时，这个想法就出现了：如果技术继续遵守“摩尔定律”（英特尔联合创始人戈登·摩尔于 1965 年观察到，每平方英寸集成的晶体管数量自集成电路发明以来，电路每 18 个月就会增加一倍），那么封装在硅芯片上的电路尺寸不断缩小，最终将达到单个元件不大于几个原子的程度。但是，由于在原子尺度上控制假定电路的行为和特性的物理定律本质上是量子力学的，而不是经典的，因此自然而然地出现了一个问题：是否可以基于量子物理原理设计出一种新型计算机。

受到 Ed Fredkin 关于可逆计算的想法（参见 Hagar 2016）的启发，费曼是最早尝试回答这个问题的人之一，他于 1982 年创建了一个抽象模型，该模型展示了如何使用量子系统进行计算。他还解释了这样的机器如何能够充当量子物理的模拟器，并推测任何经典计算机都只能低效地完成相同的任务。 1985年，David Deutsch提出了第一个通用量子图灵机，为量子电路模型（Deutsch 1989）和量子算法的发展铺平了道路。

20 世纪 90 年代，Deutsch-Josza 算法（1992 年）和 Simon 算法（1994 年）被发现。后者为肖尔的因式分解算法提供了基础。该算法于 1994 年发布，标志着量子计算发展的“相变”，甚至在物理学界之外也引起了极大的兴趣。同年，Cirac 和 Zoller (1995) 首次通过实验实现了带有俘获离子的量子 CNOT（受控非）门。 1995年，Peter Shor和Andrew Steane（独立）提出了第一个量子纠错方案。同年，根据 Cirac 和 Zoller 的提议，在科罗拉多州博尔德首次实现了量子逻辑门。 1996 年，贝尔实验室的 Lov Grover 发明了一种量子搜索算法，与经典算法相比，该算法产生了可证明的（尽管只是二次方）“加速”。一年后，第一个基于核磁共振（NMR）技术的量子计算模型被提出。该技术于 1998 年通过 2 量子位寄存器实现，并于 2000 年在洛斯阿拉莫斯国家实验室扩展到 7 量子位。

量子计算的绝热和簇态模型分别于 2000 年和 2002 年被发现（Farhi, Goldstone, Gutmann, & Sipser 2000; Raussendorf & Briegel 2002），2011 年 D-Wave 系统宣布创建“D-Wave one” ，”在 128 量子位处理器上运行的绝热量子计算机系统（Johnson、Amin、吉尔德特等人，2011）。 2010 年代末见证了嘈杂的中规模量子计算 (NISQ) 时代的开始 (Preskill 2018)，2019 年，隶属于 Google LLC 的科学家宣布 (Arute、Arya、Babbush 和合著者 2019)，他们已经实现了“量子计算霸权” ”（Aaronson 2019 [其他互联网资源]）——（在这个案例，NISQ）量子计算机能够解决尚无有效经典算法已知的特定问题 - 至少到 2022 年，发现一种优于 Google LLC 量子计算机的经典算法（Pan，Chen，＆Zhang 2022），更不用说随后的理论结果证明了 Google LLC 方法的固有局限性（Aharonov、Gao、Landau、Liu 和 Vazirani 2023）。尽管自 Shor 算法发现以来该领域取得了巨大的发展，但即使在今天，基本问题仍然悬而未决：（1）理论上，量子算法能否有效解决经典的棘手问题？ （2）在操作上，我们真的可以实现大规模量子计算机来运行这些算法吗？

2. 基础知识

在本节中，我们回顾量子算法的基本范式，即量子电路模型，它包括基本的量子信息单位（量子位）及其基本逻辑操作（量子门）。有关更详细的介绍，请参阅 Nielsen & Chuang (2010) 和 Mermin (2007)。

2.1 量子位

量子位是比特的量子模拟，比特是信息的经典基本单位。它是具有特定属性的数学对象，可以通过多种不同方式在实际物理系统中实现。正如经典位有状态（0 或 1）一样，量子位也有状态。然而与经典比特相反，|0⟩和|1⟩只是量子比特的两种可能状态，并且其任何线性组合（叠加）也是可能的。因此，一般来说，量子位的物理状态是叠加|ψ⟩=α|0⟩+β|1⟩（其中α和β是复数）。量子位的状态可以描述为二维希尔伯特空间中的向量，这是一个复向量空间（参见量子力学条目）。特殊状态 |0⟩ 和 |1⟩ 被称为计算基础状态，并形成该向量空间的标准正交基础。根据量子理论，当我们尝试在此基础上测量量子位以确定其状态时，我们要么以 |α|2 的概率得到 |0⟩，要么以 |β|2 的概率得到 |1⟩。由于|α|2+|β|2=1（即，量子位是上述二维希尔伯特空间中的单位向量），我们可以（忽略整体相位因子）有效地将其状态写为|ψ⟩= cos (θ)|0⟩+eiψsin(θ)|1⟩，其中θ和ψ定义了单位三维球面上的一个点，如下图所示。该球体通常称为布洛赫球体，它提供了一种可视化单个量子位的状态空间的有用方法。

|0⟩

一个球体，|0> 位于北极，|1> 位于南极；从球体中心开始，有 3 个轴，分别标记为 x、y 和 z。 x-y 平面与球体赤道水平相交。通过从 x 轴向 y 轴水平移动角度 phi，然后向 z 轴向上倾斜 psi 来记录球体表面上的任意点。

|1⟩

布洛赫球体

由于 α 和 β 很复杂，因此是连续变量，人们可能会认为单个量子位能够存储无限量的信息。然而，在测量时，它仅产生具有量子态指定的某些概率的经典结果（0 或 1）。换句话说，测量改变了量子位的状态，将其从叠加“折叠”为其一项。事实上，我们可以证明（Holevo 1973），从单个量子位实际可检索的信息量（Timpson (2013, 47ff.) 称之为“可访问信息”）不超过一位。然而，如果不测量量子位，那么它“存储”的“隐藏”信息量（廷普森称之为“规范信息”）在其（单一）动态演化下会被保留。量子力学的这一特征允许人们利用量子门（即酉变换）来操纵存储在未测量的量子位中的信息，并且是量子计算机的推定能力的来源之一。