Entropic barriers as a reason for hardness in both classical and quantum algorithms
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. W...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2021-10-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/PhysRevResearch.3.043015 |