PIRSA:11050046

Nonlocal Games and Computational Complexity: A Survey

Ito, T. (2011). Nonlocal Games and Computational Complexity: A Survey. Perimeter Institute. https://pirsa.org/11050046

Ito, Tsuyoshi. Nonlocal Games and Computational Complexity: A Survey. Perimeter Institute, May. 13, 2011, https://pirsa.org/11050046 

          @misc{ pirsa_PIRSA:11050046,
            doi = {10.48660/11050046},
            url = {https://pirsa.org/11050046},
            author = {Ito, Tsuyoshi},
            keywords = {Quantum Foundations},
            language = {en},
            title = {Nonlocal Games and Computational Complexity: A Survey},
            publisher = {Perimeter Institute},
            year = {2011},
            month = {may},
            note = {PIRSA:11050046 see, \url{https://pirsa.org}}
          }

Tsuyoshi Ito Institute for Quantum Computing (IQC)

Talk numberPIRSA:11050046
DOI10.48660/11050046
Collection
Talk Type Conference
Subject

Abstract

A seminal work by Cleve, Høyer, Toner and Watrous (quant-ph/0404076) proposed a close connection between quantum nonlocality and computational complexity theory by considering nonlocal games and multi-prover interactive proof systems with entangled provers. It opened up the whole area of study of the computational nature of nonlocality. Since then, understanding nonlocality has been one of the major goals in computational complexity theory in the quantum setting. This talk gives a survey of this exciting area.