activity
20192022
most citedEntropic barriers as a reason for hardness in both classical and quantum algorithms

5 citations · 9 across the 3 of their papers we have counts for

collaborators
Showing cond-mat.dis-nnShow all

1 paper · 1 filter

cond-mat.dis-nn2021★ 5 cited

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

Matteo Bellitti, Federico Ricci-Tersenghi, Antonello Scardicchio

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…