Tibor Rakovszky: Spin glass order in classical and quantum LDPC codes

Spin glasses constitute an important family of problems in statistical physics, characterized by a complex "rugged" free energy landscape with a large number of local minima. As such, they go beyond the usual paradigm of symmetry breaking order and have important connections to computer science. While many archetypical models of spin glasses involve all-to-all interactions, it is important to understand the behavior in systems with finite connectivity, where rigorous results are harder to obtain. In this work, we revisit this problem in the context of so-called low-density parity check (LDPC) codes and we rigorously establish the existence of spin glass order in a large family of such models, building on techniques developed in the context of error correction. We then generalize these results to quantum LDPC codes and show that these can realize a novel "topological quantum spin glass", which combines properties of spin glasses with those of quantum topological order, such as long-range entanglement. Along the way, we prove a theorem about the relaxation times of quantum channels, generalizing the so-called bottleneck theorem for classical Markov chains, which is of independent interest.