Juspreet Sandhu from Harvard University is visiting QuTech, and will be giving a talk on Monday July 11th at 15:30-16:30hrs on "Spin-glass theory, quantum inapproximability and convex optimization".

Abstract: Since 2003, major progress has been made in confirming, from a mathematically rigorous view, the fundamental work of Parisi about the theory of Replica-Symmetry Breaking for the Sherrington-Kirkpatrick Model. This includes the seminal work by Guerra & Talgrand that culminated in the proof of the Parisi principle, and the work of Panchenko that proved the Parisi Ultrametricity conjecture, showing en-route that Mean-Field Spin Glasses satisfy the famed Ghirlanda-Guerra identities. Even more recently, the mathematical machinery developed in proving these landmark results has had algorithmic implications, beginning to give a geometric theory for understanding when typical instances of certain optimization problems are hard for various families of natural algorithms, and when efficient optimization is actually possible. This emerging dichotomy builds on the so-called "Overlap Gap Property", which is a clustering phenomenon exhibited by near-optimal solutions to certain optimization problems.
In this talk, we will briefly review the landmark rigorous results in the theory of Mean-Field Spin Glasses, and then introduce a statement of the Overlap-Gap Property and give some geometric intuition for the property. The presence of this property leads to an assortment of hardness results, while its absence typically guarantees efficient algorithms - We will mention prior results that illustrate this dichotomy. We will then conclude by discussing two results by my collaborators & I that contribute further to this emerging dichotomy with ramifications for Quantum Optimization.
The two results are:
1) A result that obstructs all local quantum algorithms (suitably defined) from well-approximating typical instances of constraint satisfaction problems that satisfy a version of the Overlap-Gap Property.
2) A result that gives an efficient Sum-of-Squares algorithm to find near-optimal ground states for typical instances of Spherical Spin Glasses under a no-Overlap Gap Property (or, equivalently, assuming full-Replica Symmetry Breaking).
Based on prior work with Chi-Ning Chou, Peter J. Love and Jonathan Shi, as well as ongoing work with Tommaso D'Orsi and Jonathan Shi.