Symmetry-protected sign problem and magic in quantum phases of matter

Understand

We introduce the concepts of a symmetry-protected sign problem and symmetry-protected magic to study the complexity of symmetry-protected topological (SPT) phases of matter.

• In particular, we say a state has a symmetry-protected sign problem or symmetry-protected magic, if finite-depth quantum circuits composed of symmetric gates are unable to transform the state into a non-negative real wave function or stabilizer state, respectively.
• We prove that states belonging to certain SPT phases have these properties, as a result of their anomalous symmetry action at a boundary.
• For example, we find that one-dimensional $\mathbb{Z}_2 \times \mathbb{Z}_2$ SPT states (e.g.