论文标题
量子增强马尔可夫链蒙特卡洛
Quantum-enhanced Markov chain Monte Carlo
论文作者
论文摘要
来自复杂概率分布的采样是在许多领域引起的硬计算问题，包括统计物理，优化和机器学习。量子计算机最近已用于从经典中很难采样的复杂分布中采样，但在应用中很少出现。在这里，我们将一种量子算法引入了来自在几种应用中构成瓶颈的分布中的样品，我们在超导量子处理器上实现了瓶颈。该算法执行Markov Chain Monte Carlo（MCMC），这是一种流行的迭代采样技术，可从经典ISING模型的Boltzmann分布中采样。在每个步骤中，量子处理器都探索了叠加中的模型以提出随机移动，然后被经典计算机接受或拒绝，并返回到量子处理器，以确保收敛到所需的Boltzmann分布。我们发现，在模拟和实验中，这种量子算法在相关问题实例上的迭代次数少于迭代次数。因此，它为量子计算机打开了一条新的路径，以在短期内解决有用（不仅仅是困难的问题）。
Sampling from complicated probability distributions is a hard computational problem arising in many fields, including statistical physics, optimization, and machine learning. Quantum computers have recently been used to sample from complicated distributions that are hard to sample from classically, but which seldom arise in applications. Here we introduce a quantum algorithm to sample from distributions that pose a bottleneck in several applications, which we implement on a superconducting quantum processor. The algorithm performs Markov chain Monte Carlo (MCMC), a popular iterative sampling technique, to sample from the Boltzmann distribution of classical Ising models. In each step, the quantum processor explores the model in superposition to propose a random move, which is then accepted or rejected by a classical computer and returned to the quantum processor, ensuring convergence to the desired Boltzmann distribution. We find that this quantum algorithm converges in fewer iterations than common classical MCMC alternatives on relevant problem instances, both in simulations and experiments. It therefore opens a new path for quantum computers to solve useful--not merely difficult--problems in the near term.
