Symmetry-protected Sign Problem and Magic in Quantum Phases of Matter

We introduce the concepts of a symmetry-protected sign problem and symmetry-protected magic, defined by the inability of symmetric finite-depth quantum circuits to transform a state into a non-negative real wave function and a stabilizer state, respectively. We show that certain symmetry-protected topological (SPT) phases have these properties, as a result of their anomalous symmetry action at a boundary. For example, one-dimensional Z₂ × Z₂ SPT states (e.g. cluster state) have a symmetry-protected sign problem, and two-dimensional Z₂ SPT states (e.g. Levin-Gu state) have both a symmetry-protected sign problem and magic. We also comment on the relation of a symmetry-protected sign problem to the computational wire property of one-dimensional SPT states and the greater implications of our results for measurement based quantum computing.