生成随机数看似容易，但其难度却出乎意料——尤其是在随机数的概率分布非常复杂的情况下。
在科学研究中（例如在训练神经网络时），经常会遇到这种情况。在这种情况下，研究人员可以使用一种通用计算最早使用的技术：Metropolis算法。该算法于1953年首次在开创性的MANIAC计算机上运行，而它的现代版名称则是马尔科夫链蒙特卡罗（MCMC）算法。
7月12日，来自IBM Quantum的科学家Layden等人在《自然》杂志上撰文，通过使用量子计算机来加速程序的性能，报告了这一算法发展中更为现代的转折。
MCMC算法是一种根据指定概率分布生成随机数的框架，这项任务被称为采样。该框架包含多种变体，所有变体都涉及样本的迭代；经过足够多的循环后，需要保证样本的分布符合所需的目标分布。
这一过程中的每次迭代都包含两个部分：
– 建议步骤，即在当前样本的基础上建议一个样本；
– 接受或拒绝步骤，即接受新样本作为迭代中的下一个样本，或拒绝新样本以重复上述过程。
马尔科夫链蒙特卡罗（MCMC）算法从目标概率分布中抽取随机数，涉及的两个步骤：提出一个样本，然后接受该样本作为迭代中的下一个样本；或者拒绝该样本，从而触发该过程重新开始。这两个步骤的设计都必须保证足够的迭代次数，以便最终得到符合目标分布的样本，实现这一目标所需的迭代次数称为收敛时间(convergence time)。具体来说，样本收敛到目标分布的迭代次数比使用传统MCMC算法的迭代次数更少。
MCMC 算法的变体可通过每个步骤所使用的不同策略来区分。最重要的是，这两个步骤必须以这样一种方式构建，即保证重复这两个步骤最终得到的样本分布符合所需的分布。因此，“需要多长时间”是任何MCMC变体的关键属性。
在样本按照目标分布分布之前，这个过程需要重复1000次吗？还是一百万次？
所需的迭代次数称为收敛时间，它取决于随机变量的维度——描述采样变量所需的比特数。维数越大，收敛时间越长。不幸的是，对于目前使用的大多数 MCMC 变体而言，收敛时间与变量维度的确切数学关系并不严格。然而，这并没有阻止人们使用MCMC算法：他们倾向于利用收敛的经验和统计特征。
Layden等人设计了一种MCMC变体：利用量子计算机在提议步骤中产生样本。在任何迭代中，随机样本都被编码为量子态，并对其进行一系列量子运算以产生输出态，该输出态可被测量以生成新样本。这本身并不特别：在MCMC算法的提议步骤中，几乎任何程序都可以用来生成新样本（包括简单地对当前样本施加噪声）。
然而，此次的研究人员必须能够证明这些步骤收敛到了目标分布，而这对于任意的提议程序来说是不可能的。这就引出了Layden及其同事的关键创新：他们设计了一套量子操作，当量子提议步骤与标准的接受或拒绝步骤相结合时，就可以验证收敛性。
作者通过数值模拟和早期量子计算硬件实验相结合的方式，展示了他们的量子增强MCMC算法。他们的研究结果表明了迭代对目标分布的预测收敛性。更重要的是，他们还证明了该收敛速度快于之前为提议步骤设计的几种经典替代方案。
实际的收敛速度很难测量，作者仅对有限复杂度的过程进行了测量——那些目标变量分布最多可由10比特描述的过程；他们还对20比特变量目标分布的收敛率进行了近似计算。
在所有情况下，他们都发现了令人信服的证据，证明量子版MCMC算法的收敛速度比经典版更快。他们根据经验确定，这种速度提升是多项式的，量子增强策略的收敛时间约为传统策略收敛时间的立方根。
这种速度提升从何而来？与大多数量子增强一样，很难将其归因于量子系统的任何一个特征。Layden等人提供的数字证据表明，他们所选择的量子操作在生成多样化提案与满足目标概率分布所施加的约束之间取得了微妙的平衡：这是经典提案策略难以实现的权衡。
平均收敛速率模拟
收敛率实验
量子加速机制
尽管Layden及其同事的工作很全面，但也存在一些局限性。
首先，量子增强算法的收敛性证明只有在量子操作完美执行的情况下才是有效的：在硬件不产生任何噪声的情况下。然而，他们的实验结果表明，收敛率对噪声具有一定的稳健性，尤其是当硬件噪声可以随机化时。
其次，加速收敛仅在小规模问题中观察到，在更大规模问题中可能会消失，特别是在存在噪声的情况下。如果作者对加速原因的解释是正确的，并且如果硬件噪声可以在更大尺度上被抑制，加速很可能会持续下去——但这在现阶段还远远不能确定。
最后，尽管Layden等人已经证明他们的量子增强算法比一些常见的经典提议策略收敛更快，但他们还没有测试更多MCMC变体。因此，这一差距有可能被现有的或可能设计出的其他经典提议策略弥补，甚至有可能是受到这项工作的启发。
尽管存在这些局限性，Layden及其同事的研究为早期含噪声量子计算机生成有用的解决方案提供了一个重要而令人兴奋的应用，同时也为富有成果的未来研究确定了许多方向。
转自安全内参，原文链接:https://www.secrss.com/articles/56622
封面来源于网络，如有侵权请联系删除