Entropic barriers as a reason for hardness in both classical and quantum algorithms

被引：16

作者：

Bellitti, Matteo ^{[1
]}

Ricci-Tersenghi, Federico ^{[2
,3
,4
]}

Scardicchio, Antonello ^{[5
,6
]}

机构：

[1] Boston Univ, Dept Phys, Boston, MA 02215 USA

[2] Sapienza Univ Roma, Dipartimento Fis, Ple A Moro 2, I-00185 Rome, Italy

[3] CNR, Nanotec, Rome Unit, Ple A Moro 2, I-00185 Rome, Italy

[4] Ist Nazl Fis Nucl, Sez Roma 1, Ple A Moro 2, I-00185 Rome, Italy

[5] Abdus Salam Int Ctr Theoret Phys, Str Costiera 11, I-34151 Trieste, Italy

[6] Ist Nazl Fis Nucl, Sez Trieste, Via Valerio 2, I-34127 Trieste, Italy

来源：

PHYSICAL REVIEW RESEARCH | 2021年 / 3卷 / 04期

基金：

欧洲研究理事会;

关键词：

SPIN MODELS; FERROMAGNET; TRANSITION; DYNAMICS; PHASE;

D O I：

10.1103/PhysRevResearch.3.043015

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

We study both classical and quantum algorithms to solve a hard optimization problem, namely 3-XORSAT on 3-regular random graphs. By introducing a new quasi-greedy algorithm that is not allowed to jump over large energy barriers, we show that the problem hardness is mainly due to entropic barriers. We study, both analytically and numerically, several optimization algorithms, finding that entropic barriers affect in a similar way classical local algorithms and quantum annealing. For the adiabatic algorithm, the difficulty we identify is distinct from that of tunneling under large barriers, but does, nonetheless, give rise to exponential running (annealing) times.

引用

页数：15

共 72 条

[11] Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms [J].