Classical and Quantum Annealing in the Median of Three Satisfiability
Classical and Quantum Annealing in the Median of Three Satisfiability
复制标题
三个可满足性中值的经典和量子退火
DOI：
10.1103/physreva.83.012309
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
H. Raedt
中科院分区：
文献类型：
--
作者：
T. Neuhaus;M. Peschina;K. Michielsen;H. Raedt
我们确定了一个特定的合奏的经典和量子复杂性的三个可满足性问题与一个独特的满意的分配高达N = 100和80个变量，分别。在经典极限，我们采用广义系综技术和测量的时间，马尔可夫蒙特卡罗过程花费在寻找经典基态。在量子极限下，我们确定了沿沿着量子绝热轨道的最大有限关联长度，该轨道由问题哈密顿量和恒定横场哈密顿量组成的哈密顿量中的绝热控制参数的线性扫描确定。在我们的合奏的中位数，这两个复杂性指数发散的变量的数量。因此，标准的传统绝热量子计算无法将计算复杂度降低到多项式。此外，量子极限下的增长速率常数是经典极限下的3.8倍，这使得经典涨落在基态搜索中比量子涨落更有利。
We determine the classical and quantum complexities of a specific ensemble of three-satisfiability problems with a unique satisfying assignment for up to N = 100 and 80 variables, respectively. In the classical limit, we employ generalized ensemble techniques and measure the time that a Markovian Monte Carlo process spends in searching classical ground states. In the quantum limit, we determine the maximum finite correlation length along a quantum adiabatic trajectory determined by the linear sweep of the adiabatic control parameter in the Hamiltonian composed of the problem Hamiltonian and the constant transverse field Hamiltonian. In the median of our ensemble, both complexities diverge exponentially with the number of variables. Hence, standard, conventional adiabatic quantum computation fails to reduce the computational complexity to polynomial. Moreover, the growth-rate constant in the quantum limit is 3.8 times as large as the one in the classical limit, making classical fluctuations more beneficial than quantum fluctuations in ground-state searches.