论文标题
近期设备的量子采样算法
Quantum Sampling Algorithms for Near-Term Devices
论文作者
论文摘要
从经典Gibbs分布中进行有效的采样是一个重要的计算问题，其应用程序从蒙特卡洛的统计物理和优化算法到机器学习的应用。我们介绍了一种量子算法系列，该算法通过准备编码整个Gibbs分布的状态来提供无偏样的样品。我们表明，这种方法会导致在经典的马尔可夫链算法上加速，以获取几个示例，包括ISING模型和来自两个不同图的加权独立集中的采样。我们的方法将计算复杂性与相变相连，从而提供了量子加速的物理解释。此外，它为探索在近期量子设备上探索潜在有用的采样算法的大门，因为可以使用Rydberg Atom阵列自然实现了从某些图上进行采样的算法。
Efficient sampling from a classical Gibbs distribution is an important computational problem with applications ranging from statistical physics over Monte Carlo and optimization algorithms to machine learning. We introduce a family of quantum algorithms that provide unbiased samples by preparing a state encoding the entire Gibbs distribution. We show that this approach leads to a speedup over a classical Markov chain algorithm for several examples including the Ising model and sampling from weighted independent sets of two different graphs. Our approach connects computational complexity with phase transitions, providing a physical interpretation of quantum speedup. Moreover, it opens the door to exploring potentially useful sampling algorithms on near-term quantum devices as the algorithm for sampling from independent sets on certain graphs can be naturally implemented using Rydberg atom arrays.
