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 条

[1] Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions [J].

Altarelli, Fabrizio ;

Monasson, Remi ;

Zamponi, Francesco .

INTERNATIONAL WORKSHOP ON STATISTICAL-MECHANICAL INFORMATICS 2007 (IW-SMI 2007), 2008, 95

[2] Anderson localization makes adiabatic quantum optimization fail [J].

Altshuler, Boris ;

Krovi, Hari ;

Roland, Jeremie .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2010, 107 (28) :12446-12450

[3]

AMBAINIS A, ARXIVQUANTPH0411152

[4]

[Anonymous], 2005, PHASE TRANSITIONS CO

[5]

[Anonymous], 2012, P 23 ANN ACM SIAM S

[6]

Arora S, 2009, COMPUTATIONAL COMPLEXITY: A MODERN APPROACH, P1, DOI 10.1017/CBO9780511804090

[7] Quantum supremacy using a programmable superconducting processor [J].

Arute, Frank ;

Arya, Kunal ;

Babbush, Ryan ;

Bacon, Dave ;

Bardin, Joseph C. ;

Barends, Rami ;

Biswas, Rupak ;

Boixo, Sergio ;

Brandao, Fernando G. S. L. ;

Buell, David A. ;

Burkett, Brian ;

Chen, Yu ;

Chen, Zijun ;

Chiaro, Ben ;

Collins, Roberto ;

Courtney, William ;

Dunsworth, Andrew ;

Farhi, Edward ;

Foxen, Brooks ;

Fowler, Austin ;

Gidney, Craig ;

Giustina, Marissa ;

Graff, Rob ;

Guerin, Keith ;

Habegger, Steve ;

Harrigan, Matthew P. ;

Hartmann, Michael J. ;

Ho, Alan ;

Hoffmann, Markus ;

Huang, Trent ;

Humble, Travis S. ;

Isakov, Sergei V. ;

Jeffrey, Evan ;

Jiang, Zhang ;

Kafri, Dvir ;

Kechedzhi, Kostyantyn ;

Kelly, Julian ;

Klimov, Paul V. ;

Knysh, Sergey ;

Korotkov, Alexander ;

Kostritsa, Fedor ;

Landhuis, David ;

Lindmark, Mike ;

Lucero, Erik ;

Lyakh, Dmitry ;

Mandra, Salvatore ;

McClean, Jarrod R. ;

McEwen, Matthew ;

Megrant, Anthony ;

Mi, Xiao .

NATURE, 2019, 574 (7779) :505-+

[8] The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective [J].

Bapst, V. ;

Foini, L. ;

Krzakala, F. ;

Semerjian, G. ;

Zamponi, F. .

PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS, 2013, 523 (03) :127-205

[9] Effect of quantum fluctuations on the coloring of random graphs [J].

Bapst, Victor ;

Semerjian, Guilhem ;

Zamponi, Francesco .

PHYSICAL REVIEW A, 2013, 87 (04)

[10] Hiding solutions in random satisfiability problems: A statistical mechanics approach [J].

Barthel, W ;

Hartmann, AK ;

Leone, M ;

Ricci-Tersenghi, F ;

Weigt, M ;

Zecchina, R .

PHYSICAL REVIEW LETTERS, 2002, 88 (18) :1887011-1887014

← 1 2 3 4 5 6 7 8 →