论文标题
吉布斯分区功能的简单（经典）和更快（量子）算法
Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
论文作者
论文摘要
We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature.我们的工作有两个主要贡献：首先，我们修改了štefankovič，vempala和Vigoda的经典算法（\ emph {J.〜ACM}，56（3），2009年，以提高其样品复杂性；其次，我们量化了这种新算法，由于Harrow和Wei（Soda 2020），该问题先前最快的量子算法改进。估计分区功能的常规方法需要在形成所谓冷却时间表的一组反向温度下近似吉布斯分布的平均值。 The length of the cooling schedule directly affects the complexity of the algorithm.将我们改进的版本组合到štefankovič，vempala和Vigoda的算法与Huber的配对产品估计器（\ emph {Ann。\ appl。\ probab。}，25（2），〜2015），我们的新量子Algorithm使用更短的cool cool Schedule。 This length matches the optimal length conjectured by Štefankovič, Vempala and Vigoda.与最佳经典算法绘制的随机样品数量相比，量子算法在所需的量子样本数量中也具有二次优势，其计算复杂性具有四边形的依赖性，更好地依赖于用于生产量子样品的马尔可夫链的光谱差距。
We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. Our work has two main contributions: first, we modify the classical algorithm of Štefankovič, Vempala and Vigoda (\emph{J.~ACM}, 56(3), 2009) to improve its sample complexity; second, we quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei (SODA 2020). The conventional approach to estimating partition functions requires approximating the means of Gibbs distributions at a set of inverse temperatures that form the so-called cooling schedule. The length of the cooling schedule directly affects the complexity of the algorithm. Combining our improved version of the algorithm of Štefankovič, Vempala and Vigoda with the paired-product estimator of Huber (\emph{Ann.\ Appl.\ Probab.}, 25(2),~2015), our new quantum algorithm uses a shorter cooling schedule than previously known. This length matches the optimal length conjectured by Štefankovič, Vempala and Vigoda. The quantum algorithm also achieves a quadratic advantage in the number of required quantum samples compared to the number of random samples drawn by the best classical algorithm, and its computational complexity has quadratically better dependence on the spectral gap of the Markov chains used to produce the quantum samples.
