Spontaneous Symmetry Breaking via Regularization: Hardness and Approximation

Symmetries in physical systems are often encoded as invariances of an energy functional, or Hamiltonian. Spontaneous symmetry breaking (SSB) occurs when a Hamiltonian is invariant under a symmetry group, while its ground states, i.e., global minimizers, retain only a proper residual subgroup of those symmetries. From an optimization perspective, this creates a fundamental obstruction: equivariant optimization methods, such as gradient descent, cannot escape the symmetry class of their initialization and therefore cannot reach symmetry-breaking ground states when initialized at highly symmetric states. Despite the central role of SSB in physics, its computational and optimization-theoretic aspects remain poorly understood. In this work, we initiate a rigorous study of SSB through the lens of regularized optimization. We formulate symmetry breaking as minimizing a Hamiltonian together with a regularization term that rewards states with reduced residual symmetry. We show that, for general symmetry groups, the resulting regularized SSB problem is NP-hard to approximate within any constant factor, even when the Hamiltonian landscape contributes no computational difficulty. For compact groups, we develop a tractable randomized relaxation that provides a constant-factor approximation guarantee and reduces the problem from optimization over both group elements and states to optimization over states alone. This relaxation naturally yields a stochastic surrogate objective whose stationary points serve as efficient certificates of symmetry breaking. Finally, we establish convergence guarantees for finding such certificates using stochastic Frank-Wolfe methods. To our knowledge, this work introduces the first general optimization-theoretic framework for regularized spontaneous symmetry breaking, establishing a new connection between symmetry breaking in physical systems and optimization theory.