QAOA on the infinite SK model maps exactly to a spin-boson Hamiltonian whose ground-state energy can be computed with matrix-product states, yielding numerical evidence that depth O(n/ε^1.13) suffices for (1-ε) approximation in the average case.
Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
Given a graph $G$ of degree $k$ over $n$ vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth $2L$, we develop a local message passing algorithm whose complexity is $O(nkL)$, and that achieves near optimal cut values among all $L$-local algorithms. Focusing on max-cut, the algorithm constructs a cut of value $nk/4+ n\mathsf{P}_\star\sqrt{k/4}+\mathsf{err}(n,k,L)$, where $\mathsf{P}_\star\approx 0.763166$ is the value of the Parisi formula from spin glass theory, and $\mathsf{err}(n,k,L)=o_n(n)+no_k(\sqrt{k})+n \sqrt{k} o_L(1)$ (subscripts indicate the asymptotic variables). Our result generalizes to locally treelike graphs, i.e., graphs whose girth becomes $2L$ after removing a small fraction of vertices. Earlier work established that, for random $k$-regular graphs, the typical max-cut value is $nk/4+ n\mathsf{P}_\star\sqrt{k/4}+o_n(n)+no_k(\sqrt{k})$. Therefore our algorithm is nearly optimal on such graphs. An immediate corollary of this result is that random regular graphs have nearly minimum max-cut, and nearly maximum min-bisection among all regular locally treelike graphs. This can be viewed as a combinatorial version of the near-Ramanujan property of random regular graphs.
representative citing papers
Approximate stochastic localization plus conductance transfers yield a weak Poincaré inequality for the SK model at β < 1/2, enabling efficient Glauber sampling from a warm start.
Presents the first iterative spectral algorithm for near-optimal solutions to random quadratic optimization over the hypercube, resolving Subag's conjecture via potential Hessian ascent and SDE approximation.
Extends NP-hardness of exceeding r/q + O(1/sqrt(D)) for bounded-degree max-Ek-LINSAT(q,r) over F_q and shows quantum decoding is required for DQI to achieve the hardness-optimal 1/sqrt(D) scaling.
citing papers explorer
-
Spin-Boson Mapping of the Quantum Approximate Optimization Algorithm
QAOA on the infinite SK model maps exactly to a spin-boson Hamiltonian whose ground-state energy can be computed with matrix-product states, yielding numerical evidence that depth O(n/ε^1.13) suffices for (1-ε) approximation in the average case.
-
Weak Poincar\'e Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model
Approximate stochastic localization plus conductance transfers yield a weak Poincaré inequality for the SK model at β < 1/2, enabling efficient Glauber sampling from a warm start.
-
Potential Hessian Ascent: The Sherrington-Kirkpatrick Model
Presents the first iterative spectral algorithm for near-optimal solutions to random quadratic optimization over the hypercube, resolving Subag's conjecture via potential Hessian ascent and SDE approximation.
-
Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
Extends NP-hardness of exceeding r/q + O(1/sqrt(D)) for bounded-degree max-Ek-LINSAT(q,r) over F_q and shows quantum decoding is required for DQI to achieve the hardness-optimal 1/sqrt(D) scaling.