Smelyanskiy V N, Knysh S, Morris R D
NASA Ames Research Center, MS 269-3, Moffett Field, California 94035-1000, USA.
Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Sep;70(3 Pt 2):036702. doi: 10.1103/PhysRevE.70.036702. Epub 2004 Sep 16.
In this paper we analyze the performance of the Quantum Adiabatic Evolution algorithm on a variant of the satisfiability problem for an ensemble of random graphs parametrized by the ratio of clauses to variables, gamma=M/N . We introduce a set of macroscopic parameters (landscapes) and put forward an ansatz of universality for random bit flips. We then formulate the problem of finding the smallest eigenvalue and the excitation gap as a statistical mechanics problem. We use the so-called annealing approximation with a refinement that a finite set of macroscopic variables (instead of only energy) is used, and are able to show the existence of a dynamic threshold gamma= gamma(d) starting with some value of K -the number of variables in each clause. Beyond the dynamic threshold, the algorithm should take an exponentially long time to find a solution. We compare the results for extended and simplified sets of landscapes and provide numerical evidence in support of our universality ansatz. We have been able to map the ensemble of random graphs onto another ensemble with fluctuations significantly reduced. This enabled us to obtain tight upper bounds on the satisfiability transition and to recompute the dynamical transition using the extended set of landscapes.
在本文中，我们分析了量子绝热演化算法在一类可满足性问题变体上的性能，该问题针对由子句与变量之比γ = M/N 参数化的随机图系综。我们引入了一组宏观参数（景观），并针对随机比特翻转提出了一种普遍性假设。然后，我们将寻找最小特征值和激发间隙的问题表述为一个统计力学问题。我们使用所谓的退火近似，并进行了改进，即使用有限集的宏观变量（而不是仅能量），并且能够证明从某个K值（每个子句中的变量数量）开始存在动态阈值γ = γ(d)。超过动态阈值后，算法找到解所需的时间将呈指数级增长。我们比较了扩展和简化景观集的结果，并提供了支持我们普遍性假设的数值证据。我们已经能够将随机图集综映射到另一个波动显著减小的集综上。这使我们能够获得可满足性转变的严格上界，并使用扩展的景观集重新计算动态转变。
