91̽»¨

Classical and Topological Quantum Spin Glasses in (q)LDPC codes

Ordered phases of matter have close connections to computation. Two prominent examples are spin glass order, with wide-ranging applications in machine learning and optimization, and topological order, closely related to quantum error correction.

Here, we show how expansion, a notion from code theory that guarantees efficient decodability, naturally implies glassiness in low density parity check (LDPC) codes. Concretely, we (i) provide a mathematically rigorous proof of spin glass order in a family of models with finite connectivity based on classical LDPC codes and (ii) identify a novel form of​ topological​ quantum spin glass order (TQSG) in models based on quantum LPDC codes. The TQSG phase combines the complex energy landscape of spin glasses with the long-range entanglement of topological ordered states. It also realizes a new mechanism for quantum self-correction via spin glass order, physically distinct from the spontaneous breaking of (higher-form) symmetries as realized e.g. in the four-dimensional Toric code. 

En route to proving these results, we develop a quantum generalization of Gibbs state decompositions and prove a bottleneck theorem for quantum channels, both of which we expect to be of independent interest.