Exactly solvable out-of-equilbrium dynamics: hydrodynamics of sorting algorithms

Equilibrium statistical mechanics and computation have a rich past, full of deep connections between machine learning, statistical modeling and quantum information. In contrast, many contemporary problems (such as error correction or image denoising) reside in the non-equilibrium domain, which is terra incognita. To this end, we 'introduce' exactly solvable classical circuits, modeling non-equilibrium dynamics in 1D: sorting algorithms from elementary computer science classes. We discuss a transfer-matrix-like exact solution to the dynamics for all time, which allows analytical computation of local observables via statistical moments. The (Eulerian) hydrodynamic limit of the dynamics is also discussed, revealing an unconventional advection equation with infinitely many conserved quantities. We also develop an effective 'statistical mechanics' description of the system, which can even capture the dynamics. Opening the system to a bath, we find a rich phase diagram of out-of-equilibrium phase transitions between computational complexity classes, connecting a 'fizzy' sorting phase to a 'flat' unsorting phase. Further study of the model entails unexpected connections to probability theory and suggests new directions for dynamics of classical/quantum permutation circuits.