敲开图灵之门：CS 大四学生长文畅谈量子计算机的「前世、今生、未来」

磐创AI分享

来源 | thegradient.pub

作者 | Ather Fawaz

整理 | 机器之心

编辑 | 陈萍、杜伟

【导读】量子力学的发展已经持续了 100 多年的时间，从 20 世纪 80 年代开始，欧美科学家陆续提出量子计算机的概念。经过几十年的发展，量子计算领域也初步形成了较为完备的体系。但与经典计算机相比，量子计算机的发展仍处于早期阶段。在本文中，一名计算机科学专业的大四学生以洋洋洒洒 6 千余字的篇幅为读者梳理了量子力学、量子计算机以及量子机器学习等领域的发展历程与进展。

零和 1；零零碎碎；阴与阳。最重要的开关，有的开，有的关。我们都已经习惯了使用现代计算机。每年，像英特尔、AMD、ARM 以及英伟达这样的行业巨头都会发布各自的下一代顶级硅芯片，彼此之间竞争角逐，不断挑战传统计算机的极限。

如果我们严格评估这些多核 CPU、GPU 和庞大的云计算集群，则很快就会意识到速度更快的处理器并不一定增加计算能力。说实话，在过去几十年里，计算速度以及能够处理的数据都呈指数级增长。我们可以在网络上存储和分析数兆字节的数据，训练 GPT-3 这样的深度学习模型，并且计算智能可以在围棋和国际象棋等复杂游戏中击败冠军和大师级对手。

但是，所有这些技术的进步是否已经从根本上扩大了我们能够利用计算机做的事情，是否超出了最初利用计算机的范畴？或者简单来说，我们是否已经改变了传统的计算机模式？

现代计算机是根据冯 · 诺依曼结构（Ogban 等人, 2007）的原理运行。冯 · 诺依曼结构利用处理单元的输入和输出，并且该处理单元根据一组指令对输入执行逻辑函数，如下图所示：

虽然冯 · 诺依曼结构非常适合解决实际问题，但它并不能描述计算过程本身。为此，我们需要一台图灵机(De Mol, 2018)。图灵机提供了当今计算机的一个抽象模型，并按照一套规则操作磁带（tape）上的符号，然后磁带根据机器的当前状态前进或停止。

众所周知，传统计算机能够执行的所有计算也都可以在图灵机器上完成。聪明的读者会将这个结果与邱奇 - 图灵论题（Church-Turing thesis）联系起来，该论题表明「任何真实世界的计算都可以使用λ-calculus 来完成，这相当于使用一般递归函数」（Rabin, 2012）。然而，在实践中，对于任何实际的、合理大小的问题来说，图灵机的速度都太慢了。

图灵机示意图。图源：https://web.mit.edu/manoli/turing/www/turing.html

正如邱奇 - 图灵论题所证明的那样，图灵机的计算能力是我们还没有突破的天花板。正如文章后面讨论的那样，尽管基于图灵机的计算设备开启了计算的可能性，但也存在缺点。

然而，这也不是说一切都完了。马丁路德金曾经说过：「我们必须接受有限的失望，但万万不可失去无穷的希望」。打破这种天花板不仅仅是将大量晶体管塞入芯片中，还需要从根本上重新思考计算机，这要从最基本的单元 - 比特开始。

进入量子领域

在过去 120 年里，我们或许取得了物理学历史上最伟大的进步。爱因斯坦的狭义和广义相对论改变了我们对时间、空间和引力的看法，而狄拉克（英国）、泡利（奥地利）、费曼（美国）、薛定谔（奥地利）以及海森堡（德国）和普朗克（德国）的量子力学公式则彻底改变了我们对电子、质子和中子的无限小世界的理解。

1927 年左右的索尔维国际会议（Solvay International Conference）被认为是近代物理学的转折点。图源：https://rarehistoricalphotos.com/solvay-conference-probably-intelligent-picture-ever-taken-1927/

量子力学是这些物理学相关进步中的最后一个，它与寻找强大的新计算模型有着最直接的关联。二十世纪 80 年代早期，费曼设想量子计算机可以提供一种方法来解决当代（或经典）计算机难以解决的指数级问题（费曼, 1986）。这是可能的，因为量子计算机要求我们采用完全不同的比特概念。在我们深入研究这种计算模式之前，必须定义量子计算机的含义。

经典计算机拥有可以在任何给定时刻以 0 或 1 状态存在的比特，而量子计算机中的量子比特（或简称量子位, qubit ）能够以额外的状态存在。量子比特既能够以离散状态（0 或 1）存在，也可以两种状态叠加存在。这是量子比特的一个固有属性，为其自身的定域性（locality）赋予了一个概率分布。

经典比特和量子比特。图源：https://www.cloudtp.com/doppler/what-is-quantum-computing/

本文的目的不是解释量子计算机引擎盖下发生的量子离心率（eccentricities）。然而，值得回顾的是量子物理的两个基础概念：波粒二象性（wave-particle duality）和纠缠（entanglement），它们是量子计算机的基石。

量子力学

量子比特的状态可以用列向量（column vector）表示。不同状态由不同的列向量表示，其中每个列向量与其余向量正交。量子比对应的状态由其他可能的状态线性组合而成，这些可能的状态利用复数加权。也就是说，在任何给定的时刻，量子比特处于这些基态的叠加中，或处在一个概率波（probability wave）中。在所有这些可能的位置中测量一个精确位置的行为会使这个概率波或波函数（wavefunction）崩溃，从而揭示单一状态。

这就是波粒二象性（wave-particle duality）的关键：一个粒子既表现出类波行为又表现出类粒子行为。除非我们明确地观察到一个粒子，否则永远无法说它处于什么状态；哥本哈根诠释（Copenhagen Interpretation）正式提出了一个关于粒子在测量前位置的问题(Faye, 2002)。

波粒二象性。图源：https://www.4piacademy.com/wave-particle-duality/

第二个需要理解的重要原理是量子纠缠（quantum entanglement）。以一个粒子系统为例，每个粒子都有自己的波函数。多粒子系统被定义为状态空间的张量积。这个由 k 个粒子组成的张量积（每个粒子用 n 维列向量表示）被称为具有 n^k 维。这种状态空间的表示被称为状态集合。

现在，为便于说明，让我们把 k 个粒子的初始系统提炼为两个粒子，每个粒子处于两种状态的叠加，a 和 b（为了简单起见，它们可以是圆形或正方形）。如果关于一个粒子状态的知识不能揭示另一个粒子状态的信息，我们就说这两个粒子是相互独立的。

独立粒子。图源：https://www.quantamagazine.org/entanglement-made-simple-20160428/

然而，如果知道一个粒子的状态给了我们关于另一个粒子状态的即时信息，则可以说这两个粒子是纠缠在一起的。不管一对纠缠粒子之间的距离如何，测量一个粒子的状态会在瞬间揭示另一个粒子的信息。这意味着，如果你产生了两个纠缠粒子，把它们带到太阳系的对立两端，一个粒子波函数的坍缩将立即导致另一个粒子波函数的坍缩。两个粒子之间的交流速度比光速还快，爱因斯坦将这种特质总结为「幽灵般的超距作用（spooky action at a distance）。

粒子纠缠。图源：https://www.quantamagazine.org/entanglement-made-simple-20160428/

完全不同的计算模型

就像经典计算机中一个晶体管代表 1 比特信息一样，硅或磷等半导体材料的核自旋代表 1 量子比特信息。这些半导体硅或磷原子通过电场和磁场进行操作和读取（Vogel 于 2019 年发表在 Physics World 期刊上）。

如前所述，量子比特是量子计算机的基本单元。由于量子比特可以存在于比传统 0 和 1 比特更多的状态中，我们可以使用量子比特来编码更多的信息。实际上，使用量子比特对经典比特进行编码是可能的，但反过来就不成立了。你无法用一个经典的晶体管来编码量子比特的信息。对于比特而言，n 个晶体管可以编码 n 组件系统；封装一个 8 比特的经典系统只需要 8 个存储位。

如果 n 组件系统是量子的，则需要 2^n 个复数对其进行编码（Kopczyk, 2018）。推而广之，编码一个 8 量子比特的量子计算机则需要 256 个复数。若要在经典计算机上模拟 64 个量子比特，则需要 2^64=18, 446, 744, 073, 709, 551, 616 个复数。因此，与经典计算机相比，量子计算提供了更大的势态（potential states）空间；虽然量子比特是一个更大的计算对象，但需要更小数量的量子比特来表示困难的计算问题。显然，经典计算机很难模拟这样的表示。

经典的门运算包括 AND、 OR、XOR 等，它们是对比特进行任何操作的基础。与之类似，量子门也通过相应的「量子门」来修改量子比特的状态。然而，量子计算机有一组特定于量子比特运算的特殊门，包括 Hadamard 和 CNOT 门（Djordjevic, 2012）。Hadamard 门可以用来创建态叠加（Qiskit/IBM, n.d.），而 CNOT 门可以用来纠缠量子位（Qiskit/IBM, n.d.）。

量子电路图。图源：https://www.bsc.es/research-development/research-areas/quantum-information/quantum-algorithms

通过量子门，量子计算将从某个接收输入的初始状态开始。从那里，量子计算过渡到最终状态，然后可以对其进行测量以检索特定信息。

应用在量子比特上的可能变换可以使用布洛赫球旋转来表示。

通过巧妙地运用叠加和纠缠原理，量子计算机可以同时计算多个量子比特的结果（Kopczyk, 2018）。例如，假设我们的量子计算需要对一组输入进行转换或使用函数，则可以将该函数应用于多个输入，同时获得它们的结果。另一方面，在经典计算机上，相同的操作需要按照每个输入顺序执行或者采用独立的经典电路完成。

举例来说，由于经典比特没有纠缠或者叠加，因此需要单独的测量和计算来从中提取信息。就量子计算机而言，纠缠和叠加使我们能够在单次操作中同时计算多个量子比特的信息。本质上，这种计算模型允许我们探索不同的路径，并同时执行数学运算。

这是量子计算机提供的关键优势。这种固有的并行性非常有效，我们称之为「指数计算能力」。为了成倍增强计算能力，我们只需要在电路中增加一个量子比特。这一发现促成了「量子算法」的发展，该算法利用量子计算机提供的并行性，在某些问题上获得了相比最优经典求解的指数级加速。

量子计算机的详细概述。图源：https://www.engadget.com/2018-02-23-ibm-q-quantum-computer-experiments.html#/

量子计算机首次超越经典计算机出现在 2019 年。来自谷歌的研究者使用 Sycamore（一个 53 位的量子计算机）在 200 秒内解决了一个问题。相反，同样的问题，经典超级计算机大约 1 万年才能解决。Sycamore 的结果被官方称为「量子优越性」，这是量子计算的典型范式，显示出它比经典计算范式更强大（Arute&Arya, 2019505-510）。

谷歌的 53 量子位量子计算机 Sycamore。(Arute & Arya, 2019, 501-510)

之后，尽管 IBM 的论文研究 (Pednault et al., 2019) 迅速质疑了 Google 的结果，但谷歌的论文《Quantum supremacy using a programmable superconducting processor》通常被认为是量子计算机发展的突破性时刻。

量子计算机的科研道路并非一帆风顺

到目前为止，我们只讨论了量子计算机的积极方面。但就其实现和发展而言，量子计算机的发展并非一帆风顺。事实证明，在叠加状态下悬浮量子比特非常困难。为了实现稳定性，量子计算机需要放在冷藏室，把量子比特冷却到接近绝对零度（0 k）的温度。这意味着，至少到目前为止，量子计算机的使用仅限于小众研究领域和昂贵的实验室。

NISQ 时代典型的量子计算机环境。图源：IBM Q

此外，量子比特容易受到噪声的干扰（这种现象被称为退相干），这意味着它们在相互作用的粒子环境中失去了概率量子行为和存储的信息。出现这种现象是因为在量子层面上，没有任何观察或相互作用能够温和地同时从一个系统中提取信息，但却能保持其原始的未受干扰状态。这种相互作用有效地定域化量子，导致有利的叠加状态消失（Bacciagaluppi, 2020），这也是我们为什么不能完全实现量子计算机潜力的原因（Kopczyk, 2018）。

相干性问题。图源：https://jqi.umd.edu/news/quantum-bit/2013/11/25/coherence-time-survival-quantum-state

考虑到量子计算机的局限性，我们正处在研究人员所说的嘈杂中型量子（Noisy Intermediate-Scale Quantum, NISQ）计算机时代。目前的量子计算机还没有足够的能力产生容错结果。退相干通过破坏量子算法的加速优势影响它们的有效性。由于 Shor 算法在多项式时间内实现大量数字的质因数分解，所以有可能破坏我们现有的加密标准，但该算法仍不失为一种理论进步。

最重要的是，量子计算机并不是所有类型计算机的最佳选择，也存在自己的短板，比如无法更快递完成两个数字的初级运算，训练神经网络也不是毫不费力，也不会更快地运行日常程序。就如 IBM 所称，量子计算机「永远不会统治、超越经典的计算机，但会和经典计算机协同合作，因为每种计算机都有自己独特的优势」。（Pednault & Gunnels, 2019）。

量子机器学习

近年来的研究表明，量子计算的真正潜力在于建立一个由经典段和量子段组成的 pipeline。考虑到科学应用，我们必须计算粒子的基态。这个问题在研究化学反应和平衡时往往非常重要。

基态被定义为粒子处于最低能级时的状态，因此是最稳定的状态。传统上，获得基态需要从粒子状态的本征向量中计算最小的本征值，这些本征向量由称为哈密顿量（Hamiltonian）的矩阵表示。对于小系统来说，经典计算机在求解时不会遇到太大的困难。但是对于拥有大量粒子的大系统来说，这个简单的任务会成指数增长，很快就会耗尽计算机资源。

然而，如果我们使用混合的量子机器学习算法，则能更容易地处理搜索空间的增长。变分量子本征求解器（VQE）使用经典算法和量子算法来估计哈密顿量的最小本征值。简单地说，它的量子部分被称为 ansatz，用于智能地搜索粒子所有可能的状态空间。经典部分用梯度下降调整 ansatz 的参数，使之接近最优解。这种结合已经证明了量子计算机在这类粒子模拟任务中特别有用。

VQE 算法原理图。图源：https://www.researchgate.net/figure/Schematic-representation-of-the-Variational-Quantum-Eigensolver-algorithm-applied-to-the_fig1_312194694

在过去的几年里，量子机器学习领域的各种其他算法也被陆续提出。用于传统 k - 均值聚类的最著名的量子算法优化了向量之间的 Lloyd 经典距离计算子程序（Rebollo-Monedero & Girod, 2009），以将经典的 O（NkM）计算复杂度指数降低到 O（Mklog（N）），其中 k 是聚类的数量，M 是训练示例的数量，N 是特征计数（Biamonte&Wittek, 2017, 195-202）。

研究人员还研究了量子计算机在运行神经网络方面的能力。虽然在量子领域中，神经网络的鲁棒表达（robust formulation）仍然需要很长的路要走（Schuld&Sinayskiy，2014），但学术界已经提出了使用量子电路来表征经典神经网络的各种方法。例如，来自 ETH Zurich 和 IBM Q 的研究人员比较了经典神经网络和量子神经网络的维度、可优化性和可训练性（Abbas 等人, 2020）。

量子神经网络（Abbas et al., 2020）

Abbas 等人使用模型的维度来对比不同神经网络的性能。他们的结果表明，与经典神经网络相比，结合「良好」特征图（用于编码数据）的量子神经网络具有更高的有效维数。此外，经典神经网络有时会由于高度退化的 Fisher 信息矩阵放缓训练速度，而量子神经网络提供了更具描述性的 Fisher 信息矩阵，具有更均匀的非零本征值。在 IBM 27 量子比特机器上，这种量子神经网络相比经典神经网络在 Iris 数据集上具有更快的训练和收敛速度。

量子神经网络训练结果优于传统的神经网络（Abbas et al., 2020）

这些结果表明，具有三段（特征映射、变分和测量）的鲁棒量子神经网络呈现出高容量和快速可训练性等优点。

NP 困难、搜索和蒙特卡罗模拟

量子计算机也擅长解决优化问题。优化问题利用一个特定的启发式解决方案，从一组有效的解决方案中找到最好的解决方案。为了理解量子计算环境下优化是如何运作的，研究人员设计了一些 NP 困难（NP-hard）问题的量子算法。这方面的一个例子是旅行商问题（Traveling-Salesman-Problem, TSP），它为很多城市提供了比经典蛮力方法更高的二次加速（Srinivasan et al., 2018）。

其他利用量子计算机并行性的算法同样取得了很好的效果。Grover 算法是目前搜索 N 个条目的无序数据库的最快量子算法。在经典计算机中，这项任务需要的时间与 N 成比例，但是量子计算机展示出平方根加速并在 O(sqrt(N))内完成任务。同样地，量子计算机可以在 N 个数据点执行傅里叶变换，对稀疏 N*N 矩阵反演，并找到在时间上与 log (N)中多项式成正比的本征值和本征向量。对于这些任务，已知的最佳经典算法需要的时间与 N log⁡(N)成正比，也就是说，量子计算机在这种情况下也表现出指数级的加速(Biamonte & Wittek, 2017, 195-202)。

金融行业也正在为量子计算机的潜在应用做准备。股票市场以及相关指标的分析可以转化为优化问题。考虑到这一点，量子计算机的直接实际应用可能会在金融领域扎根。

西班牙一家银行 BBVA 在 2020 年 7 月发布的一项研究发现，量子计算机可以提高信用评分、现货套利机会，以及加速蒙特卡罗模拟（经济学人, 2020 年）。同样，摩根大通（JPMorgan Chase&Co.）研究部门的负责人 Marco Pistoia 也希望，量子计算机可以通过加速资产定价、挖掘表现更好的投资组合以及改进现有的 ML 算法等措施提高潜在利润。就连高盛（Goldman Sachs）量子研究负责人 William Zeng 也大胆宣称，量子计算机可以革新银行业和金融业（The Economist, 2020）。

纠缠的未来

量子计算机揭示了一种很有前途的计算和解决问题的新方法。对难解问题的指数加速比和多项式时间求解是量子比特量子力学属性的自然后果。这就使得计算模型更接近于量子图灵机的抽象模型。

回到我们最初对图灵机的讨论，量子图灵机是经典图灵机的泛化或量子化，其中磁头和磁带是叠加的。形式上，机器的状态是希尔伯特空间中的量子状态。量子图灵机的磁带是一个无限的「单边磁带」，它代表了叠加的比特。在这种情况下，量子计算是一种酉变换（unitary transformation），其结果由量子测量决定，它将把相干叠加中的「单边磁带」简化为具有可分离正交本征态的经典双边带（Moschovakis, 2003）。

量子图灵机图示。

将这种计算模型与硬件相耦合，谷歌量子优越性的展示被研究界的许多人认为违反了 Church-Turing 理论的扩展，该理论认为这种计算模型应该使用传统图灵机来有效地建模。事实上，Bernstein 和 Vazirani 在 1993 年的一项研究表明量子图灵机与传统图灵机有本质的区别，前者可以解决某些在经典图灵机上需要超多项式时间的问题。

在化学、金融和优化问题上的实际应用也为量子计算机在现实世界中的应用提供了途径。此外，量子神经网络显著的可训练性和维数也为利用量子计算机进行机器学习与深度学习的研究提供了令人兴奋的新途径。

IBM、Intel、Zapata、Amazon 和 Honeywell 等科技公司意识到量子计算机的潜力，都纷纷加大了对其商业应用的投资。用于量子计算机编程的高级语言、框架和库，如 Q#、Qiskit、TensorFlow Quantum 和 Cirq 等，也都在稳步增长。这些框架和它们的教程降低了量子开发的门槛，如果这一趋势能够延续下去，那么我们可以有望在这十年里看到量子计算领域的一系列令人兴奋的新发展。

尽管取得了这些进展，我们仍需要对量子计算机的现状进行批判性的思考。量子比特对退相干的依赖加上其高昂的低温要求对现有的硬件带来了极大的限制。因此，量子计算机是否真的能在实际应用中发挥优越性，可能不是此时此刻要问的正确问题。更紧迫的问题是，我们能否克服 NISQ 时代不切实际的地方。

作者简介：本文作者 Ather Fawaz 为巴基斯坦拉哈尔市 FAST 大学的一名大四学生，主修计算机科学（CS）专业。他的研究兴趣在于深度学习和对抗网络领域，但同样对物理学和数学具有浓厚的兴趣。本文发表在了斯坦福大学人工智能实验室（SAIL）的学生与研究人员于 2017 年始创的数字杂志《Gradient》上。

原文链接：https://thegradient.pub/knocking-on-turings-door-quantum-computing-and-machine-learning/