Abstract The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising
variational quantum algorithm that aims to solve combinatorial optimization problems that …

In this review article we discuss connections between the physics of disordered systems,
phase transitions in inference problems, and computational hardness. We introduce two …

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 …

We consider the Sherrington-Kirkpatrick model of spin glasses at high-temperature and no
external field, and study the problem of sampling from the Gibbs distribution μ in polynomial …

The Quantum Approximate Optimization Algorithm can naturally be applied to combinatorial
search problems on graphs. The quantum circuit has p applications of a unitary operator that …

These notes survey and explore an emerging method, which we call the low-degree
method, for understanding statistical-versus-computational tradeoffs in high-dimensional …

Let A∈\mathbbR^n*n be a symmetric random matrix with independent and identically
distributed (iid) Gaussian entries above the diagonal. We consider the problem of …

Many high-dimensional statistical inference problems are believed to possess inherent
computational hardness. Various frameworks have been proposed to give rigorous …

We study the problem of algorithmically optimizing the Hamiltonian HN H_N of a spherical or
Ising mixed pp‐spin glass. The maximum asymptotic value OPT OPT of HN/N H_N/N is …

We establish the satisfiability threshold for random k-SAT for all k≥ k0. That is, there exists a
limiting density αs (k) such that a random k-SAT formula of clause density α is with high …