量子机器学习全文翻译

量子机器学习全文翻译

翻译自17年nature文章

 

 

• 发布时间： 2017年9月14日

量子机器学习

• 雅各布·比亚蒙特（ Jacob Biamonte）
• 彼得Wittek，
• 尼古拉·潘科蒂（ Nicola Pancotti）
• 帕特里克·雷本特斯特（ Patrick Rebentrost）
• 内森·韦伯＆
• 塞思·劳埃德（Seth Lloyd） 

性质 体积 549， 页数195 – 202（2017）引用本文

• 21k次访问

• 317 引文

• 387 高度

• 指标细节

抽象

在计算机功能和算法进步的推动下，机器学习技术已成为查找数据模式的强大工具。量子系统产生的非典型模式被认为无法有效地产生经典系统，因此可以合理地假设量子计算机在机器学习任务上可能会胜过经典计算机。量子机器学习领域探索了如何设计和实现量子软件，该软件可以使机器学习比传统计算机更快。最近的工作产生了量子算法，可以作为机器学习程序的基础，但是硬件和软件方面的挑战仍然很大。

主要

在我们拥有计算机之前很久，人们努力寻找数据模式。托勒密将对恒星运动的观测结果与宇宙的地心模型相匹配，并用复杂的行星轮来解释行星的逆行运动。在16世纪，开普勒分析了哥白尼和布拉赫的数据，揭示了以前隐藏的模式：行星以椭圆形移动，太阳在椭圆的一个焦点处移动。通过对天文学数据进行分析以揭示这种模式，产生了数学技术，例如求解线性方程组的方法（牛顿-高斯），通过梯度下降学习最佳值（牛顿），多项式插值（拉格朗日）和最小二乘拟合（拉普拉斯） 。

二十世纪中叶，数字计算机的建设使数据分析技术得以自动化。在过去的半个世纪中，计算机功能的飞速发展使得线性代数数据分析技术（例如回归分析和主成分分析）得以实现，并导致了更复杂的学习方法（例如支持向量机）。在同一时期，数字计算机的发展和迅速发展催生了新颖的机器学习方法。诸如感知器之类的人工神经网络是在1950年代实现的（参考资料1），只要计算机有能力实现它们。在1960年代至1990年代引入并实施了基于神经网络（例如Hopfield网络和Boltzmann机器）的深度学习和训练方法（例如反向传播）（参考资料2）。在过去的十年中，特别是在过去的五年中，强大的计算机和专用信息处理器相结合，能够实现数十亿权重的深度网络3，并将其应用于非常大的数据集，这表明这种深度学习网络能够识别数据中复杂而微妙的模式。

众所周知，量子力学会在数据中产生非典型模式。诸如深度神经网络之类的经典机器学习方法通​​常具有以下特征：它们既可以识别数据中的统计模式，又可以产生具有相同统计模式的数据：它们可以识别所产生的模式。这种观察表明了以下希望。如果小型量子信息处理器可以产生传统计算机难以计算的统计模式，那么也许它们也可以识别同样难以识别传统的模式。

这种希望的实现取决于能否找到用于机器学习的有效量子算法。量子算法是一组可以解决问题的指令，例如可以确定在量子计算机上执行的两个图是否同构的问题。量子机器学习软件将量子算法用作较大实现的一部分。通过分析量子算法规定的步骤，可以清楚地看到它们有可能在特定问题上胜过经典算法（即减少所需步骤的数量）。这种潜力被称为量子加速。

量子加速的概念取决于人们是采用正式的计算机科学观点（需要数学证明）还是基于现实的有限尺寸设备可以完成的工作的观点（需要有统计优势的可靠统计证据）问题大小的有限范围。对于量子机器学习，经典算法的最佳性能并不总是已知的。这类似于用于整数分解的Shor多项式时间量子算法的情况：没有发现次指数时间经典算法，但是这种可能性没有得到证明。

确定与量子机器学习和经典机器学习相对的缩放优势的方法将取决于量子计算机的存在，这被称为“基准测试”问题。这样的优势可以包括提高分类精度和对经典不可访问系统进行采样。因此，目前使用复杂性理论中的理想化措施来表征机器学习中的量子加速：查询复杂性和门复杂性（请参见专栏1和专栏1表））。查询复杂度衡量的是经典算法或量子算法对信息源的查询数量。如果解决量子问题所需的查询数量少于经典算法所需的查询数量，则会导致量子加速。为了确定门的复杂性，对获得所需结果所需的基本量子运算（或门）的数量进行计数。

表1给定量子机器学习子例程的加速技术

查询和门的复杂性是理想化的模型，可量化解决问题类别所需的资源。在不知道如何将这种理想化映射到现实的情况下，关于真实场景中必要的资源缩放的说法不多。因此，经典机器学习算法所需的资源大部分是通过数值实验来量化的。量子机器学习算法的资源需求在实践中可能同样难以量化。对它们的实际可行性的分析是本次审查的中心主题。

如将在审查中可以看出，有用于机器量子算法学习其表现出量子加速比4，5，6，7。例如，量子基本线性代数子程序（BLAS）-Fourier变换，找到的特征向量和特征值，在其最知名的经典同行求解线性方程组，显示出指数量子加速比8，9，10。这种量子BLAS（qBLAS）可以转化为量子加速器，用于各种数据分析和机器学习算法，包括线性代数，最小二乘拟合，梯度下降，牛顿法，主成分分析，线性，半定和二次编程，拓扑分析和支持向量机9，11，12，13，14，15，16，17，18，19。与此同时，专用量子信息处理器，如量子退火炉和可编程量子光学阵列被很好地匹配深度学习架构20，21，22。尽管尚不清楚在多大程度上可以实现这种潜力，但仍有理由乐观地认为量子计算机可以识别传统计算机无法识别的数据模式。

我们考虑学习机可以是经典的23，24，25，26，27，28，29，30，31，32或量子8，9，11，13，33，34，35，36。它们分析数据可以是由量子感测或测量装置制造古典或量子状态30，37。我们简要讨论了常规机器学习-使用经典计算机在经典数据中查找模式。然后，我们转向量子机器学习，其中量子计算机分析的数据可以是经典数据（最终被编码为量子态），也可以是量子数据。最后，我们简要讨论了使用经典机器学习技术在量子动力学中寻找模式的问题。

 

古典机器学习和数据分析可以分为几类。首先，计算机可用于执行“经典”数据分析方法，例如最小二乘回归，多项式插值和数据分析。机器学习协议可以是有监督的，也可以是无监督的。在监督学习中，训练数据被划分为带标签的类别，例如手写数字的样本以及手写数字应该代表的实际数字，并且机器的工作是学习如何在训练之外为数据分配标签组。在无监督学习中，训练集没有标签，机器的目标是找到训练数据所属的自然类别（例如，互联网上不同类型的照片），然后对训练集之外的数据进行分类。

 

通过对高维向量空间中的向量执行矩阵运算，可以运行多种数据分析和机器学习协议。但是量子力学全都涉及高维向量空间中向量的矩阵运算。

这些方法背后的关键要素是，n个量子位或qubits 的量子状态是2 n维复矢量空间中的矢量。对量子位执行量子逻辑运算或测量，会将相应的状态向量乘以2 n  ×2 n矩阵。通过建立这样的矩阵变换，量子计算机已经示出执行常见线性代数运算，如傅立叶变换38，寻找特征向量和特征值39，并求解线性方程组集超过2个Ñ在时间维向量空间，在多项式Ñ，比最著名的古典音乐快几倍8。后者通常称为Harrow，Hassidim和Lloyd（HHL）算法 8（请参见专栏2）。原始变体假定条件良好的矩阵稀疏。稀疏不太可能在数据的科学，但是后来改进放宽这一假设包括低秩矩阵，以及 10，33，40。超越HHL，在这里我们考察了几种量子算法，这些量子算法在量子机器学习软件中采用线性代数技术时会作为子例程出现。

 

• 发布时间： 2017年9月14日

量子机器学习

• 雅各布·比亚蒙特（ Jacob Biamonte）
• 彼得Wittek，
• 尼古拉·潘科蒂（ Nicola Pancotti）
• 帕特里克·雷本特斯特（ Patrick Rebentrost）
• 内森·韦伯＆
• 塞思·劳埃德（Seth Lloyd） 

性质 体积 549， 页数195 – 202（2017）引用本文

• 21k次访问

• 317 引文

• 387 高度

• 指标细节

抽象

在计算机功能和算法进步的推动下，机器学习技术已成为查找数据模式的强大工具。量子系统产生的非典型模式被认为无法有效地产生经典系统，因此可以合理地假设量子计算机在机器学习任务上可能会胜过经典计算机。量子机器学习领域探索了如何设计和实现量子软件，该软件可以使机器学习比传统计算机更快。最近的工作产生了量子算法，可以作为机器学习程序的基础，但是硬件和软件方面的挑战仍然很大。

主要

在我们拥有计算机之前很久，人们努力寻找数据模式。托勒密将对恒星运动的观测结果与宇宙的地心模型相匹配，并用复杂的行星轮来解释行星的逆行运动。在16世纪，开普勒分析了哥白尼和布拉赫的数据，揭示了以前隐藏的模式：行星以椭圆形移动，太阳在椭圆的一个焦点处移动。通过对天文学数据进行分析以揭示这种模式，产生了数学技术，例如求解线性方程组的方法（牛顿-高斯），通过梯度下降学习最佳值（牛顿），多项式插值（拉格朗日）和最小二乘拟合（拉普拉斯） 。

二十世纪中叶，数字计算机的建设使数据分析技术得以自动化。在过去的半个世纪中，计算机功能的飞速发展使得线性代数数据分析技术（例如回归分析和主成分分析）得以实现，并导致了更复杂的学习方法（例如支持向量机）。在同一时期，数字计算机的发展和迅速发展催生了新颖的机器学习方法。诸如感知器之类的人工神经网络是在1950年代实现的（参考资料1），只要计算机有能力实现它们。在1960年代至1990年代引入并实施了基于神经网络（例如Hopfield网络和Boltzmann机器）的深度学习和训练方法（例如反向传播）（参考资料2）。在过去的十年中，特别是在过去的五年中，强大的计算机和专用信息处理器相结合，能够实现数十亿权重的深度网络3，并将其应用于非常大的数据集，这表明这种深度学习网络能够识别数据中复杂而微妙的模式。

众所周知，量子力学会在数据中产生非典型模式。诸如深度神经网络之类的经典机器学习方法通​​常具有以下特征：它们既可以识别数据中的统计模式，又可以产生具有相同统计模式的数据：它们可以识别所产生的模式。这种观察表明了以下希望。如果小型量子信息处理器可以产生传统计算机难以计算的统计模式，那么也许它们也可以识别同样难以识别传统的模式。

这种希望的实现取决于能否找到用于机器学习的有效量子算法。量子算法是一组可以解决问题的指令，例如可以确定在量子计算机上执行的两个图是否同构的问题。量子机器学习软件将量子算法用作较大实现的一部分。通过分析量子算法规定的步骤，可以清楚地看到它们有可能在特定问题上胜过经典算法（即减少所需步骤的数量）。这种潜力被称为量子加速。

量子加速的概念取决于人们是采用正式的计算机科学观点（需要数学证明）还是基于现实的有限尺寸设备可以完成的工作的观点（需要有统计优势的可靠统计证据）问题大小的有限范围。对于量子机器学习，经典算法的最佳性能并不总是已知的。这类似于用于整数分解的Shor多项式时间量子算法的情况：没有发现次指数时间经典算法，但是这种可能性没有得到证明。

确定与量子机器学习和经典机器学习相对的缩放优势的方法将取决于量子计算机的存在，这被称为“基准测试”问题。这样的优势可以包括提高分类精度和对经典不可访问系统进行采样。因此，目前使用复杂性理论中的理想化措施来表征机器学习中的量子加速：查询复杂性和门复杂性（请参见专栏1和专栏1表））。查询复杂度衡量的是经典算法或量子算法对信息源的查询数量。如果解决量子问题所需的查询数量少于经典算法所需的查询数量，则会导致量子加速。为了确定门的复杂性，对获得所需结果所需的基本量子运算（或门）的数量进行计数。

表1给定量子机器学习子例程的加速技术

全尺寸表

查询和门的复杂性是理想化的模型，可量化解决问题类别所需的资源。在不知道如何将这种理想化映射到现实的情况下，关于真实场景中必要的资源缩放的说法不多。因此，经典机器学习算法所需的资源大部分是通过数值实验来量化的。量子机器学习算法的资源需求在实践中可能同样难以量化。对它们的实际可行性的分析是本次审查的中心主题。

如将在审查中可以看出，有用于机器量子算法学习其表现出量子加速比4，5，6，7。例如，量子基本线性代数子程序（BLAS）-Fourier变换，找到的特征向量和特征值，在其最知名的经典同行求解线性方程组，显示出指数量子加速比8，9，10。这种量子BLAS（qBLAS）可以转化为量子加速器，用于各种数据分析和机器学习算法，包括线性代数，最小二乘拟合，梯度下降，牛顿法，主成分分析，线性，半定和二次编程，拓扑分析和支持向量机9，11，12，13，14，15，16，17，18，19。与此同时，专用量子信息处理器，如量子退火炉和可编程量子光学阵列被很好地匹配深度学习架构20，21，22。尽管尚不清楚在多大程度上可以实现这种潜力，但仍有理由乐观地认为量子计算机可以识别传统计算机无法识别的数据模式。

我们考虑学习机可以是经典的23，24，25，26，27，28，29，30，31，32或量子8，9，11，13，33，34，35，36。它们分析数据可以是由量子感测或测量装置制造古典或量子状态30，37。我们简要讨论了常规机器学习-使用经典计算机在经典数据中查找模式。然后，我们转向量子机器学习，其中量子计算机分析的数据可以是经典数据（最终被编码为量子态），也可以是量子数据。最后，我们简要讨论了使用经典机器学习技术在量子动力学中寻找模式的问题。

方框1：量子加速

量子计算机以量子相干和纠缠等效应来处理信息，而传统计算机则无法做到。在过去的二十年中，在构建更强大的量子计算机方面取得了稳步进展。量子算法是在量子计算机上执行的用于解决问题（例如搜索数据库）的逐步过程。量子机器学习软件利用量子算法来处理信息。解决某些问题时，量子算法原则上可以胜过最著名的经典算法。这被称为量子加速105。

For example, quantum computers can search an unsorted database with N entries in time proportional to √N—that is, O(√N)—where a classical computer given blackbox access to the same database takes time proportional to N: thus the quantum computer exhibits a square-root speedup over the classical computer. Similarly, quantum computers can perform Fourier transforms over N data points, invert sparse N × N matrices, and find their eigenvalues and eigenvectors in time proportional to a polynomial in log2N, where the best known algorithms for classical computers take time proportional to N log 2 N：因此，量子计算机比最佳的经典计算机算法展现出指数级的加速。

在框1表，加速比采取相对于它们的经典对应物（S） -因此，Ô（√ Ñ）指二次加速和ø（日志（Ñ））指相对于它们的经典对应的指数。

显示更多从这个盒子里

经典机器学习

古典机器学习和数据分析可以分为几类。首先，计算机可用于执行“经典”数据分析方法，例如最小二乘回归，多项式插值和数据分析。机器学习协议可以是有监督的，也可以是无监督的。在监督学习中，训练数据被划分为带标签的类别，例如手写数字的样本以及手写数字应该代表的实际数字，并且机器的工作是学习如何在训练之外为数据分配标签组。在无监督学习中，训练集没有标签，机器的目标是找到训练数据所属的自然类别（例如，互联网上不同类型的照片），然后对训练集之外的数据进行分类。

基于线性代数的量子机器学习

通过对高维向量空间中的向量执行矩阵运算，可以运行多种数据分析和机器学习协议。但是量子力学全都涉及高维向量空间中向量的矩阵运算。

这些方法背后的关键要素是，n个量子位或qubits 的量子状态是2 n维复矢量空间中的矢量。对量子位执行量子逻辑运算或测量，会将相应的状态向量乘以2 n  ×2 n矩阵。通过建立这样的矩阵变换，量子计算机已经示出执行常见线性代数运算，如傅立叶变换38，寻找特征向量和特征值39，并求解线性方程组集超过2个Ñ在时间维向量空间，在多项式Ñ，比最著名的古典音乐快几倍8。后者通常称为Harrow，Hassidim和Lloyd（HHL）算法 8（请参见专栏2）。原始变体假定条件良好的矩阵稀疏。稀疏不太可能在数据的科学，但是后来改进放宽这一假设包括低秩矩阵，以及 10，33，40。超越HHL，在这里我们考察了几种量子算法，这些量子算法在量子机器学习软件中采用线性代数技术时会作为子例程出现。

方框2：HHL算法

用于方程组求逆的HHL算法是一个基本且易于理解的子例程，它是许多量子机器学习算法的基础。该算法试图使用量子计算机来求解A x  =  b。HHL通过将向量表示为log 2 N个量子比特上的量子状态，并将向量x表示为量子状态来量化问题。可以假定矩阵A为Hermitian，而不会失去一般性，因为可以始终扩展该空间以使其成立。方程式然后可以通过由等式的两边乘以要解决甲-1，其中甲-1是A的倒数。然后HHL算法允许人们构造与γ成正比的量子态。更一般而言，当A不是正方形或具有零特征值时，该算法可用于查找最小化9 的状态。

该算法的工作原理如下。假设其中是的本征向量阿与本征值λ Ñ  ≥  Λ。通过下施加相位估计阿到计算λ Ñ并通过反正弦的（角度旋转辅助量子位Λ / λ Ñ），然后uncomputing相位估计我们得到：

If the ancillary qubit is measured and if 1 is observed then each eigenstate is divided through by λn, which affects the inverse. The number of times that the state preparation circuit needs to be applied to succeed, after applying amplitude amplification, is , which is the condition number for the matrix.

The HHL algorithm takes O[(logN)2] quantum steps to output , compared with the O(NlogN) steps required to find x using the best known method on a classical computer.

There are several important caveats to the HHL algorithm. First, finding the full answer x from the quantum state  requires O(N) repetitions to reconstruct the N components of x. Generalizations to HHL, such as least-squares fitting, sidestep this problem by allowing the output to have many fewer dimensions than the input. In general, however, HHL can provide only features of the data such as moments of the solution vector or its expectation value  over other sparse matrices B. The second caveat is that the input vector 需要在量子计算机上或使用qRAM进行准备，这可能很昂贵。第三个警告是，矩阵必须条件良好，并且必须有可能有效地模拟e - iA。最后，尽管HHL算法的缩放比例为O [（log N）2 ]，但当前针对实际问题的算法成本估算是令人望而却步的109，这突出了研究进一步改进10的重要性。通常，应意识到线性系统仅适用于某些问题，以实现指数级加速的承诺。

显示更多从这个盒子里

量子主成分分析

例如，考虑主成分分析（PCA）。假设数据以矢量的形式呈现v Ĵ在d维向量空间，其中d = 2 Ñ = Ñ。例如，v j可以是股票从时间t j到时间t j +1的所有股票价格变化的向量。数据的协方差矩阵为，其中上标T表示转置操作：协方差矩阵汇总了数据不同组成部分之间的相关性，例如，不同股票价格变化之间的相关性。最简单的形式是，主成分分析通过对角协方差矩阵进行运算：，其中c k是C的特征向量，而e k是相应的特征值。（由于C是对称的，所以特征向量c k形成正交集。）如果仅一些特征值c k的特征向量大，而其余的数目小或为零，则与这些特征值相对应的特征向量称为C的主分量。每个主成分代表数据中潜在的共同趋势或相关形式，并且根据主成分v  =  分解数据向量v既可以压缩数据的表示形式，又可以预测未来的行为。就计算复杂度和查询复杂度而言，用于执行PCA的经典算法的标度为O（d 2）。（我们注意到，我们使用“ big O”表示法来跟踪主导扩展的主导术语。）

对于经典数据11的量子主成分分析，我们随机选择一个数据向量v j，并使用量子随机存取存储器（qRAM）41将该向量映射为量子状态：。概括向量的量子状态具有log d个量子位，并且qRAM的操作需要除以O（log d）个步骤可以并行执行的O（d）个操作。由于v j是随机选择的，因此得到的量子态具有密度矩阵，其中N是数据矢量的数量。与协方差矩阵比较对于经典数据C，我们看到数据量子版本的密度矩阵实际上是协方差矩阵，直到总因子为止。通过重复采样数据，并且使用称为密度矩阵幂特技42与量子相位估计算法相结合39，其中发现矩阵的特征向量和特征值，就可以采用任何的数据向量的量子版本并将其分解成主成分，同时揭示C的特征值：。然后可以通过对C的本征向量的量子表示进行测量来探究C的主要成分的特性。量子算法在计算复杂度和查询复杂度上均缩放为O [（log N）2 ]。也就是说，量子PCA的效率比经典PCA高出几倍。

 

量子支持向量机和内核方法

监督机器学习算法的最简单示例是线性支持向量机和感知器。这些方法试图在数据集中的两类数据之间找到最佳的分离超平面，从而很可能仅在超平面的一侧找到一类的所有训练示例。当超平面和数据之间的余量最大化时，将给出针对数据的最鲁棒的分类器。在这里，训练中学习的“权重”是超平面的参数。支持向量机的最大能力之一是通过核函数43将其推广到非线性超曲面。这样的分类器已经在图像分割以及生物科学中获得了巨大的成功。

像它的经典对应物一样，量子支持向量机是量子机器学习算法13的范例。第一个量子支持向量机在2000年代初44进行了讨论，它使用了Grover搜索功能最小化的方法45。因此从N个向量中找到s个支持向量迭代。最近，开发了最小二乘量子支持向量机，该机利用了qBLAS子例程的全部功能。数据输入可以来自各种来源，例如来自访问经典数据的qRAM或来自准备量子状态的量子子例程。一旦将数据提供给量子计算设备，就用量子相位估计和矩阵求逆（HHL算法）对其进行处理。原则上，构造最优分离超平面并测试矢量是位于一侧还是另一侧所需的所有操作都可以在log N多项式时间上执行，其中N是准备量子所需的矩阵维数超平面向量的版本。多项式13讨论了径向基函数核和径向基函数核46，以及另一种基于核的方法，称为高斯过程回归47。这种用于量子支持机的方法已经在核磁共振试验台上进行了手写数字识别任务48的实验验证。

 

 

基于qBLAS的优化

许多数据分析和机器学习技术都涉及优化。越来越多的兴趣是使用D-Wave处理器通过量子退火解决组合优化问题。一些优化问题也可以表述为线性系统的单次求解，例如受等式约束的二次函数优化，二次规划问题的子集。如果涉及的矩阵是稀疏的或低秩的，则可以及时解决这些问题，即log d中的多项式，其中d是通过HHL矩阵求逆算法得到的系统维数，相对于经典算法，它的指数提速时间是是d中的多项式。

机器学习中的大多数方法都需要对其性能进行迭代优化。例如，不等式约束通常通过罚函数49和梯度下降或牛顿法的变化来处理。量子PCA方法的一种修改实现了迭代梯度下降和牛顿法用于多项式优化，并且可以再次提供比经典方法19更快的指数加速。以量子态编码的本溶液的多个副本用于在每个步骤中改进该溶液。Brandao和Svore提供了半定式编程的量子版本，该版本支持超多项式加速的可能性18。量子近似优化算法（QAO算法）50 提供了一种独特的方法，可以根据问题的罚函数应用交替的量子位旋转进行优化。

 

将经典数据读入量子机器

必须先输入经典数据，然后才能在量子计算机上对其进行处理。这个“输入问题”通常开销很小，但是对于某些算法可能会带来严重的瓶颈。同样，在量子设备上处理数据后读取数据时也会遇到“输出问题”。像输入问题一样，输出问题通常会导致明显的运行速度下降。

特别是，如果我们希望将HHL，最小二乘拟合，量子主成分分析，量子支持向量机和相关方法应用于经典数据，则该过程首先需要将大量数据加载到量子系统中，这可能需要指数时间51。原则上可以使用qRAM来解决此问题，但这样做的代价可能会导致大数据问题52望而却步。除了基于组合优化的方法外，唯一不依赖大规模qRAM的，基于线性代数的量子机器学习算法是用于执行数据拓扑分析（持久同源性）的量子算法14。除了最小二乘拟合和量子支持向量机以外，基于线性代数的算法也可能会遇到输出问题，因为所需的经典量（例如HHL的解向量或PCA的主分量）难以指数地估算。

尽管有可能实现指数级量子加速，但在优化上不花太多精力，电路尺寸和电路深度开销仍会迅速增加（在HHL 53的一种拟议实现中，大约10 25个量子门）。需要持续的工作来优化此类算法，提供更好的成本估算，并最终了解我们将需要提供的经典量子计算机替代经典机器学习所需的那种量子计算机。

 

深度量子学习

经典的深度神经网络是用于机器学习的高效工具，非常适合激发深度量子学习方法的发展。专用量子信息处理器，如量子退火炉和可编程光子电路非常适合用于构造深量子学习网络21，54，55。可以量化的最简单的深度神经网络是Boltzmann机器（请参见方框3和方框3图）。经典的Boltzmann机器由具有可调相互作用的钻头组成：通过调整这些相互作用来训练Boltzmann机器，以使钻头的热统计数据由Boltzmann–Gibbs分布描述（见图1b）。），再现数据的统计信息。要量化玻尔兹曼机，只需简单地将神经网络表示为与相互作用的伊辛模型相对应的一组相互作用的量子自旋。然后，通过将Boltzmann机器中的输入神经元初始化为固定状态并使系统热化，我们可以读出输出量子位以获得答案。

 

深度量子学习的一个基本特征是它不需要大型的通用量子计算机。量子退火器是专用的量子信息处理器，与通用的量子计算机相比，它更易于构建和扩展（参见图1a）。量子退火器非常适合于实现深度量子学习器，并且可以通过商业途径获得。D-Wave量子退火炉是一个可调的横向伊辛模型，可以对其进行编程以产生经典系统和某些量子自旋系统的热态。D-Wave设备已用于在超过一千个自旋56上执行深度量子学习协议。量子玻尔兹曼机22具有更通用的可调谐耦合器，能够实现通用量子逻辑，目前处于设计阶段57。片上硅波导已被用于构建具有数百个可调谐干涉仪的线性光学阵列，并且专用超导量子信息处理器可用于实现量子近似优化算法。

量子计算机可以在这里提供多种优势。首先，量子方法可以使系统二次热化快于它的古典对应20，58，59，60。这样可以对完全连接的Boltzmann机器进行准确的培训。其次，量子计算机可以通过提供改进的采样方式来加速Boltzmann训练。由于玻耳兹曼机器中的神经元激活模式是随机的，因此需要多次重复来确定成功概率，进而发现改变神经网络权重对深层网络性能的影响。相反，在训练量子Boltzmann机器时，量子相干性可以二次减少学习所需任务所需的样本数量。此外，对训练数据的量子访问（即qRAM或量子黑盒子例程）使机器可以使用对训练数据的访问请求，比传统方法所需的访问请求少二次：20。

量子信息处理为深度学习提供了新的，基本上是量子的模型。例如，添加的横向场的伊辛模型量子波尔兹曼机可以诱导各种量子效应，如隧道22，61。添加另外的量子联轴器变换量子波尔兹曼机到各种量子系统57，62。在可调谐的伊辛模型中添加可调谐的横向相互作用对于全量子计算来说是普遍的57：通过适当的权重分配，该模型可以执行通用量子计算机可以执行的任何算法。这样的通用深度量子学习者可以识别和分类传统计算机无法做到的模式。

与经典的玻尔兹曼机不同，量子玻尔兹曼机输出量子态。因此，深量子网络可以学习生成代表多种系统的量子状态，从而允许网络充当量子关联存储器63的形式。经典机器学习缺乏这种产生量子态的能力。因此，量子玻尔兹曼训练的应用范围不仅限于对量子态进行分类，还提供了更丰富的经典数据模型。

 

用于量子数据的量子机器学习

量子机器学习最直接的应用也许是量子数据，即量子系统和过程所产生的实际状态。如上所述，许多量子机器学习算法通过将经典数据映射到量子力学状态，然后使用基本的量子线性代数子例程来操纵这些状态，从而找到经典数据中的模式。这些量子机器学习算法可以直接应用于光和物质的量子态，以揭示其潜在的特征和模式。所得的量子分析模式通常比对量子系统中数据进行的经典分析更加有效和更具启发性。例如，给定一个N × N描述的系统的多个副本与经典设备在A上执行层析成像所需的O（N 2）测量相比，密度主矩阵可以使用量子主成分分析来找到其特征值并揭示时间O [（log N）2 ]中对应的特征向量。密度矩阵，以及执行经典PCA所需的O（N 2）操作。量子数据的这种量子分析可以在相对较小的量子计算机上进行，这可能会在未来几年内实现。

一种特别强大的量子数据分析技术是使用量子模拟器来探测量子动力学。量子模拟器是“量子模拟计算机”，即可以对其动力学进行编程以匹配某些所需量子系统的动力学的量子系统。量子模拟器可以是构造为模拟特定类别的量子系统的专用设备，也可以是通用量子计算机。由受信任的量子模拟器连接到未知系统和调整模拟器以抵消未知动力学的模型，未知系统的动态特性可以有效地使用近似贝叶斯推理得知64，65，66。这成倍地减少了执行仿真所需的测量次数。类似地，通用量子仿真器算法67允许人们重建量子动力学，而ref的量子Boltzmann训练算法。图61允许在希尔伯特空间的维度上以时间对数的方式重建状态，这比通过经典的层析X射线摄影术重建动力学成指数地快。

要使用一台量子计算机，帮助检定量子系统65，66或接受输入状态，在量子PCA算法的使用，我们必须面对装载相干输入状态的大量技术挑战。然而，因为这样的应用程序不需要qRAM并为指数的加速潜力器件特性22，61，65，66，他们仍然是量子机器学习的近期应用前景广阔的可能性之一。

设计和控制量子系统

量子计算和信息科学发展中的主要挑战涉及调整量子门以匹配量子误差校正所需的严格要求。启发式搜索方法可以有助于实现这一目标的监督学习的场景68，69（例如，在的情况下，最近邻耦合的超导人造原子69与在噪声存在99.9％以上的栅极保真度），并且因此将达到一个接受容错量子计算的阈值。相似的方法已成功构建了单次Toffoli门，再次达到99.9％70以上的门保真度。遗传算法已被用来减少量子门71中的数字和实验误差。它们已用于通过辅助量子位和不完善的门来模拟受控NOT门。除了性能优于数字量子模拟的协议外，已经证明遗传算法也可用于抑制门72中的实验误差。另一种方法是使用随机梯度下降和两体相互作用将Toffoli门嵌入到一系列量子操作或门中，而无需使用时间依赖的量子网络73的自然动力学进行控制。动态解耦序列有助于保护量子态免受退相干，这可以使用递归神经网络74进行设计。

控制量子系统同样重要和复杂。学习方法在开发控制序列以优化自适应量子计量学方面也非常成功，这是许多量子技术中的关键量子构件。已经提出了用于控制量子分子的遗传算法，以克服由于在实验过程中改变环境参数而引起的问题75。强化学习采用启发式全局优化算法，如用于设计电路的算法，得到了广泛的成功，特别是在噪声和退相干的情况下，与该系统的尺寸缩放以及76，77，78。人们还可以在基于门的量子系统中利用强化学习。例如，基于智能代理的量子信息自适应控制器展示了针对固定方向未知量级外部杂散场的自适应校准和补偿策略。

古典机器学习也是一种强大的工具，可用于提取有关量子态的理论见解。神经网络最近被部署来研究凝聚态两个中心问题，即相的事项检测79，80和基态搜索81。这些成功实现了比已建立的数值工具更好的性能。理论物理学家现在正在研究这些模型，以与传统方法（例如张量网络）相比，分析地了解其描述能力。对奇异状态的有趣应用已经在市场上，并且已经显示出从无序或拓扑有序的系统中捕获非常重要的特征。

对未来工作的看法

正如我们在这条已经讨论的，小的量子计算机和较大专用量子模拟器，退火炉等似乎有在机器学习和数据分析的潜在用途15，21，22，36，48，82，83，84，85，86，87，88，89，90，91，92，93，94，95。但是，量子算法的执行需要尚不可用的量子硬件。

在硬件方面，几种使能技术取得了长足的进步。通过量子云计算（“ Qloud”）将广泛提供具有50–100量子位的小型量子计算机。特殊用途的量子信息处理器，例如量子模拟器，量子退火器，集成光子芯片，氮空位中心（NV）金刚石阵列，qRAM和按订单生产的超导电路，将继续在尺寸和复杂性上发展。量子机器学习提供了一套潜在应用为小量子计算机23，24，25，26，27，28，29，30，31，96，97，98通过专用量子信息处理器的补充和增强的21，22，数字处理器量子70，73，78，99，100和传感器76，77，101。

尤其是，使用集成的超导电路，其原理上是可扩展的，已经构建并运行了约2,000量子比特的量子退火器。量子退火器实现量子机器学习算法的最大挑战包括改善连接性和在量子位之间实现更通用的可调耦合。使用硅中集成的光子器件已经构造了具有约100个可调干涉仪的可编程量子光学阵列，但是随着这种电路规模的扩大，量子效应的损失也会增加。量子机器学习的一个特别重要的挑战是接口设备（如qRAM）的构造，该接口设备允许经典信息以量子力学形式52进行编码。一个qRAM访问N多条数据由2个N个量子开关的分支阵列组成，该分支阵列在内存调用期间必须一致地运行。原则上，这种qRAM需要花费时间O（log N）来执行存储调用，并且每次切换操作最多可以容忍O（1 / log N）的错误率，其中log N是qRAM电路的深度。已经进行了qRAM的原理证明，但是构造大型量子开关阵列是一个困难的技术问题。

这些硬件挑战本质上是技术性的，并且存在克服这些挑战的明确途径。但是，如果要将量子机器学习变成量子计算机的“杀手级应用”，则必须克服这些问题。如前所述，已经确定的大多数量子算法都面临许多限制其适用性的警告。我们可以将上述注意事项归纳为四个基本问题。

1. 1个

   输入问题。尽管量子算法可以极大地提高处理数据的速度，但很少能提供读取数据的优势。这意味着在某些情况下，输入中的读取成本可以控制量子算法的成本。了解这一因素是一个持续的挑战。

2. 2

   输出问题。要从某些量子算法中获得完整的解决方案作为一串位，需要学习指数数量的位。这使得量子机器学习算法的某些应用不可行。通过仅了解解决方案状态的摘要统计信息，可以潜在地避开此问题。

3. 3

   成本问题。与输入/输出问题密切相关，目前对量子机器学习算法所需门的真实数目了解甚少。复杂性的界限表明，对于足够大的问题，它们将提供巨大的优势，但仍不清楚何时出现交叉点。

4. 4

   基准测试问题。在实践中通常很难断言量子算法比所有已知的经典机器算法都要好，因为这将需要针对现代启发式方法进行广泛的基准测试。为量子机器学习建立下界将部分解决这个问题。

为了避免其中的一些问题，我们可以将量子计算应用于量子数据，而不是经典数据。其中的一个目的是使用量子机器学习来表征和控制量子计算机66。这将实现类似于传统计算中出现的创新的良性循环，其中，然后利用每一代处理器来设计下一代处理器。我们已经开始看到这个周期与传统机器学习的第一批成果被用来提高量子处理器设计23，24，25，26，27，28，29，30，31，102，103，104，而这又为量子增强机器学习应用程序本身提供强大的计算资源 8，9，11，13，33，34，35，36。

 

 

量子机器学习全文翻译

翻译自17年nature文章

 

 

• 发布时间： 2017年9月14日

量子机器学习

• 雅各布·比亚蒙特（ Jacob Biamonte）
• 彼得Wittek，
• 尼古拉·潘科蒂（ Nicola Pancotti）
• 帕特里克·雷本特斯特（ Patrick Rebentrost）
• 内森·韦伯＆
• 塞思·劳埃德（Seth Lloyd） 

性质 体积 549， 页数195 – 202（2017）引用本文

• 21k次访问

• 317 引文

• 387 高度

• 指标细节

抽象

在计算机功能和算法进步的推动下，机器学习技术已成为查找数据模式的强大工具。量子系统产生的非典型模式被认为无法有效地产生经典系统，因此可以合理地假设量子计算机在机器学习任务上可能会胜过经典计算机。量子机器学习领域探索了如何设计和实现量子软件，该软件可以使机器学习比传统计算机更快。最近的工作产生了量子算法，可以作为机器学习程序的基础，但是硬件和软件方面的挑战仍然很大。

主要

在我们拥有计算机之前很久，人们努力寻找数据模式。托勒密将对恒星运动的观测结果与宇宙的地心模型相匹配，并用复杂的行星轮来解释行星的逆行运动。在16世纪，开普勒分析了哥白尼和布拉赫的数据，揭示了以前隐藏的模式：行星以椭圆形移动，太阳在椭圆的一个焦点处移动。通过对天文学数据进行分析以揭示这种模式，产生了数学技术，例如求解线性方程组的方法（牛顿-高斯），通过梯度下降学习最佳值（牛顿），多项式插值（拉格朗日）和最小二乘拟合（拉普拉斯） 。

二十世纪中叶，数字计算机的建设使数据分析技术得以自动化。在过去的半个世纪中，计算机功能的飞速发展使得线性代数数据分析技术（例如回归分析和主成分分析）得以实现，并导致了更复杂的学习方法（例如支持向量机）。在同一时期，数字计算机的发展和迅速发展催生了新颖的机器学习方法。诸如感知器之类的人工神经网络是在1950年代实现的（参考资料1），只要计算机有能力实现它们。在1960年代至1990年代引入并实施了基于神经网络（例如Hopfield网络和Boltzmann机器）的深度学习和训练方法（例如反向传播）（参考资料2）。在过去的十年中，特别是在过去的五年中，强大的计算机和专用信息处理器相结合，能够实现数十亿权重的深度网络3，并将其应用于非常大的数据集，这表明这种深度学习网络能够识别数据中复杂而微妙的模式。

众所周知，量子力学会在数据中产生非典型模式。诸如深度神经网络之类的经典机器学习方法通​​常具有以下特征：它们既可以识别数据中的统计模式，又可以产生具有相同统计模式的数据：它们可以识别所产生的模式。这种观察表明了以下希望。如果小型量子信息处理器可以产生传统计算机难以计算的统计模式，那么也许它们也可以识别同样难以识别传统的模式。

这种希望的实现取决于能否找到用于机器学习的有效量子算法。量子算法是一组可以解决问题的指令，例如可以确定在量子计算机上执行的两个图是否同构的问题。量子机器学习软件将量子算法用作较大实现的一部分。通过分析量子算法规定的步骤，可以清楚地看到它们有可能在特定问题上胜过经典算法（即减少所需步骤的数量）。这种潜力被称为量子加速。

量子加速的概念取决于人们是采用正式的计算机科学观点（需要数学证明）还是基于现实的有限尺寸设备可以完成的工作的观点（需要有统计优势的可靠统计证据）问题大小的有限范围。对于量子机器学习，经典算法的最佳性能并不总是已知的。这类似于用于整数分解的Shor多项式时间量子算法的情况：没有发现次指数时间经典算法，但是这种可能性没有得到证明。

确定与量子机器学习和经典机器学习相对的缩放优势的方法将取决于量子计算机的存在，这被称为“基准测试”问题。这样的优势可以包括提高分类精度和对经典不可访问系统进行采样。因此，目前使用复杂性理论中的理想化措施来表征机器学习中的量子加速：查询复杂性和门复杂性（请参见专栏1和专栏1表））。查询复杂度衡量的是经典算法或量子算法对信息源的查询数量。如果解决量子问题所需的查询数量少于经典算法所需的查询数量，则会导致量子加速。为了确定门的复杂性，对获得所需结果所需的基本量子运算（或门）的数量进行计数。

表1给定量子机器学习子例程的加速技术

查询和门的复杂性是理想化的模型，可量化解决问题类别所需的资源。在不知道如何将这种理想化映射到现实的情况下，关于真实场景中必要的资源缩放的说法不多。因此，经典机器学习算法所需的资源大部分是通过数值实验来量化的。量子机器学习算法的资源需求在实践中可能同样难以量化。对它们的实际可行性的分析是本次审查的中心主题。

如将在审查中可以看出，有用于机器量子算法学习其表现出量子加速比4，5，6，7。例如，量子基本线性代数子程序（BLAS）-Fourier变换，找到的特征向量和特征值，在其最知名的经典同行求解线性方程组，显示出指数量子加速比8，9，10。这种量子BLAS（qBLAS）可以转化为量子加速器，用于各种数据分析和机器学习算法，包括线性代数，最小二乘拟合，梯度下降，牛顿法，主成分分析，线性，半定和二次编程，拓扑分析和支持向量机9，11，12，13，14，15，16，17，18，19。与此同时，专用量子信息处理器，如量子退火炉和可编程量子光学阵列被很好地匹配深度学习架构20，21，22。尽管尚不清楚在多大程度上可以实现这种潜力，但仍有理由乐观地认为量子计算机可以识别传统计算机无法识别的数据模式。

我们考虑学习机可以是经典的23，24，25，26，27，28，29，30，31，32或量子8，9，11，13，33，34，35，36。它们分析数据可以是由量子感测或测量装置制造古典或量子状态30，37。我们简要讨论了常规机器学习-使用经典计算机在经典数据中查找模式。然后，我们转向量子机器学习，其中量子计算机分析的数据可以是经典数据（最终被编码为量子态），也可以是量子数据。最后，我们简要讨论了使用经典机器学习技术在量子动力学中寻找模式的问题。

 

古典机器学习和数据分析可以分为几类。首先，计算机可用于执行“经典”数据分析方法，例如最小二乘回归，多项式插值和数据分析。机器学习协议可以是有监督的，也可以是无监督的。在监督学习中，训练数据被划分为带标签的类别，例如手写数字的样本以及手写数字应该代表的实际数字，并且机器的工作是学习如何在训练之外为数据分配标签组。在无监督学习中，训练集没有标签，机器的目标是找到训练数据所属的自然类别（例如，互联网上不同类型的照片），然后对训练集之外的数据进行分类。

 

通过对高维向量空间中的向量执行矩阵运算，可以运行多种数据分析和机器学习协议。但是量子力学全都涉及高维向量空间中向量的矩阵运算。

这些方法背后的关键要素是，n个量子位或qubits 的量子状态是2 n维复矢量空间中的矢量。对量子位执行量子逻辑运算或测量，会将相应的状态向量乘以2 n  ×2 n矩阵。通过建立这样的矩阵变换，量子计算机已经示出执行常见线性代数运算，如傅立叶变换38，寻找特征向量和特征值39，并求解线性方程组集超过2个Ñ在时间维向量空间，在多项式Ñ，比最著名的古典音乐快几倍8。后者通常称为Harrow，Hassidim和Lloyd（HHL）算法 8（请参见专栏2）。原始变体假定条件良好的矩阵稀疏。稀疏不太可能在数据的科学，但是后来改进放宽这一假设包括低秩矩阵，以及 10，33，40。超越HHL，在这里我们考察了几种量子算法，这些量子算法在量子机器学习软件中采用线性代数技术时会作为子例程出现。

 

• 发布时间： 2017年9月14日

量子机器学习

• 雅各布·比亚蒙特（ Jacob Biamonte）
• 彼得Wittek，
• 尼古拉·潘科蒂（ Nicola Pancotti）
• 帕特里克·雷本特斯特（ Patrick Rebentrost）
• 内森·韦伯＆
• 塞思·劳埃德（Seth Lloyd） 

性质 体积 549， 页数195 – 202（2017）引用本文

• 21k次访问

• 317 引文

• 387 高度

• 指标细节

抽象

在计算机功能和算法进步的推动下，机器学习技术已成为查找数据模式的强大工具。量子系统产生的非典型模式被认为无法有效地产生经典系统，因此可以合理地假设量子计算机在机器学习任务上可能会胜过经典计算机。量子机器学习领域探索了如何设计和实现量子软件，该软件可以使机器学习比传统计算机更快。最近的工作产生了量子算法，可以作为机器学习程序的基础，但是硬件和软件方面的挑战仍然很大。

主要

在我们拥有计算机之前很久，人们努力寻找数据模式。托勒密将对恒星运动的观测结果与宇宙的地心模型相匹配，并用复杂的行星轮来解释行星的逆行运动。在16世纪，开普勒分析了哥白尼和布拉赫的数据，揭示了以前隐藏的模式：行星以椭圆形移动，太阳在椭圆的一个焦点处移动。通过对天文学数据进行分析以揭示这种模式，产生了数学技术，例如求解线性方程组的方法（牛顿-高斯），通过梯度下降学习最佳值（牛顿），多项式插值（拉格朗日）和最小二乘拟合（拉普拉斯） 。

二十世纪中叶，数字计算机的建设使数据分析技术得以自动化。在过去的半个世纪中，计算机功能的飞速发展使得线性代数数据分析技术（例如回归分析和主成分分析）得以实现，并导致了更复杂的学习方法（例如支持向量机）。在同一时期，数字计算机的发展和迅速发展催生了新颖的机器学习方法。诸如感知器之类的人工神经网络是在1950年代实现的（参考资料1），只要计算机有能力实现它们。在1960年代至1990年代引入并实施了基于神经网络（例如Hopfield网络和Boltzmann机器）的深度学习和训练方法（例如反向传播）（参考资料2）。在过去的十年中，特别是在过去的五年中，强大的计算机和专用信息处理器相结合，能够实现数十亿权重的深度网络3，并将其应用于非常大的数据集，这表明这种深度学习网络能够识别数据中复杂而微妙的模式。

众所周知，量子力学会在数据中产生非典型模式。诸如深度神经网络之类的经典机器学习方法通​​常具有以下特征：它们既可以识别数据中的统计模式，又可以产生具有相同统计模式的数据：它们可以识别所产生的模式。这种观察表明了以下希望。如果小型量子信息处理器可以产生传统计算机难以计算的统计模式，那么也许它们也可以识别同样难以识别传统的模式。

这种希望的实现取决于能否找到用于机器学习的有效量子算法。量子算法是一组可以解决问题的指令，例如可以确定在量子计算机上执行的两个图是否同构的问题。量子机器学习软件将量子算法用作较大实现的一部分。通过分析量子算法规定的步骤，可以清楚地看到它们有可能在特定问题上胜过经典算法（即减少所需步骤的数量）。这种潜力被称为量子加速。

量子加速的概念取决于人们是采用正式的计算机科学观点（需要数学证明）还是基于现实的有限尺寸设备可以完成的工作的观点（需要有统计优势的可靠统计证据）问题大小的有限范围。对于量子机器学习，经典算法的最佳性能并不总是已知的。这类似于用于整数分解的Shor多项式时间量子算法的情况：没有发现次指数时间经典算法，但是这种可能性没有得到证明。

确定与量子机器学习和经典机器学习相对的缩放优势的方法将取决于量子计算机的存在，这被称为“基准测试”问题。这样的优势可以包括提高分类精度和对经典不可访问系统进行采样。因此，目前使用复杂性理论中的理想化措施来表征机器学习中的量子加速：查询复杂性和门复杂性（请参见专栏1和专栏1表））。查询复杂度衡量的是经典算法或量子算法对信息源的查询数量。如果解决量子问题所需的查询数量少于经典算法所需的查询数量，则会导致量子加速。为了确定门的复杂性，对获得所需结果所需的基本量子运算（或门）的数量进行计数。

表1给定量子机器学习子例程的加速技术

全尺寸表

查询和门的复杂性是理想化的模型，可量化解决问题类别所需的资源。在不知道如何将这种理想化映射到现实的情况下，关于真实场景中必要的资源缩放的说法不多。因此，经典机器学习算法所需的资源大部分是通过数值实验来量化的。量子机器学习算法的资源需求在实践中可能同样难以量化。对它们的实际可行性的分析是本次审查的中心主题。

如将在审查中可以看出，有用于机器量子算法学习其表现出量子加速比4，5，6，7。例如，量子基本线性代数子程序（BLAS）-Fourier变换，找到的特征向量和特征值，在其最知名的经典同行求解线性方程组，显示出指数量子加速比8，9，10。这种量子BLAS（qBLAS）可以转化为量子加速器，用于各种数据分析和机器学习算法，包括线性代数，最小二乘拟合，梯度下降，牛顿法，主成分分析，线性，半定和二次编程，拓扑分析和支持向量机9，11，12，13，14，15，16，17，18，19。与此同时，专用量子信息处理器，如量子退火炉和可编程量子光学阵列被很好地匹配深度学习架构20，21，22。尽管尚不清楚在多大程度上可以实现这种潜力，但仍有理由乐观地认为量子计算机可以识别传统计算机无法识别的数据模式。

我们考虑学习机可以是经典的23，24，25，26，27，28，29，30，31，32或量子8，9，11，13，33，34，35，36。它们分析数据可以是由量子感测或测量装置制造古典或量子状态30，37。我们简要讨论了常规机器学习-使用经典计算机在经典数据中查找模式。然后，我们转向量子机器学习，其中量子计算机分析的数据可以是经典数据（最终被编码为量子态），也可以是量子数据。最后，我们简要讨论了使用经典机器学习技术在量子动力学中寻找模式的问题。

方框1：量子加速

量子计算机以量子相干和纠缠等效应来处理信息，而传统计算机则无法做到。在过去的二十年中，在构建更强大的量子计算机方面取得了稳步进展。量子算法是在量子计算机上执行的用于解决问题（例如搜索数据库）的逐步过程。量子机器学习软件利用量子算法来处理信息。解决某些问题时，量子算法原则上可以胜过最著名的经典算法。这被称为量子加速105。

For example, quantum computers can search an unsorted database with N entries in time proportional to √N—that is, O(√N)—where a classical computer given blackbox access to the same database takes time proportional to N: thus the quantum computer exhibits a square-root speedup over the classical computer. Similarly, quantum computers can perform Fourier transforms over N data points, invert sparse N × N matrices, and find their eigenvalues and eigenvectors in time proportional to a polynomial in log2N, where the best known algorithms for classical computers take time proportional to N log 2 N：因此，量子计算机比最佳的经典计算机算法展现出指数级的加速。

在框1表，加速比采取相对于它们的经典对应物（S） -因此，Ô（√ Ñ）指二次加速和ø（日志（Ñ））指相对于它们的经典对应的指数。

显示更多从这个盒子里

经典机器学习

古典机器学习和数据分析可以分为几类。首先，计算机可用于执行“经典”数据分析方法，例如最小二乘回归，多项式插值和数据分析。机器学习协议可以是有监督的，也可以是无监督的。在监督学习中，训练数据被划分为带标签的类别，例如手写数字的样本以及手写数字应该代表的实际数字，并且机器的工作是学习如何在训练之外为数据分配标签组。在无监督学习中，训练集没有标签，机器的目标是找到训练数据所属的自然类别（例如，互联网上不同类型的照片），然后对训练集之外的数据进行分类。

基于线性代数的量子机器学习

通过对高维向量空间中的向量执行矩阵运算，可以运行多种数据分析和机器学习协议。但是量子力学全都涉及高维向量空间中向量的矩阵运算。

这些方法背后的关键要素是，n个量子位或qubits 的量子状态是2 n维复矢量空间中的矢量。对量子位执行量子逻辑运算或测量，会将相应的状态向量乘以2 n  ×2 n矩阵。通过建立这样的矩阵变换，量子计算机已经示出执行常见线性代数运算，如傅立叶变换38，寻找特征向量和特征值39，并求解线性方程组集超过2个Ñ在时间维向量空间，在多项式Ñ，比最著名的古典音乐快几倍8。后者通常称为Harrow，Hassidim和Lloyd（HHL）算法 8（请参见专栏2）。原始变体假定条件良好的矩阵稀疏。稀疏不太可能在数据的科学，但是后来改进放宽这一假设包括低秩矩阵，以及 10，33，40。超越HHL，在这里我们考察了几种量子算法，这些量子算法在量子机器学习软件中采用线性代数技术时会作为子例程出现。

方框2：HHL算法

用于方程组求逆的HHL算法是一个基本且易于理解的子例程，它是许多量子机器学习算法的基础。该算法试图使用量子计算机来求解A x  =  b。HHL通过将向量表示为log 2 N个量子比特上的量子状态，并将向量x表示为量子状态来量化问题。可以假定矩阵A为Hermitian，而不会失去一般性，因为可以始终扩展该空间以使其成立。方程式然后可以通过由等式的两边乘以要解决甲-1，其中甲-1是A的倒数。然后HHL算法允许人们构造与γ成正比的量子态。更一般而言，当A不是正方形或具有零特征值时，该算法可用于查找最小化9 的状态。

该算法的工作原理如下。假设其中是的本征向量阿与本征值λ Ñ  ≥  Λ。通过下施加相位估计阿到计算λ Ñ并通过反正弦的（角度旋转辅助量子位Λ / λ Ñ），然后uncomputing相位估计我们得到：

If the ancillary qubit is measured and if 1 is observed then each eigenstate is divided through by λn, which affects the inverse. The number of times that the state preparation circuit needs to be applied to succeed, after applying amplitude amplification, is , which is the condition number for the matrix.

The HHL algorithm takes O[(logN)2] quantum steps to output , compared with the O(NlogN) steps required to find x using the best known method on a classical computer.

There are several important caveats to the HHL algorithm. First, finding the full answer x from the quantum state  requires O(N) repetitions to reconstruct the N components of x. Generalizations to HHL, such as least-squares fitting, sidestep this problem by allowing the output to have many fewer dimensions than the input. In general, however, HHL can provide only features of the data such as moments of the solution vector or its expectation value  over other sparse matrices B. The second caveat is that the input vector 需要在量子计算机上或使用qRAM进行准备，这可能很昂贵。第三个警告是，矩阵必须条件良好，并且必须有可能有效地模拟e - iA。最后，尽管HHL算法的缩放比例为O [（log N）2 ]，但当前针对实际问题的算法成本估算是令人望而却步的109，这突出了研究进一步改进10的重要性。通常，应意识到线性系统仅适用于某些问题，以实现指数级加速的承诺。

显示更多从这个盒子里

量子主成分分析

例如，考虑主成分分析（PCA）。假设数据以矢量的形式呈现v Ĵ在d维向量空间，其中d = 2 Ñ = Ñ。例如，v j可以是股票从时间t j到时间t j +1的所有股票价格变化的向量。数据的协方差矩阵为，其中上标T表示转置操作：协方差矩阵汇总了数据不同组成部分之间的相关性，例如，不同股票价格变化之间的相关性。最简单的形式是，主成分分析通过对角协方差矩阵进行运算：，其中c k是C的特征向量，而e k是相应的特征值。（由于C是对称的，所以特征向量c k形成正交集。）如果仅一些特征值c k的特征向量大，而其余的数目小或为零，则与这些特征值相对应的特征向量称为C的主分量。每个主成分代表数据中潜在的共同趋势或相关形式，并且根据主成分v  =  分解数据向量v既可以压缩数据的表示形式，又可以预测未来的行为。就计算复杂度和查询复杂度而言，用于执行PCA的经典算法的标度为O（d 2）。（我们注意到，我们使用“ big O”表示法来跟踪主导扩展的主导术语。）

对于经典数据11的量子主成分分析，我们随机选择一个数据向量v j，并使用量子随机存取存储器（qRAM）41将该向量映射为量子状态：。概括向量的量子状态具有log d个量子位，并且qRAM的操作需要除以O（log d）个步骤可以并行执行的O（d）个操作。由于v j是随机选择的，因此得到的量子态具有密度矩阵，其中N是数据矢量的数量。与协方差矩阵比较对于经典数据C，我们看到数据量子版本的密度矩阵实际上是协方差矩阵，直到总因子为止。通过重复采样数据，并且使用称为密度矩阵幂特技42与量子相位估计算法相结合39，其中发现矩阵的特征向量和特征值，就可以采用任何的数据向量的量子版本并将其分解成主成分，同时揭示C的特征值：。然后可以通过对C的本征向量的量子表示进行测量来探究C的主要成分的特性。量子算法在计算复杂度和查询复杂度上均缩放为O [（log N）2 ]。也就是说，量子PCA的效率比经典PCA高出几倍。

 

量子支持向量机和内核方法

监督机器学习算法的最简单示例是线性支持向量机和感知器。这些方法试图在数据集中的两类数据之间找到最佳的分离超平面，从而很可能仅在超平面的一侧找到一类的所有训练示例。当超平面和数据之间的余量最大化时，将给出针对数据的最鲁棒的分类器。在这里，训练中学习的“权重”是超平面的参数。支持向量机的最大能力之一是通过核函数43将其推广到非线性超曲面。这样的分类器已经在图像分割以及生物科学中获得了巨大的成功。

像它的经典对应物一样，量子支持向量机是量子机器学习算法13的范例。第一个量子支持向量机在2000年代初44进行了讨论，它使用了Grover搜索功能最小化的方法45。因此从N个向量中找到s个支持向量迭代。最近，开发了最小二乘量子支持向量机，该机利用了qBLAS子例程的全部功能。数据输入可以来自各种来源，例如来自访问经典数据的qRAM或来自准备量子状态的量子子例程。一旦将数据提供给量子计算设备，就用量子相位估计和矩阵求逆（HHL算法）对其进行处理。原则上，构造最优分离超平面并测试矢量是位于一侧还是另一侧所需的所有操作都可以在log N多项式时间上执行，其中N是准备量子所需的矩阵维数超平面向量的版本。多项式13讨论了径向基函数核和径向基函数核46，以及另一种基于核的方法，称为高斯过程回归47。这种用于量子支持机的方法已经在核磁共振试验台上进行了手写数字识别任务48的实验验证。

 

 

基于qBLAS的优化

许多数据分析和机器学习技术都涉及优化。越来越多的兴趣是使用D-Wave处理器通过量子退火解决组合优化问题。一些优化问题也可以表述为线性系统的单次求解，例如受等式约束的二次函数优化，二次规划问题的子集。如果涉及的矩阵是稀疏的或低秩的，则可以及时解决这些问题，即log d中的多项式，其中d是通过HHL矩阵求逆算法得到的系统维数，相对于经典算法，它的指数提速时间是是d中的多项式。

机器学习中的大多数方法都需要对其性能进行迭代优化。例如，不等式约束通常通过罚函数49和梯度下降或牛顿法的变化来处理。量子PCA方法的一种修改实现了迭代梯度下降和牛顿法用于多项式优化，并且可以再次提供比经典方法19更快的指数加速。以量子态编码的本溶液的多个副本用于在每个步骤中改进该溶液。Brandao和Svore提供了半定式编程的量子版本，该版本支持超多项式加速的可能性18。量子近似优化算法（QAO算法）50 提供了一种独特的方法，可以根据问题的罚函数应用交替的量子位旋转进行优化。

 

将经典数据读入量子机器

必须先输入经典数据，然后才能在量子计算机上对其进行处理。这个“输入问题”通常开销很小，但是对于某些算法可能会带来严重的瓶颈。同样，在量子设备上处理数据后读取数据时也会遇到“输出问题”。像输入问题一样，输出问题通常会导致明显的运行速度下降。

特别是，如果我们希望将HHL，最小二乘拟合，量子主成分分析，量子支持向量机和相关方法应用于经典数据，则该过程首先需要将大量数据加载到量子系统中，这可能需要指数时间51。原则上可以使用qRAM来解决此问题，但这样做的代价可能会导致大数据问题52望而却步。除了基于组合优化的方法外，唯一不依赖大规模qRAM的，基于线性代数的量子机器学习算法是用于执行数据拓扑分析（持久同源性）的量子算法14。除了最小二乘拟合和量子支持向量机以外，基于线性代数的算法也可能会遇到输出问题，因为所需的经典量（例如HHL的解向量或PCA的主分量）难以指数地估算。

尽管有可能实现指数级量子加速，但在优化上不花太多精力，电路尺寸和电路深度开销仍会迅速增加（在HHL 53的一种拟议实现中，大约10 25个量子门）。需要持续的工作来优化此类算法，提供更好的成本估算，并最终了解我们将需要提供的经典量子计算机替代经典机器学习所需的那种量子计算机。

 

深度量子学习

经典的深度神经网络是用于机器学习的高效工具，非常适合激发深度量子学习方法的发展。专用量子信息处理器，如量子退火炉和可编程光子电路非常适合用于构造深量子学习网络21，54，55。可以量化的最简单的深度神经网络是Boltzmann机器（请参见方框3和方框3图）。经典的Boltzmann机器由具有可调相互作用的钻头组成：通过调整这些相互作用来训练Boltzmann机器，以使钻头的热统计数据由Boltzmann–Gibbs分布描述（见图1b）。），再现数据的统计信息。要量化玻尔兹曼机，只需简单地将神经网络表示为与相互作用的伊辛模型相对应的一组相互作用的量子自旋。然后，通过将Boltzmann机器中的输入神经元初始化为固定状态并使系统热化，我们可以读出输出量子位以获得答案。

 

深度量子学习的一个基本特征是它不需要大型的通用量子计算机。量子退火器是专用的量子信息处理器，与通用的量子计算机相比，它更易于构建和扩展（参见图1a）。量子退火器非常适合于实现深度量子学习器，并且可以通过商业途径获得。D-Wave量子退火炉是一个可调的横向伊辛模型，可以对其进行编程以产生经典系统和某些量子自旋系统的热态。D-Wave设备已用于在超过一千个自旋56上执行深度量子学习协议。量子玻尔兹曼机22具有更通用的可调谐耦合器，能够实现通用量子逻辑，目前处于设计阶段57。片上硅波导已被用于构建具有数百个可调谐干涉仪的线性光学阵列，并且专用超导量子信息处理器可用于实现量子近似优化算法。

量子计算机可以在这里提供多种优势。首先，量子方法可以使系统二次热化快于它的古典对应20，58，59，60。这样可以对完全连接的Boltzmann机器进行准确的培训。其次，量子计算机可以通过提供改进的采样方式来加速Boltzmann训练。由于玻耳兹曼机器中的神经元激活模式是随机的，因此需要多次重复来确定成功概率，进而发现改变神经网络权重对深层网络性能的影响。相反，在训练量子Boltzmann机器时，量子相干性可以二次减少学习所需任务所需的样本数量。此外，对训练数据的量子访问（即qRAM或量子黑盒子例程）使机器可以使用对训练数据的访问请求，比传统方法所需的访问请求少二次：20。

量子信息处理为深度学习提供了新的，基本上是量子的模型。例如，添加的横向场的伊辛模型量子波尔兹曼机可以诱导各种量子效应，如隧道22，61。添加另外的量子联轴器变换量子波尔兹曼机到各种量子系统57，62。在可调谐的伊辛模型中添加可调谐的横向相互作用对于全量子计算来说是普遍的57：通过适当的权重分配，该模型可以执行通用量子计算机可以执行的任何算法。这样的通用深度量子学习者可以识别和分类传统计算机无法做到的模式。

与经典的玻尔兹曼机不同，量子玻尔兹曼机输出量子态。因此，深量子网络可以学习生成代表多种系统的量子状态，从而允许网络充当量子关联存储器63的形式。经典机器学习缺乏这种产生量子态的能力。因此，量子玻尔兹曼训练的应用范围不仅限于对量子态进行分类，还提供了更丰富的经典数据模型。

 

用于量子数据的量子机器学习

量子机器学习最直接的应用也许是量子数据，即量子系统和过程所产生的实际状态。如上所述，许多量子机器学习算法通过将经典数据映射到量子力学状态，然后使用基本的量子线性代数子例程来操纵这些状态，从而找到经典数据中的模式。这些量子机器学习算法可以直接应用于光和物质的量子态，以揭示其潜在的特征和模式。所得的量子分析模式通常比对量子系统中数据进行的经典分析更加有效和更具启发性。例如，给定一个N × N描述的系统的多个副本与经典设备在A上执行层析成像所需的O（N 2）测量相比，密度主矩阵可以使用量子主成分分析来找到其特征值并揭示时间O [（log N）2 ]中对应的特征向量。密度矩阵，以及执行经典PCA所需的O（N 2）操作。量子数据的这种量子分析可以在相对较小的量子计算机上进行，这可能会在未来几年内实现。

一种特别强大的量子数据分析技术是使用量子模拟器来探测量子动力学。量子模拟器是“量子模拟计算机”，即可以对其动力学进行编程以匹配某些所需量子系统的动力学的量子系统。量子模拟器可以是构造为模拟特定类别的量子系统的专用设备，也可以是通用量子计算机。由受信任的量子模拟器连接到未知系统和调整模拟器以抵消未知动力学的模型，未知系统的动态特性可以有效地使用近似贝叶斯推理得知64，65，66。这成倍地减少了执行仿真所需的测量次数。类似地，通用量子仿真器算法67允许人们重建量子动力学，而ref的量子Boltzmann训练算法。图61允许在希尔伯特空间的维度上以时间对数的方式重建状态，这比通过经典的层析X射线摄影术重建动力学成指数地快。

要使用一台量子计算机，帮助检定量子系统65，66或接受输入状态，在量子PCA算法的使用，我们必须面对装载相干输入状态的大量技术挑战。然而，因为这样的应用程序不需要qRAM并为指数的加速潜力器件特性22，61，65，66，他们仍然是量子机器学习的近期应用前景广阔的可能性之一。

设计和控制量子系统

量子计算和信息科学发展中的主要挑战涉及调整量子门以匹配量子误差校正所需的严格要求。启发式搜索方法可以有助于实现这一目标的监督学习的场景68，69（例如，在的情况下，最近邻耦合的超导人造原子69与在噪声存在99.9％以上的栅极保真度），并且因此将达到一个接受容错量子计算的阈值。相似的方法已成功构建了单次Toffoli门，再次达到99.9％70以上的门保真度。遗传算法已被用来减少量子门71中的数字和实验误差。它们已用于通过辅助量子位和不完善的门来模拟受控NOT门。除了性能优于数字量子模拟的协议外，已经证明遗传算法也可用于抑制门72中的实验误差。另一种方法是使用随机梯度下降和两体相互作用将Toffoli门嵌入到一系列量子操作或门中，而无需使用时间依赖的量子网络73的自然动力学进行控制。动态解耦序列有助于保护量子态免受退相干，这可以使用递归神经网络74进行设计。

控制量子系统同样重要和复杂。学习方法在开发控制序列以优化自适应量子计量学方面也非常成功，这是许多量子技术中的关键量子构件。已经提出了用于控制量子分子的遗传算法，以克服由于在实验过程中改变环境参数而引起的问题75。强化学习采用启发式全局优化算法，如用于设计电路的算法，得到了广泛的成功，特别是在噪声和退相干的情况下，与该系统的尺寸缩放以及76，77，78。人们还可以在基于门的量子系统中利用强化学习。例如，基于智能代理的量子信息自适应控制器展示了针对固定方向未知量级外部杂散场的自适应校准和补偿策略。

古典机器学习也是一种强大的工具，可用于提取有关量子态的理论见解。神经网络最近被部署来研究凝聚态两个中心问题，即相的事项检测79，80和基态搜索81。这些成功实现了比已建立的数值工具更好的性能。理论物理学家现在正在研究这些模型，以与传统方法（例如张量网络）相比，分析地了解其描述能力。对奇异状态的有趣应用已经在市场上，并且已经显示出从无序或拓扑有序的系统中捕获非常重要的特征。

对未来工作的看法

正如我们在这条已经讨论的，小的量子计算机和较大专用量子模拟器，退火炉等似乎有在机器学习和数据分析的潜在用途15，21，22，36，48，82，83，84，85，86，87，88，89，90，91，92，93，94，95。但是，量子算法的执行需要尚不可用的量子硬件。

在硬件方面，几种使能技术取得了长足的进步。通过量子云计算（“ Qloud”）将广泛提供具有50–100量子位的小型量子计算机。特殊用途的量子信息处理器，例如量子模拟器，量子退火器，集成光子芯片，氮空位中心（NV）金刚石阵列，qRAM和按订单生产的超导电路，将继续在尺寸和复杂性上发展。量子机器学习提供了一套潜在应用为小量子计算机23，24，25，26，27，28，29，30，31，96，97，98通过专用量子信息处理器的补充和增强的21，22，数字处理器量子70，73，78，99，100和传感器76，77，101。

尤其是，使用集成的超导电路，其原理上是可扩展的，已经构建并运行了约2,000量子比特的量子退火器。量子退火器实现量子机器学习算法的最大挑战包括改善连接性和在量子位之间实现更通用的可调耦合。使用硅中集成的光子器件已经构造了具有约100个可调干涉仪的可编程量子光学阵列，但是随着这种电路规模的扩大，量子效应的损失也会增加。量子机器学习的一个特别重要的挑战是接口设备（如qRAM）的构造，该接口设备允许经典信息以量子力学形式52进行编码。一个qRAM访问N多条数据由2个N个量子开关的分支阵列组成，该分支阵列在内存调用期间必须一致地运行。原则上，这种qRAM需要花费时间O（log N）来执行存储调用，并且每次切换操作最多可以容忍O（1 / log N）的错误率，其中log N是qRAM电路的深度。已经进行了qRAM的原理证明，但是构造大型量子开关阵列是一个困难的技术问题。

这些硬件挑战本质上是技术性的，并且存在克服这些挑战的明确途径。但是，如果要将量子机器学习变成量子计算机的“杀手级应用”，则必须克服这些问题。如前所述，已经确定的大多数量子算法都面临许多限制其适用性的警告。我们可以将上述注意事项归纳为四个基本问题。

1. 1个

   输入问题。尽管量子算法可以极大地提高处理数据的速度，但很少能提供读取数据的优势。这意味着在某些情况下，输入中的读取成本可以控制量子算法的成本。了解这一因素是一个持续的挑战。

2. 2

   输出问题。要从某些量子算法中获得完整的解决方案作为一串位，需要学习指数数量的位。这使得量子机器学习算法的某些应用不可行。通过仅了解解决方案状态的摘要统计信息，可以潜在地避开此问题。

3. 3

   成本问题。与输入/输出问题密切相关，目前对量子机器学习算法所需门的真实数目了解甚少。复杂性的界限表明，对于足够大的问题，它们将提供巨大的优势，但仍不清楚何时出现交叉点。

4. 4

   基准测试问题。在实践中通常很难断言量子算法比所有已知的经典机器算法都要好，因为这将需要针对现代启发式方法进行广泛的基准测试。为量子机器学习建立下界将部分解决这个问题。

为了避免其中的一些问题，我们可以将量子计算应用于量子数据，而不是经典数据。其中的一个目的是使用量子机器学习来表征和控制量子计算机66。这将实现类似于传统计算中出现的创新的良性循环，其中，然后利用每一代处理器来设计下一代处理器。我们已经开始看到这个周期与传统机器学习的第一批成果被用来提高量子处理器设计23，24，25，26，27，28，29，30，31，102，103，104，而这又为量子增强机器学习应用程序本身提供强大的计算资源 8，9，11，13，33，34，35，36。