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.

arXiv comment16 pages, 17 figures

References in corpus (48)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Annealing in the Transverse Ising Model
• Metal-insulator transition in a weakly interacting many-electron system with localized single-particle states
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical physics of inference: Thresholds and algorithms
• QuSpin: a Python Package for Dynamics and Exact Diagonalisation of Quantum Many Body Systems part I: spin chains
• Phase Transitions in the Coloring of Random Graphs
• Anderson localization casts clouds over adiabatic quantum optimization
• Review: Local Integrals of Motion in Many-Body Localized systems
• Clustering of solutions in the random satisfiability problem
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• First order phase transition in the Quantum Adiabatic Algorithm
• A Landscape Analysis of Constraint Satisfaction Problems
• Many-body mobility edge in a mean-field quantum spin glass
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• A ferromagnet with a glass transition
• Simplest random K-satisfiability problem
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• 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
• Exact solutions for diluted spin glasses and optimization problems
• On the freezing of variables in random constraint satisfaction problems
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• On the dynamics of the glass transition on Bethe lattices
• First-order transitions and the performance of quantum algorithms in random optimization problems
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• 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
• Population annealing: Theory and application in spin glasses
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Rethinking mean-field glassy dynamics and its relation with the energy landscape: the awkward case of the spherical mixed p-spin model
• Suboptimality of local algorithms for a class of max-cut problems
• Quantum annealing: the fastest route to quantum computation?
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
• Approximation schemes for the dynamics of diluted spin models: the Ising ferromagnet on a Bethe lattice
• Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inference
• A solvable model of quantum random optimization problems
• Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
• Complexity transitions in global algorithms for sparse linear systems over finite fields
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• Ergodic and localized regions in quantum spin glasses on the Bethe lattice
• Thresholds of descending algorithms in inference problems
• 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
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking

Cited by in corpus (5)

• 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
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking