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

Understand

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 (SPTOs), when a discrete invariant of a SPTO known as a twist phase is nontrivial and -1.
• Our construction demonstrates that sufficiently large string order parameters of such SPTOs are indicative of globally constrained correlations useful for the unconditional computational separation.