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

Abstract

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.

Accepted to PRL; 5 pages + 13 pages supplemental material, 1 + 1 figures

References in corpus (18)

• Entanglement versus Correlations in Spin Systems
• Diverging Entanglement Length in Gapped Quantum Spin Systems
• String order and symmetries in quantum spin lattices
• Novel schemes for measurement-based quantum computation
• Localizable Entanglement
• Measurement-based quantum computation beyond the one-way model
• Computational power of correlations
• Measurement-based quantum computer in the gapped ground state of a two-body Hamiltonian
• The contextual fraction as a measure of contextuality
• Quantum computation on the edge of a symmetry-protected topological order
• Experimental Realization of a Quantum Integer-Spin Chain with Controllable Interactions
• Resource quality of a symmetry-protected topologically ordered phase for quantum computation
• Analytic Relations between Localizable Entanglement and String Correlations in Spin Systems
• Symmetry protection of measurement-based quantum computation in ground states
• Non-adaptive Measurement-based Quantum Computation and Multi-party Bell Inequalities
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Modeling Pauli measurements on graph states with nearest-neighbor classical communication
• Cohomology and the Algebraic Structure of Contextuality in Measurement Based Quantum Computation

Cited by in corpus (11)

• Measurement-based quantum computation in finite one-dimensional systems: string order implies computational power
• The role of cohomology in quantum computation with magic states
• Playing quantum nonlocal games with six noisy qubits on the cloud
• Quantum computational advantage attested by nonlocal games with the cyclic cluster state
• Low-depth Clifford circuits approximately solve MaxCut
• Hierarchies of resources for measurement-based quantum computation
• Playing nonlocal games across a topological phase transition on a quantum computer
• Classification of measurement-based quantum wire in stabilizer PEPS
• Playing nonlocal games with phases of quantum matter
• A multi-player, multi-team nonlocal game for the toric code
• Entanglement and private information in many-body thermal states