  We study a mechanism whereby quantum information present in the initial state
of a quantum many-body system can be protected for arbitrary times due to a
combination of symmetry and spatial locality. Remarkably, the mechanism is
sufficiently generic that the dynamics can be fully ergodic upon resolving the
protecting symmetry and fixing the encoded quantum state, resulting in an
infinite-temperature quantum memory. After exemplifying the mechanism in a
strongly nonintegrable two-dimensional (2D) spin model inspired by the surface
code, we find it has a natural interpretation in the language of noiseless
subsystems and stabilizer subsystem codes. This interpretation yields a number
of further examples, including a nonintegrable Hamiltonian with quantum memory
based on the Bacon-Shor code. The lifetime of the encoded quantum information
in these models is infinite provided the dynamics respect the stabilizer
symmetry of the underlying subsystem code. In the presence of
symmetry-violating perturbations, we make contact with previous work leveraging
the concept of prethermalization to show that the encoded quantum information
retains a parametrically long lifetime under dynamics with an enlarged
continuous symmetry group. We identify conditions on the underlying subsystem
code that enable such a prethermal enhancement of the memory lifetime.
