Computational protection in quantum many-body systems

Computational complexity places fundamental limits on the time required to solve a problem, regardless of whether one uses classical or quantum resources. In the quantum adiabatic paradigm, computation proceeds by slowly deforming a Hamiltonian whose ground state does not encode the answer into one whose ground state does, with the runtime set by the minimum spectral gap encountered along the interpolation. Nontrivial computational complexity intrinsically precludes the existence of a fully gapped adiabatic path between these two low-energy subspaces, thereby enforcing a quantum phase transition. This raises a natural question: in what sense can computational-complexity barriers protect quantum phases? In this work, we develop a framework to address this question explicitly. By analyzing concrete one- and two-dimensional local Hamiltonians inspired by elementary arithmetic, we illustrate how computational structure can protect distinct patterns of long-range correlations, and therefore distinct many-body phases. We further discuss how this perspective offers computational insights into several fundamental phenomena in quantum many-body physics, including higher-form symmetries and mixed-state phases.