The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures

Abstract

The problem of optimizing over random structures emerges in many areas of science and engineering, ranging from statistical physics to machine learning and artificial intelligence. For many such structures finding optimal solutions by means of fast algorithms is not known and often is believed not possible. At the same time the formal hardness of these problems in form of say complexity-theoretic $NP$-hardness is lacking. In this introductory article a new approach for algorithmic intractability in random structures is described, which is based on the topological disconnectivity property of the set of pair-wise distances of near optimal solutions, called the Overlap Gap Property. The article demonstrates how this property a) emerges in most models known to exhibit an apparent algorithmic hardness b) is consistent with the hardness/tractability phase transition for many models analyzed to the day, and importantly c) allows to mathematically rigorously rule out large classes of algorithms as potential contenders, in particular the algorithms exhibiting the input stability (insensitivity).

26 pages, 6 figures, 1 table

References in corpus (9)

• A Quantum Approximate Optimization Algorithm
• The Loss Surfaces of Multilayer Networks
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• The Overlap Gap Property and Approximate Message Passing Algorithms for $p$-spin models
• Shattering Versus Metastability in Spin Glasses

Cited by in corpus (46)

• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Challenges and Opportunities in Quantum Optimization
• NLTS Hamiltonians from good quantum codes
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Quantum-Informed Recursive Optimization Algorithms
• Disordered Systems Insights on Computational Hardness
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert
• Energy landscapes of combinatorial optimization in Ising machines
• Hard Optimization Problems have Soft Edges
• Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• (Dis)assortative Partitions on Random Regular Graphs
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin Models
• On the free energy of vector spin glasses with non-convex interactions
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Statistical mechanics of the maximum-average submatrix problem
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Combinatorial NLTS From the Overlap Gap Property
• Gap Amplification for Reconfiguration Problems
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• On the topology of solutions to random continuous constraint satisfaction problems
• The Overlap Gap Property limits limit swapping in the QAOA
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• The phase diagram of compressed sensing with ${\ell }_0$-norm regularization
• Algebraic dynamical systems from LDPC codes satisfy a strong negation of the weak Pinsker property
• Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
• Quantum Glassiness From Efficient Learning
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Uniformly Random Colourings of Sparse Graphs
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Interacting Copies of Random Constraint Satisfaction Problems
• Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem
• Maximum Consensus by Weighted Influences of Monotone Boolean Functions