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: | Matteo Bellitti, Federico Ricci-Tersenghi, Antonello Scardicchio |
---|---|
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 |
Similar Items
-
Limits and Performances of Algorithms Based on Simulated Annealing in Solving Sparse Hard Inference Problems
by: Maria Chiara Angelini, et al.
Published: (2023-04-01) -
Fluctuations, Entropic Quantifiers and Classical-Quantum Transition
by: Flavia Pennini, et al.
Published: (2014-02-01) -
Entropic Aspects of Nonlinear Partial Differential Equations: Classical and Quantum Mechanical Perspectives
by: Angelo Plastino
Published: (2017-04-01) -
Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
by: Maxime Dupont, et al.
Published: (2022-12-01) -
Quantum algorithms for attacking hardness assumptions in classical and post‐quantum cryptography
by: J.‐F. Biasse, et al.
Published: (2023-03-01)