论文标题
用于近似分区函数的均值时间量子算法
A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
论文作者
论文摘要
我们提出了一种新型的量子算法，以相对于状态空间大小的对数估算均方根时间的吉布斯分区函数。这是在štefankovič，vempala和Vigoda的开创性近线性时间算法中获得的第一种速度[JACM，2009]。我们的结果还通过利用量子马尔可夫链的特性来保留在先前工作中获得的二次加速和光谱差距。作为应用程序，我们获得了用于计算Ising模型的分区功能的最著名算法的新多项式改进，计算了$ K $ - 色的数量，匹配或独立的图表，并估算凸体的体积。 我们的方法依赖于开发量子相和幅度估计算法的新变体，这些变体返回几乎没有偏差的估计值，而没有破坏其初始量子状态。我们将这些子例程扩展到几乎无偏的量子平均估计器中，该估计量比经典的经验平均值快速地降低方差。在我们的工作之前，不存在这种估计量。这些具有普遍兴趣的属性会导致在计算分区函数的模拟退火范式内提供更好的收敛保证。
We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time with respect to the logarithm of the size of the state space. This is the first speed-up of this type to be obtained over the seminal nearly-linear time algorithm of Štefankovič, Vempala and Vigoda [JACM, 2009]. Our result also preserves the quadratic speed-up in precision and spectral gap achieved in previous work by exploiting the properties of quantum Markov chains. As an application, we obtain new polynomial improvements over the best-known algorithms for computing the partition function of the Ising model, counting the number of $k$-colorings, matchings or independent sets of a graph, and estimating the volume of a convex body. Our approach relies on developing new variants of the quantum phase and amplitude estimation algorithms that return nearly unbiased estimates with low variance and without destroying their initial quantum state. We extend these subroutines into a nearly unbiased quantum mean estimator that reduces the variance quadratically faster than the classical empirical mean. No such estimator was known to exist prior to our work. These properties, which are of general interest, lead to better convergence guarantees within the paradigm of simulated annealing for computing partition functions.
