Simons Institute Courses

The Quantum Games PCP - Results and Confessions

Explore quantum complexity theory, focusing on the quantum PCP conjecture and its relation to interactive proof systems. Learn about recent developments and challenges in this cutting-edge field.

• YouTube
• 48 minutes
• Self-Paced
• Free Video

Circuit-To-Hamiltonian Mapping Using Tensor Networks and Fault Tolerance

Explores novel circuit-to-Hamiltonian mapping using tensor networks, avoiding clock registers. Discusses implications for quantum complexity, fault tolerance, and the quantum PCP conjecture.

• YouTube
• 36 minutes
• Self-Paced
• Free Video

NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes

Explores breakthroughs in complexity theory using low-rate quantum LDPC codes, improving NLTS Hamiltonians and Sum-of-Squares hierarchy lower bounds with novel code construction techniques.

• YouTube
• 44 minutes
• Self-Paced
• Free Video

Expansion of Higher-Dimensional Cubical Complexes with Application to Good Quantum Locally Testable Codes

Explore quantum locally testable codes, their optimal parameters, and connections to expander codes and qLDPC codes in this advanced talk on quantum complexity theory.

• YouTube
• 39 minutes
• Self-Paced
• Free Video

Local Minima in Quantum Systems

Explores computational challenges in finding local energy minima of quantum systems, comparing classical and quantum approaches and their implications for understanding Nature's cooling processes.

• YouTube
• 46 minutes
• Self-Paced
• Free Video

What on Earth Does Complexity Theory Have to Do with Gravity?

Explore the intriguing connection between complexity theory and gravity, delving into quantum PCP, area laws, and quantum gravity concepts.

• YouTube
• 1 hour 5 minutes
• Self-Paced
• Free Video

Classification of 2D Gapped Ground States With Strict Area Law

Explores classification of 2D gapped ground states with strict area law, showing conversion to generalized string-net Hamiltonian ground states using constant-depth quantum circuits.

• YouTube
• 50 minutes
• Self-Paced
• Free Video

Introduction to Commuting Local Hamiltonian Problems

Explore quantum complexity through commuting local Hamiltonian problems, focusing on quantum PCP, area laws, and quantum gravity connections.

• YouTube
• 48 minutes
• Self-Paced
• Free Video

How Quantum Complexity Found Its Way into Black Hole Physics

Explore the surprising connection between quantum complexity and black hole physics, uncovering new insights into horizon properties and the quantum extended Church Turing Thesis.

• YouTube
• 1 hour 12 minutes
• Self-Paced
• Free Video

Oracle Separations Between QMA and QCMA

Explores recent non-standard oracle separations between QMA and QCMA, discussing connections to sparse Hamiltonians and potential paths towards standard oracle separation.

• YouTube
• 47 minutes
• Self-Paced
• Free Video

Quantum Complexity of Clique Homology

Explore the quantum mechanical structure in topology, connecting complexity theory to QMA hardness and examining implications for quantum algorithms and PCPs.

• YouTube
• 44 minutes
• Self-Paced
• Free Video

Some Stories of Graphs and Geometry

Explore fascinating connections between graphs and geometry, uncovering intriguing mathematical insights and their applications in various fields.

• YouTube
• 37 minutes
• Self-Paced
• Free Video

Locality in Codes and Computation

Exploring local algorithms in error-correcting codes and their impact on computational theory, from error detection to cryptocurrency applications. Challenges and future directions discussed.

• YouTube
• 47 minutes
• Self-Paced
• Free Video

Quantum Constraint Satisfaction - Richard M. Karp Distinguished Lecture

Explore quantum Hamiltonian complexity, comparing it to classical constraint satisfaction. Learn about QMA-completeness, search-to-decision, dichotomy theorems, and coping with QMA-hardness in quantum applications.

• YouTube
• 1 hour 1 minute
• Self-Paced
• Free Video

Decoders for Good Quantum LDPC Codes

Explores linear-time decoders for asymptotically good quantum LDPC codes, discussing single-shot decoding and its implications for practical quantum error correction.

• YouTube
• 43 minutes
• Self-Paced
• Free Video