Unlearnable phases of matter

1. Problem Statement

The paper addresses a fundamental gap in understanding the limitations of machine learning (ML), specifically in unsupervised learning (density estimation). While supervised learning has known hard instances (e.g., parity functions), the classes of data distributions that are inherently hard to learn in an unsupervised setting, and the physical properties responsible for this "unlearnability," remain poorly understood.

The authors investigate whether non-trivial mixed-state phases of matter—characterized by specific correlation structures—can be efficiently learned by neural networks. They posit that certain phases, defined by Locally Indistinguishable (LI) states and long-range Conditional Mutual Information (CMI), present computational barriers that prevent neural networks from learning global properties of the distribution.

2. Methodology

The authors employ a combination of theoretical proofs, statistical learning theory, and extensive numerical simulations.

A. Theoretical Framework: Restricted Statistical Query (SQ) Model

• Local SQ Model: The authors introduce a restricted $\ell$-local Statistical Query (SQ) model to capture the essence of gradient-based training in autoregressive neural networks (RNNs, CNNs, Transformers). In this model, the learning algorithm can only query expectations of functions $\phi(x)$ that depend on at most $\ell$ spins (local operators).
• Justification: They argue that:
  1. Neural networks exhibit a "simplicity bias," prioritizing local features.
  2. If the target distribution is LI with a local Gibbs state, the noisy gradient descent trajectory remains within the space of local Gibbs states, effectively simulating local SQ.
  3. For contractive RNNs, the query functions are explicitly local.

B. Key Physical Concepts

• Locally Indistinguishable (LI) States: Two states $\rho_1$ and $\rho_2$ are LI if they have identical local observables (up to an exponentially small error) but differ globally.
• Conditional Mutual Information (CMI): Defined as $I(A:C|B)$. The authors establish a critical link:
  • Long-range CMI implies the existence of a spatially LI partner.
  • Conversely, for 1D systems, LI implies long-range CMI.
• Strong-to-Weak Spontaneous Symmetry Breaking (SWSSB): A class of mixed-state phases where global symmetry is broken in a way that creates LI states with different symmetry charges (e.g., even vs. odd parity).

C. Numerical Validation

The authors train various autoregressive architectures (LSTM/RNN, Convolutional Neural Networks (CNN), and Transformers) on:

1. Toric Code Syndrome Distribution: Under bit-flip noise.
2. Surface Code Distribution: Under decoherence.
3. 1D Repetition Code: As a toy model.
4. Ising Model: Ferromagnetic ground states.

They measure performance using KL Divergence and the ability to recover global symmetry charges (e.g., global parity).

3. Key Contributions & Theoretical Results

A. Hardness of Learning LI States

The authors prove that LI states cannot be learned efficiently under the local SQ model.

• Proof Mechanism: If two target distributions $\rho_1$ and $\rho_2$ are LI, their training trajectories under noisy gradient descent are super-polynomially close. The mutual information between the oracle responses and the specific target state is negligible.
• Result: The network can learn a mixture of LI states but fails to distinguish between them, effectively failing to learn the global observable that distinguishes them.

B. Easiness of Short-Range CMI States

In contrast, they prove that distributions with short-ranged CMI (finite Markov length $\xi$) in quasi-1D geometries are efficiently learnable.

• Method: By partitioning the system into intervals and using local SQ to perform tomography on marginals, the full distribution can be reconstructed with polynomial resources (based on Theorem B.1 of Ref. [39]).

C. Equivalence of Long-Range CMI and LI

• Theorem: For classical distributions, long-range CMI (where $I(A:C|B) = O(1)$ for large $B$) implies the existence of a spatially LI partner.
• Implication: Phases characterized by long-range CMI (such as SWSSB phases) are inherently hard to learn because the network cannot distinguish the global symmetry sector.

D. Connection to Error Correction

The authors demonstrate that the unlearnability threshold coincides precisely with the error-correction threshold ($p_c$) in quantum codes.

• Below $p_c$: Logical information is preserved, the state is in a non-trivial phase (LI), and learning is hard.
• Above $p_c$: Logical information is lost, the state becomes trivial (maximally mixed), and learning becomes easy.

4. Results

Numerical Findings

1. Toric Code (SWSSB Phase):
   • For noise rates $p_{err} > p_c \approx 0.11$, the syndrome distribution enters the SWSSB phase.
   • Neural networks (CNNs, RNNs, Transformers) successfully minimize the KL divergence but fail to learn the global parity ($\langle \prod Z_i \rangle \to 0$).
   • The KL divergence is lower-bounded by $\log 2$, indicating the network learns the equal mixture of the two symmetry sectors rather than the specific target.
2. Surface Code:
   • Similar behavior observed. The difficulty of learning a specific logical sector (fixed logical information) vs. no logical information peaks at the critical point $p_c$.
   • The difference in KL divergence ($\Delta S$) between learning a fixed logical state and the logical-free state drops from $\log 2$ to $0$ as noise crosses the threshold, serving as a diagnostic for the decoding transition.
3. 1D Toy Model (Repetition Code):
   • Analytical calculation shows that the gradient of the loss function with respect to the noise parameter vanishes exponentially with system size ($\sim e^{-n}$) when the target is in the LI phase (parity distribution), causing training to stall unless initialized exactly at the target.

5. Significance and Implications

• New Diagnostic Tool: "Hardness of learning" serves as a novel computational probe for detecting mixed-state phases of matter and phase transitions. Unlike traditional methods requiring full state tomography, unlearnability can be detected via the failure of neural networks to capture global symmetries.
• Error Correction Thresholds: The transition from learnable to unlearnable distributions provides a method to detect error-correction thresholds in both numerical simulations and quantum experiments.
• Machine Learning Theory:
  • Identifies CMI and LI as fundamental metrics for the hardness of learning distributions.
  • Suggests that "simplicity bias" in neural networks (preference for low-degree terms in Fourier-Walsh expansion) is the mechanism that makes LI states unlearnable.
  • Provides a theoretical basis for why certain complex distributions (like those in topological phases) are difficult for current AI models to generalize.
• Security and AI Safety: The work suggests that techniques used in quantum error correction to hide information from an environment (making it locally indistinguishable) could be adapted to hide data from machine learning models, offering new avenues for data privacy and AI safety.

Conclusion

The paper establishes a rigorous link between the physics of mixed-state phases and the computational limits of machine learning. It demonstrates that non-trivial mixed-state phases characterized by locally indistinguishable states and long-range CMI are fundamentally unlearnable by standard gradient-based neural networks. This unlearnability is not a failure of the architecture but a fundamental property of the data distribution, which can be exploited as a powerful diagnostic tool for identifying phase transitions and error thresholds in physical systems.