  Symmetry-protected topological (SPT) phases are many-body quantum states that
are topologically nontrivial as long as the relevant symmetries are unbroken.
In this work we show that SPT phases are also well defined for average
symmetries, where quenched disorders locally break the symmetries, but restore
the symmetries upon disorder averaging. An example would be crystalline SPT
phases with imperfect lattices. Specifically, we define the notion of average
SPT for disordered ensembles of quantum states. We then classify and
characterize a large class of average SPT phases using a decorated domain wall
approach, in which domain walls (and more general defects) of the average
symmetries are decorated with lower dimensional topological states. We then
show that if the decorated domain walls have dimension higher than $(0+1)d$,
then the boundary states of such average SPT will almost certainly be
long-range entangled, with probability approaching $1$ as the system size
approaches infinity. This generalizes the notion of t'Hooft anomaly to average
symmetries, which we dub "average anomaly". The average anomaly can also
manifest as constraints on lattice systems similar to the Lieb-Schultz-Mattis
(LSM) theorems, but with only average lattice symmetries. We also generalize
our problem to "quantum disorders" that can admit short-range entanglement on
their own, and develop a theory of such generalized average SPTs purely based
on density matrices and quantum channels. Our results indicate that topological
quantum phenomena associated with average symmetries can be at least as rich as
those with ordinary exact symmetries.
