A broad range of quantum optimization problems can be phrased as the question of whether a specific system has a ground state at zero energy, i.e., whether its Hamiltonian is frustration-free or `satisfiable'. Frustration-free Hamiltonians, in turn, play a central role for constructing and understanding new phases of matter in quantum many-body physics.
In this informal talk, I will present a general criterion—the Shearer condition—under which a local Hamiltonian is guaranteed to be frustration-free. Remarkably, evaluating this condition proceeds via a fully classical analysis of a hardcore lattice gas at negative fugacity, leading to an unexpected connection between the dimension of the satisfying space and the Lee-Yang edge singularity. If time permits, I will further discuss the conjecture that the Shearer condition is `tight' for the quantum satisfiability problem (unlike in the classical case) and show how to use techniques from free probability theory in the large N limit to investigate it.