Quantum Computational Advantage with String Order Parameters of One-Dimensional 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 limited 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.

Figure 1

Triangle game. (a) Players fill in the row or column of their table with a binary string if their input is 0 or 1, respectively. (b) The win conditions. Apart from the global even parity of the output, the dark and light shaded boxes denote that each entry in the row jointly have even parity. The Penrose triangle represents the condition that the top, bottom, and left entries of any clockwise ordering of the three players have odd parity. (c) Quantum strategy for the triangle game. For each pair of Pauli observables in the table, the left one corresponds to the qubit located at the corresponding corner of the triangle. Perfection of the strategy is ensured by five cluster state stabilizers, whose eigenvalues are $\pm 1$ as shown. (d) Multiplayer triangle game (see [70]). Three arbitrary players, depicted at the corners of the triangle, measure the same Pauli observables as before on the $2n$-qubit cluster state and otherwise measure along the row. They still win the original game perfectly (up to inconsequential additional outputs by the other $n-3$ players). (e) Perfect quantum strategy on 1D SPTO fixed-point states is ensured when players measure on-site symmetry and boundary operators. The Penrose-triangle constraints in (c) manifest as a collective measurement of twisted string order parameters whose expectation value is an invariant of SPTOs, called a twist phase $\mathrm{\Omega }(g,h)$, equal to $-1$.