A Tale of Turing Machines, Quantum-Entangled Particles, and Operator Algebras

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=XReR87kFrS4


Duration: 55:19
6,197 views
165

Henry Yuen (University of Toronto)
Richard M. Karp Distinguished Lecture Series, Spring 2020
https://simons.berkeley.edu/events/rmklectures2020-spring-3

In a recent result known as "MIP* = RE," ideas from three disparate fields of study — computational complexity theory, quantum information, and operator algebras — have come together to simultaneously resolve long-standing open problems in each field, including a 44-year old mystery in mathematics known as Connes’ Embedding Problem. In this talk, I will describe the evolution and convergence of ideas behind MIP* = RE: it starts with three landmark discoveries from the 1930s (Turing’s notion of a universal computing machine, the phenomenon of quantum entanglement, and von Neumann’s theory of operators), and ends with some of the most cutting-edge developments from theoretical computer science and quantum computing.

This talk is aimed at a general scientific audience, and will not assume any specialized background in complexity theory, quantum physics, or operator algebras.



Other Videos By Simons Institute for the Theory of Computing


2020-04-28CCA encryption in the QROM I
2020-04-28LWE with Side Information: Attacks and Concrete Security Estimation
2020-04-27Quantum Secure Commitments and Collapsing Hash Functions
2020-04-27Quantum Cryptography (Beyond QKD)
2020-04-27Watermarking and Traitor Tracing for PRFs
2020-04-27New Techniques for Practical Lattice-Based Zero-Knowledge
2020-04-27Signatures, Commitments, Zero-Knowledge, and Applications
2020-04-23Post-Quantum Multi-Party Computation in Constant Rounds
2020-04-23Quantum Coupon Collector
2020-04-23Laconic Function Evaluation
2020-04-20A Tale of Turing Machines, Quantum-Entangled Particles, and Operator Algebras
2020-04-15Robust Polynomial Method and a Sub-Volume Law for Locally Gapped Frustration-Free Spin Systems
2020-04-13Optimal Broadcast Encryption from Pairings and LWE
2020-04-09Secure Multi-party Quantum Computation with a Dishonest Majority
2020-04-09Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving
2020-04-08NIZK from LPN and Trapdoor Hash via Correlation Intractability for Approximable Relations
2020-04-08Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
2020-04-07The Digital Fence: Taiwan’s Response to COVID-19
2020-04-06Lattices, Post-Quantum Security and Homomorphic Encryption — Q&A
2020-04-06Lattices, Post-Quantum Security and Homomorphic Encryption
2020-04-03What Do Algorithmic Fairness and COVID-19 Case-Severity Prediction Have in Common?


Tags:
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley
Henry Yuen
Richard M. Karp Distinguished Lecture Series