敲开图灵之门：量子计算和机器学习

零和一。点点滴滴。正面和负面。最重要的是，打开和关闭某些开关。我们都已经习惯了查看和使用现代计算机。每年，诸如英特尔，AMD，ARM和NVIDIA之类的行业巨头都发布下一代的顶级芯片，锁定号角，并推动我们今天所知的传统计算机的发展。

如果我们批判性地评估云上托管的众多新的多核CPU，GPU和庞大的计算集群，我们将很快意识到更快的处理器并不一定会导致计算能力的提高。当然，在过去的几十年中，计算速度呈指数级增长，因此我们可以处理和处理的数据量也呈指数增长。我们可以在互联网上存储和分析EB级数据，训练诸如OpenAI的GPT-3之类的深度学习模型，并提供在Go和Chess等复杂游戏中击败冠军和宗师所需的计算智能。但是，所有这些技术进步是否已使我们从根本上超出了计算机的基本功能？或者简单地说，我们是否改变了传统的计算模型？

现代计算机根据冯·诺依曼架构的原理进行操作（Ogban等，2007）。冯·诺依曼架构利用输入和输出到处理单元，该处理单元基于一组指令对输入执行逻辑功能。

冯·诺依曼体系结构虽然可以以实用的方式解决问题，但它们并未描述计算过程本身。为此，我们需要图灵机（De Mol，2018）。图灵机提供了当今计算机的抽象模型。图灵机根据一组规则来操纵磁带上的符号。然后，磁带将根据机器的当前状态前进或停止。众所周知的事实是，传统计算机今天可以执行的所有计算也可以在图灵机上执行。精明的读者会将这个结果与Church-Turing论文联系起来，该论文指出“任何现实世界的计算都可以使用λ微积分来完成，这等效于使用通用递归函数”（Rabin，2012年）。然而，实际上，对于任何现实的，合理大小的问题，实际的图灵机的速度将太慢。

正如Church-Turing论文所证明的那样，图灵机提供的可计算性是我们没有突破的玻璃天花板。正如我们稍后将讨论的那样，尽管将我们的计算设备基于Turing机器释放了计算的可能性，但是该模型还存在一些固有的缺陷。

但这并不是说所有的东西都丢失了。小马丁·路德·金（Martin Luther King Jr.）曾经说过：“我们必须接受有限的失望，但绝不要失去无限的希望。”打碎这个玻璃天花板不仅需要将大量晶体管包装到计算机芯片上。它需要彻底重新考虑计算机。从他们最基本的单位开始-一点点。

最近的120年也许是物理学史上最大的进步。爱因斯坦的狭义和广义相对论改变了我们对时间，空间和引力的认识，而狄拉克，保利，费曼，薛定er，海森堡和普朗克对量子力学的表述从根本上改变了我们对电子，质子和中子的无穷小世界的理解。 。

这是量子力学中的最新进展，与寻求强大的新型计算模型最直接相关。在1980年代初期，理查德·费曼（Richard Feynman）设想，量子计算机可以提供一种方法来解决当代（或古典）计算机难以解决的指数问题（Feynman，1986）。这是可能的，因为量子计算机要求我们采用根本不同的位概念。在我们进一步深入研究这种计算模式之前，必须定义量子计算机的含义。

与传统计算机具有在任何给定时刻可以处于状态0或1的位不同，量子计算机中的量子位（或简称为qubit）可以处于其他状态。它可以离散状态（0或1）或两种状态的叠加形式存在。这是qubit的固有属性，它为局部性分配了概率分布。

我们的目的不是要提供对量子计算机机壳下发生的量子离心率的解释。然而，值得回顾一下量子物理学的两个基本概念：波粒对偶和纠缠。稍后我们将看到，这些是量子计算机的基础。

量子位的状态可以表示为列向量。不同的状态由不同的列向量表示，其中每个列向量与其余向量正交。对应于量子位的状态由可能状态的线性组合给出，这些状态由复数加权。这等效于说在任何给定时刻，量子位都处于这些基态的叠加或概率波中。在所有这些可能的位置中测量精确位置的动作会使该概率波或波函数崩溃，从而揭示单个状态。这是波粒二象性的症结所在：粒子既表现出波状行为又表现出粒子状行为。在我们明确观察到粒子之前，我们永远无法说出它处于什么状态。哥本哈根解释正式提出了关于粒子在测量之前的位置的询问（Faye，2002）。

要理解的第二个重要原理是量子纠缠。考虑一个粒子系统，每个粒子都有自己的波函数。多个粒子的系统定义为状态空间的张量积。这个k个粒子的张量积，每个粒子由n维列向量表示，具有n have维。状态空间的这种表示称为状态集合。

现在，出于说明目的，让我们将k个粒子的初始系统精简为两个粒子，每个粒子都由a和b（为简单起见，为圆形或正方形）两种状态叠加。我们说，如果有关一个粒子状态的知识不能揭示有关第二个粒子状态的信息，则这两个粒子是独立的。

但是，如果知道一个粒子的状态为我们提供了另一个粒子的状态的直接信息，则可以说这两个粒子是纠缠的。我们多么迅速地获得此信息是最令人费解的实验证明事实之一：无论一对纠缠的粒子之间的距离如何，测量一个粒子的状态都会立即显示有关另一个粒子的信息。这意味着，如果产生两个纠缠的粒子，请将它们带到太阳系的相对两端，使一个粒子的波函数崩溃将立即使另一个粒子的波函数崩溃。两个粒子之间的这种通信速度比光本身的速度快，这导致爱因斯坦本人将其特殊性标记为“远距离的怪异动作”。

沉迷于更深层次的纠缠指令需要一些严格的数学公式，因此在此我们将避免这样做。此外，尽管纠缠以比光更快的速率传输信息，但是纠缠并没有违反局部性。但有关此方面的更多详细信息，请参阅本指南（Wilczek，2016年）。

在实践中，很少遇到独立的粒子，因为系统之间的相互作用会导致纠缠，因为将波函数与具体概率相关联的基础数学将其引入粒子之间的相关性（Joos，2009）。有了这些概念（波粒对偶和量子纠缠），我们脑子里有了新生，让我们看看量子计算机如何巧妙地利用这些现象进行计算。

就像晶体管代表传统计算机中的1位信息一样，半导体材料（如硅树脂或磷）的核自旋也代表了量子位的信息。这些半导电的硅或磷原子通过电场和磁场进行操纵和读取（Vogel，n.d.）（Physics World，2019）。

如前所述，量子位是量子计算机的基本单位。由于qubit不仅可以存在于传统的0和1状态，还可以处于更多状态，因此我们可以使用它们对更多信息进行编码。实际上，可以使用qubit对经典位进行编码，但是反之则不正确。您无法在经典晶体管中编码信息的量子比特。使用位，可以使用n个晶体管对n分量系统进行编码。封装8位经典系统只需要8个存储位。如果将n分量系统改为量子，则需要2个复数对其进行编码（Kopczyk，2018）。通过扩展，对一个8量子位的量子计算机进行编码需要256个复数。要模拟64个量子位，在经典机器上将需要2⁶⁴= 18、446、744、073、709、551、616复数。因此，与经典计算机相比，量子计算提供了更大的势态空间。虽然量子位是一个更大的计算对象，但是需要较少数量的量子位来表示困难的计算问题。而且很明显，这样的表示对于经典计算机而言很难模仿。

就像经典的门（例如AND，OR，XOR）一样，它是对位进行任何运算的基础，量子门以及相应的量子门也会修改qubit的状态。但是，量子计算机具有一系列专用于量子位运算的特殊门。其中有Hadamard和CNOT闸门（Djordjevic，2012年）。 Hadamard门可用于创建状态的叠加（Qiskit / IBM，n.d。），而CNOT门可用于纠缠量子位（Qiskit / IBM，n.d。）。

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

通过巧妙地运用叠加和纠缠原理，量子计算机可以同时计算多个量子位的结果（Kopczyk，2018）。例如，假设我们的量子计算包括在一组输入上应用变换或函数；我们可以将该函数应用于多个输入，并获得其结果。另一方面，经典计算机上的相同操作需要针对每个输入顺序执行或在单独的经典电路中完成。为了说明这一点，由于经典位不会纠缠或重叠，因此需要单独的测量和计算来从它们中提取信息。在量子计算机的情况下，纠缠和叠加使我们能够在一次操作中同时计算有关多个量子位的信息。本质上，这种计算模型使我们能够探索不同的途径并串联执行数学运算。

这是量子计算机提供的关键优势。固有的并行性非常有效，并导致了我们所谓的“指数计算能力”。要使功率增加一倍，我们只需要在电路中再增加一个量子位即可。这一发现导致了新一类算法的开发，称为量子算法，该算法利用量子计算机提供的并行性来获得针对某些类型问题的最优经典解的指数级加速。

量子计算机优于传统计算机的第一个有形演示于2019年首次亮相。Google研究人员使用53位量子计算机Sycamore在200秒内解决了问题。相反，同样的问题将花费大约10,000年的时间来解决现有的经典超级计算机。 Sycamore的结果被正式称为“量子至上性”的展示，这是量子计算范式的一个明显例子，显示出自己比经典的计算方法要强大得多（Arute＆amp; Arya，2019，505-510）。

尽管IBM通过自己的后续论文迅速挑战了Google的主张（Pednault等，2019），但Google的发现（“使用可编程超导处理器的量子优势”）通常被认为是量子计算机发展的突破性时刻。 。

到目前为止，我们仅讨论了量子计算机的积极方面。但是，就其实施和发展而言，并非一帆风顺。事实证明，以叠加状态悬挂qubit非常困难。为了实现稳定性，需要将量子计算机保存在冰箱中，以将量子位冷却至仅略低于绝对零（0 K）的温度。这意味着，至少到目前为止，量子计算机仅限于利基研究领域和昂贵的实验室。

此外，量子位易受噪声（一种称为退相干现象）的影响，这意味着它们会失去相互作用的环境，从而丧失其概率量子行为以及随之而来的存储信息。发生这种情况的原因是，在量子水平上，没有观察或相互作用足够温和，无法同时从系统中提取信息，而且还保留了其原始的未干扰状态。这种相互作用有效地将量子定位，导致状态的有利叠加消失（Bacciagaluppi，2020），这也是我们未能完全实现量子计算机潜力的另一个原因（Kopczyk，2018）。

考虑到它们的局限性，我们正处于研究人员所说的量子计算机的嘈杂中级量子（NISQ）时代。当前一代的量子计算机功能不足以产生容错结果。去相干性还破坏了量子算法的加速优势，从而威胁了其有效性。这就是为什么Shor的算法仍具有理论上的优势，该算法可能通过在多项式时间内对大量数字进行素因子分解来破坏我们现有的加密标准，从而使该算法不稳定。

最重要的是，量子计算机并不是每种计算类型的最佳选择。他们不会对两个数执行基本运算，也不会更快地训练神经网络，并且肯定不会更快地运行日常程序。像IBM这样的公司甚至宣称量子计算机“将永远不会超越经典计算机，而是宁愿与它们合作，因为它们各自都有自己的独特优势”（Pednault＆amp; Gunnels，2019年） ）。

但是，量子计算机擅长存在某些问题，值得讨论。

近年来的研究表明，量子计算的真正潜力在于建立由经典段和量子段组成的流水线。考虑科学应用，我们必须计算粒子的基态。这个问题在研究化学反应和平衡时通常很重要。基态将被定义为粒子处于其最低能级，因此处于其最稳定态的状态。传统上，获得基态需要根据粒子状态的特征向量计算最小的特征值，该特征向量由称为哈密顿量的矩阵表示。对于小型系统，经典计算机不会在解决方案中大汗淋漓，但是对于具有大量粒子并很快使可用计算资源不堪重负的大型系统，此简单任务呈指数增长。

但是，如果我们使用混合的量子机器学习算法，则搜索空间的增加变得难以控制。变分本征求解器（VQE）同时使用经典算法和量子算法来估计哈密顿量的最低特征值。简而言之，它的量子部分（称为ansatz）可以智能地搜索粒子所有可能状态的空间。经典部分通过梯度下降来调整ansatz的参数，以帮助其接近最佳答案。这种结合表明，量子计算机在这类粒子模拟任务中尤其有用。

在过去的几年中，还提出了在量子机器学习框架下的其他各种算法。传统k均值聚类的最著名量子算法对向量之间的Lloyd经典距离计算子例程（Rebollo-Monedero＆amp; Girod，2009）进行了优化，以将经典O（NkM）的计算复杂度按指数级降低至O（Mklog（ N）），其中k是聚类数，M是训练示例的数量，N是特征数量（Biamonte＆amp; Wittek，2017，195-202）。

研究人员还研究了量子计算机在运行神经网络中的作用。尽管在量子领域中仍然需要完善的神经网络公式（Schuld＆amp; Sinayskiy，2014），但学者们已经提出了多种方法来代表具有量子电路的经典神经网络。来自苏黎世联邦理工学院和IBM Q的研究人员就是一个例子，他们比较了经典神经网络和量子神经网络的维数，可优化性和可训练性（Abbas等，2020）。

Abbas等人使用模型的维数来比较不同神经网络的功能。他们的结果表明，与经典神经网络相比，结合“良好”特征图（用于编码数据）的量子神经网络具有更高的有效维数。此外，与经典神经网络不同，经典神经网络有时会因高度退化的Fisher信息矩阵而导致训练缓慢，而上述量子神经网络则提供了更具描述性的Fisher信息矩阵，具有更均匀，非零的特征值。该量子神经网络比IBM 27比特机器上的Iris数据集上的经典神经网络能够更快地训练和收敛。

这些结果表明，具有三个部分（功能映射，变化和测量）的健壮量子神经网络具有诸如高容量和快速可训练性的优势。

量子计算机还擅长优化问题。优化问题利用一种特定的解决方案试探法来从一组有效的解决方案中找到最可能的解决方案。为了了解优化如何在量子计算环境中运行，研究人员针对某些NP难题设计了量子算法。一个例子是旅行商问题（TSP）的量子算法，它为许多城市的经典蛮力方法提供了二次加速（Srinivasan et al。，2018）。

利用量子计算机并行性的其他算法也突出了有希望的结果。 Grover的算法是目前搜索具有N个条目的未排序数据库的最快量子算法。在经典计算机上，此任务将需要与N成正比的时间，但是量子对应物展示了平方根加速，而是以O（sqrt（N））的形式完成了工作。类似地，量子计算机可以对N个数据点执行傅立叶变换，对N * N个稀疏矩阵求逆，并在时间上找到与对数（N）的多项式成比例的特征值和特征向量。对于这些任务，已知的最佳经典算法将花费与Nlog⁡（N）成比例的时间，也就是说，量子计算机在这种情况下也表现出指数级的加速（Biamonte＆amp; Wittek，2017，195-202）。

金融业也在为量子计算机的潜在用例做好准备。分析股票市场及其相关指标的任务可以转换为int

......