The Unlearnable Phase

Non-trivial mixed-state phases of matter are provably computationally hard to learn through unsupervised methods.

The mechanism is precise. States in certain mixed-state phases have spatially indistinguishable partners — other states that look identical in every local measurement but belong to different phases. Conditional mutual information serves as the diagnostic: when it extends to long range, the phase contains such locally indistinguishable pairs. Autoregressive neural networks — the architecture underlying most generative models — provably cannot distinguish between them.

The proof uses a restricted statistical query model to establish that any efficient learning algorithm requires exponentially many samples to classify phases with extended conditional mutual information. This includes strong-to-weak spontaneous symmetry breaking phases. The result holds for recurrent networks, convolutional networks, and Transformers alike. The architecture doesn’t matter; the barrier is informational, not architectural.

Experiments on toric codes under bit-flip noise confirm the theoretical predictions. The neural networks fail exactly where the theory says they must — at the phase boundaries corresponding to error-correction thresholds.

The implication reverses the usual relationship between learning and physics. Normally, computational difficulty is a limitation of the observer. Here, it is a property of the phase itself. The inability to learn is not a failure of the algorithm but a signature of the physical state. Computational opacity becomes a measurable, classifiable physical property — something that can be used as a phase diagnostic rather than merely suffered as a limitation.

The universe has states whose structure is real but provably invisible to any efficient observer. These are not unknown phases waiting to be characterized. They are phases whose defining property is that efficient characterization is impossible. The phase exists; it just cannot be witnessed.