  Quantum phases of matter are resources for notions of quantum computation. In
this work, we establish a new link between concepts of quantum information
theory and condensed matter physics by presenting a unified understanding of
symmetry-protected topological (SPT) order protected by subsystem symmetries
and its relation to measurement-based quantum computation (MBQC). The key
unifying ingredient is the concept of quantum cellular automata (QCA) which we
use to define subsystem symmetries acting on rigid lower-dimensional lines or
fractals on a 2D lattice. Notably, both types of symmetries are treated
equivalently in our framework. We show that states within a non-trivial SPT
phase protected by these symmetries are indicated by the presence of the same
QCA in a tensor network representation of the state, thereby characterizing the
structure of entanglement that is uniformly present throughout these phases. By
also formulating schemes of MBQC based on these QCA, we are able to prove that
most of the phases we construct are computationally universal phases of matter,
in which every state is a resource for universal MBQC. Interestingly, our
approach allows us to construct computational phases which have practical
advantages over previous examples, including a computational speedup. The
significance of the approach stems from constructing novel computationally
universal phases of matter and showcasing the power of tensor networks and
quantum information theory in classifying subsystem SPT order.
