Wild Dominik S, Sels Dries, Pichler Hannes, Zanoci Cristian, Lukin Mikhail D
Max Planck Institute of Quantum Optics, Hans-Kopfermann-Straße 1, D-85748 Garching, Germany.
Center for Computational Quantum Physics, Flatiron Institute, New York, New York 10010, USA.
Phys Rev Lett. 2021 Sep 3;127(10):100504. doi: 10.1103/PhysRevLett.127.100504.
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.
从经典吉布斯分布中进行高效采样是一个重要的计算问题，其应用范围涵盖从统计物理到蒙特卡罗和优化算法，再到机器学习等领域。我们引入了一族量子算法，通过制备编码整个吉布斯分布的态来提供无偏样本。我们证明，对于包括伊辛模型以及从两个不同图的加权独立集中采样等几个例子，这种方法相对于经典马尔可夫链算法实现了加速。我们的方法将计算复杂度与相变联系起来，为量子加速提供了一种物理解释。此外，它为在近期量子设备上探索潜在有用的采样算法打开了大门，因为从某些图的独立集中采样的算法可以自然地使用里德堡原子阵列来实现。
