  Measurement-based quantum computation (MQC) is a paradigm for studying
quantum computation using many-body entanglement and single-qubit measurements.
While MQC has inspired wide-ranging discoveries throughout quantum information,
our understanding of the general principles underlying MQC seems to be biased
by its historical reliance upon the archetypal 2D cluster state. Here, we
utilize recent advances in the subject of symmetry-protected topological order
(SPTO) to introduce a novel MQC resource state, whose physical and
computational behavior differs fundamentally from the cluster state. We show
that, in sharp contrast to the cluster state, our state enables universal
quantum computation using only measurements of single-qubit Pauli X, Y, and Z
operators. This novel computational feature is related to the "genuine" 2D SPTO
possessed by our state, and which is absent in the cluster state. Our concrete
connection between the latent computational complexity of many-body systems and
macroscopic quantum orders may find applications in quantum many-body
simulation for benchmarking classically intractable complexity.
