Quantum computational advantage with string order parameters of 1D symmetry-protected topological order

Nonlocal games with advantageous quantum strategies give arguably the most fundamental demonstration of the power of quantum resources over their classical counterparts. Recently, certain multiplayer generalizations of nonlocal games have been used to prove unconditional separations between small computational complexity classes of shallow-depth circuits. Here, we show advantageous strategies for these nonlocal games for generic ground states of one-dimensional symmetry-protected topological orders (SPTO), when an invariant of SPTO known as a twist phase is nontrivial and -1. Our construction demonstrates that general 1D SPTO with sufficiently large string order parameters possess globally constrained correlations useful for the unconditional computational separation.