PIRSA:11050046

Nonlocal Games and Computational Complexity: A Survey

APA

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

MLA

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

BibTex

          @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)

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.