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

Abstract

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 tunnelling under large barriers, but does, nonetheless, give rise to exponential running (annealing) times.

16 pages, 17 figures

References in corpus (17)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• QuSpin: a Python Package for Dynamics and Exact Diagonalisation of Quantum Many Body Systems part I: spin chains
• Clustering of solutions in the random satisfiability problem
• A Landscape Analysis of Constraint Satisfaction Problems
• Many-body mobility edge in a mean-field quantum spin glass
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• On the freezing of variables in random constraint satisfaction problems
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Quantum annealing: the fastest route to quantum computation?
• A solvable model of quantum random optimization problems
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
• The effect of quantum fluctuations on the coloring of random graphs

Cited by in corpus (4)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• Localization in the Discrete Non-Linear Schrödinger Equation and geometric properties of the microcanonical surface