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

Autor: Matteo Bellitti, Federico Ricci-Tersenghi, Antonello Scardicchio
Jazyk: angličtina
Rok vydání: 2021
Předmět:
Zdroj: Physical Review Research, Vol 3, Iss 4, p 043015 (2021)
Druh dokumentu: article
ISSN: 2643-1564
DOI: 10.1103/PhysRevResearch.3.043015
Popis: 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.
Databáze: Directory of Open Access Journals
Pro tento záznam nejsou dostupné žádné jednotky.