A Tale of Turing Machines, Quantum-Entangled Particles, and Operator Algebras
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore the convergence of computational complexity theory, quantum information, and operator algebras in this Richard M. Karp Distinguished Lecture. Delve into the groundbreaking "MIP* = RE" result, which resolves long-standing problems across multiple fields, including the 44-year-old Connes' Embedding Problem. Trace the evolution of ideas from the 1930s, covering Turing's universal computing machine, quantum entanglement, and von Neumann's operator theory, to cutting-edge developments in theoretical computer science and quantum computing. Gain insights into nonlocal games, interactive proofs, probabilistic checking, and the complexity of entanglement. Suitable for a general scientific audience, this talk requires no specialized background in complexity theory, quantum physics, or operator algebras.
Syllabus
Intro
Theory of Computing
The 1930s
The EPR paradox (1935)
A nonlocal game
The genesis of operator algebras
A zoo of algebras
A mysterious animal
A universal machine and unsolvable problem
Verifying vs finding proofs
The proofs revolution
Verifying proofs interactively
The power of interactivity
Probabilistic checking of proofs
Interactive proofs and entanglement
The complexity of entanglement
An unexpected connection
A candidate algorithm
The proof (from a thousand miles away)
The many facets of MIP* = RE
A Frequently Asked Question
A parable
Taught by
Simons Institute
Related Courses
理论计算机科学基础 | Introduction to Theoretical Computer SciencePeking University via edX 算法设计与分析(高级) | Advanced Design and Analysis of Algorithms
Peking University via edX The Introduction to Quantum Computing
Saint Petersburg State University via Coursera Computational Complexity Theory
Indian Institute of Technology Kanpur via Swayam Computational Complexity
IIT Hyderabad via Swayam