PHYSICS & COMPUTATION READING GROUP

This will be a reading group across Tufts, Harvard and MIT. The focus will be on analytic and probabilistic tools used to study the mathematical properties and algorithmic tractability of approximating (and sampling from statistics of) low-energy states of certain families of classical hamiltonians (spin glasses) and quantum hamiltonians (bosonic/fermionic systems).

Meeting Time: Thursdays, 11 AM - 1 PM EST

Location: Zoom room

Organizers: Saeed Mehraban, Juspreet Singh Sandhu

Recordings: Google Drive

Talk Schedule

• Lecture-1: Motivation & Introduction - Approximability and hardness in physics and computation
  • Speaker(s): Saeed, Juspreet
  • Date: 02/02/2023

No meeting on 02/09/2023, on account of the QIP conference scheduled 02/04/2023 through 02/10/2023

• Lecture-2: Barvinok’s method
  • Speaker: Saeed
  • Date: 02/16/2023
• Lecture-3: Deterministic counting and approximation of the permanent and partition functions I
  • Speaker: Saeed
  • Date: 02/23/2023
• Lecture-4: Deterministic counting and approximation of the permanent and partition functions II
  • Speaker: Saeed
  • Date: 03/02/2023
• Lecture-5: Overlap concentration in spin glasses and sparse random Max-CSPs I
  • Speaker: Juspreet
  • Date: 03/09/2023
• Lecture-6: Overlap concentration in spin glasses and sparse random Max-CSPs II
  • Speaker: Juspreet
  • Date: 03/16/2023
• Lecture-7: Matrix sum-of-squares optimization for spherical spin glasses
  • Speaker: Juspreet
  • Date: 03/23/2023
• Lecture-8: Stability of low-degree polynomials & Langevin dynamics
  • Speaker: Juspreet
  • Date: 03/30/2023
• Lecture-9: Open Discussion Session- Bridging the gap between different approximation techniques
  • Moderators: Saeed, Juspreet
  • Date: 04/06/2023
• Lecture-10: TBA
  • Speaker: TBA
  • Date: TBA

Relevant Papers

For a survey of Barvinok’s method, a good reference is the monograph by Barvinok [Bar] with Chapter-2 giving an overview of the technical toolkit, which uses complex analysis to study the roots of real-valued polynomials. Another source are the talks on “Computing Partition Functions” from the Simon’s workshop on the geometry of polynomials. A good historical reference for the overlap-gap property and its use in obstructing algorithms on random optimization problems is the survey by Gamarnik [G21]. A more technical survey is the one by Auffinger, Montanari and Subag [AMS22]. The three most accessible and comprehensive texts on the proof of the Parisi formula along with the applications of these techniques to solve other problems in mathematical and statistical physics are the ones by Talagrand ([Vol. 1],[Vol. 2]) and Panchenko [Pan13].

Deterministic Counting and Approximation of Quantum Hamiltonians

• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation [YL52].
• Completely Analytical Interactions: Constructive Description [DS87].
• Polynomial-Time Approximation Algorithms for the Ising Model [JS93].
• A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries [JSV].
• The Ising Partition Function: Zeros and Deterministic Approximation [LSS19].
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials [PR17].
• Classical Algorithms, Correlation Decay, and Complex Zeros of Partition Functions of Quantum Many-Body Systems [HMS19].
• Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits [AEM19].
• Approximating the Permanent of a Random Matrix with Vanishing Mean [EM18].
• The Computational Complexity of Linear Optics [AA10].
• The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs [SS12].

Analysis and Probability in Mean-Field Spin-Glasses

Interpolations, Ultrametricity and the TAP Approach

• The Thermodynamic Limit in Mean Field Spin Glass Models [GT02].
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model [Gue02].
• The Parisi Formula [Tal06].
  • On the Proof of the Parisi Formula by Guerra and Talagrand [Bol05].
• Ghirlanda-Guerra Identities and Ultrametricity: An Elementary Proof in the Discrete Case [Pan11].
• The Parisi Ultrametricity Conjecture [Pan13].
  • The Parisi Formula for Mixed p-Spin Models [Pan14].
• On the Energy Landscape of the Mixed Even p-Spin Model [CHL18].
• Thouless-Anderson-Palmer Equations for Generic p-Spin Glasses [AJ18].
  • The Thouless-Anderson-Palmer Equation in Spin Glass Theory [Bol08].
• The Generalized TAP Free Energy I, II [CPS18], [CPS21].

Analytic Properties of the Parisi Formula

• On Differentiability of the Parisi Formula [Pan08].
• On Properties of Parisi Measures [AC13].
• The Parisi Formula has a Unique Minimizer [AC14].
• Variational Representations for the Parisi Functional and the Two-Dimensional Guerra-Talagrand Bound [C16].
• The SK model is Infinite Step Replica Symmetry Breaking at Zero Temperature [ACZ20].

Overlap Concentration, Low-Degree Stability and Overlap-Gap Properties: Algorithmic Hardness

• Limits of Local Algorithms over Sparse Random Graphs [GJ14].
• Local Algorithms For Independent Sets Are Half-Optimal [VR17].
• Suboptimality of Local Algorithms for a Class of Max-Cut Problems [CGPR19].
• The Overlap Gap Property and Approximate Message Passing Algorithms for p-Spin Models [GJ21].
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [GJW20].
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses [HS21].
• Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond [CLSS22].
• Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses [JMSS22].