A cold dilute atomic gas collectively scatters light into an optical resonator when illuminated by laser light from the side. This leads to a complex coupled atom-field dynamics, including all-to-all atom-atom interactions and cavity cooling. For a sufficiently high laser power, the atoms’ steady state undergoes a phase transition from homogeneous to crystalline order. When applying several laser beams scattered into cavity modes with distinct spatial structure, a multitude of meta-stable ordered patterns emerges. As opposed to the single-mode case, attaining the optimally scattering state is not trivial anymore due to the existence of local minima in the energy landscape. By numerical simulations of the semi-classical dynamics we show that the stationary state strongly depends on the laser intensity ramp speed and the initial temperature. 

The task of solving hard optimization problems can be recast into the minimization of a multivariate cost function.  We show that the cost function can be emulated by the cavity-mediated all-to-all interactions, rendering the system described above a potential platform for solving optimization problems. In the quantum realm, ultra-cold bosons in optical lattices in a cavity can be used to implement a form of quantum annealing. In this vein, we propose a special purpose quantum simulator aimed at solving the N-queens problem. Variations of the N-queens problem are NP-complete and classically hard instances exist for relatively small atom numbers. Our implementation has no overhead from the embedding allowing to directly probe for a possible quantum speed-up in near term devices.