近日，美国IBM量子公司的David Layden及其研究团队取得一项新进展。经过不懈努力，他们提出了一种量子增强的马尔可夫链蒙特蒙特卡罗方法。相关研究成果已于2023年7月12日在国际权威学术期刊《自然》上发表。

该研究团队介绍并进行了实验演示一种适用于当前硬件的量子算法，用于从多个应用产生的复杂分布中进行采样。该算法利用著名的马尔可夫链蒙特卡罗（MCMC）迭代技术，从经典Ising模型的玻尔兹曼分布中进行采样。与大多数最近的量子算法不同，该算法能够证明其收敛于正确的分布，尽管经典方法很难模拟。然而，像大多数MCMC算法一样，该算法的收敛速度难以从理论上确定，因此研究人员进行了实验和仿真分析。实验结果表明，相比于常见的经典MCMC替代方案，该研究提出的量子算法在更少的迭代次数下就能够收敛，表明其对噪声具有非凡的鲁棒性。

在模拟中，研究人员观察到了三次和四次之间的多项式加速效果。如果这种经验加速能够在更大规模上持续存在，将有望缓解机器学习、统计物理和优化等领域中采样问题所带来的计算瓶颈。因此，该算法为量子计算机解决有用的采样问题（而不仅仅是困难的采样问题）开辟了新的途径。

据悉，量子计算机有望在某些计算问题上比经典计算机更高效。然而，目前的量子处理器受到其相对较小的规模和较高的错误率的限制。因此，近期的量子加速研究主要关注解决经典难题和与当前量子硬件匹配的问题，例如从复杂的概率分布中进行采样，尽管这些采样问题目前并不明确具有实用性。

附：英文原文

Title: Quantum-enhanced Markov chain Monte Carlo

Author: Layden, David, Mazzola, Guglielmo, Mishmash, Ryan V., Motta, Mario, Wocjan, Pawel, Kim, Jin-Sung, Sheldon, Sarah

Issue&Volume: 2023-07-12

Abstract: Quantum computers promise to solve certain computational problems much faster than classical computers. However, current quantum processors are limited by their modest size and appreciable error rates. Recent efforts to demonstrate quantum speedups have therefore focused on problems that are both classically hard and naturally suited to current quantum hardware, such as sampling from complicated—although not explicitly useful—probability distributions. Here we introduce and experimentally demonstrate a quantum algorithm that is similarly well suited to current hardware, but which samples from complicated distributions arising in several applications. The algorithm performs Markov chain Monte Carlo (MCMC), a prominent iterative technique, to sample from the Boltzmann distribution of classical Ising models. Unlike most near-term quantum algorithms, ours provably converges to the correct distribution, despite being hard to simulate classically. But like most MCMC algorithms, its convergence rate is difficult to establish theoretically, so we instead analysed it through both experiments and simulations. In experiments, our quantum algorithm converged in fewer iterations than common classical MCMC alternatives, suggesting unusual robustness to noise. In simulations, we observed a polynomial speedup between cubic and quartic over such alternatives. This empirical speedup, should it persist to larger scales, could ease computational bottlenecks posed by this sampling problem in machine learning, statistical physics and optimization. This algorithm therefore opens a new path for quantum computers to solve useful—not merely difficult—sampling problems.

DOI: 10.1038/s41586-023-06095-4

Source: https://www.nature.com/articles/s41586-023-06095-4