Making the Leap to Quantum PCPs

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


Duration: 50:16
451 views
10

Chinmay Nirkhe (IBM)
https://simons.berkeley.edu/talks/chinmay-nirkhe-ibm-2023-07-12
Quantum Summer Cluster Workshop

Last year, Anshu, Breuckmann, and I published a proof of the NLTS conjecture based on recent developments in quantum error-correcting codes. That result demonstrates the existence of robust entanglement even at low temperatures. Our motivation for studying NLTS was that it is a necessary precursor for the quantum PCP conjecture.

In this talk, I’ll speak about why our first construction of NLTS is based on codes and what I believe are the appropriate next questions to tackle for the quantum PCP conjecture. I’ll discuss the connections of these questions to other interesting problems in quantum complexity theory.

This talk will be math-light and intuition-heavy with a particular emphasis on identifying key challenges.



Other Videos By Simons Institute for the Theory of Computing


2023-07-19Introduction to Quantum Cryptography Without One-Way Functions
2023-07-15Approaching the Quantum Singleton Bound with Approximate Error Correction
2023-07-14Improved Machine Learning Algorithm for Predicting Ground State Properties
2023-07-14Learning Beyond Stabilizer States
2023-07-14Quantum Commitments and Black Hole Radiation Decoding
2023-07-14Geometry, Entropy and Complexity in Quantum Gravity (Part II)
2023-07-14Geometry, Entropy and Complexity in Quantum Gravity (Part I)
2023-07-13Dissipative State Preparation and the Dissipative Quantum Eigensolver
2023-07-13QMA and the Power of “Positivity”
2023-07-13Compiled Nonlocal Games: From CHSH to BQP Verification
2023-07-12Making the Leap to Quantum PCPs
2023-07-12How Simulating Balls and Springs Captures the Power of Quantum Computing
2023-07-12Quantum Algorithms for Approximating Partition Functions
2023-07-12Quantum Gibbs Sampling
2023-07-11Quantum Advantage with Shallow Clifford Circuits
2023-07-11Utility, Computational Cost, and Effective Quantum Volume of NISQ Experiments
2023-07-11A Phase Transition in Linear Cross-Entropy Benchmarking
2023-07-11Validated Quantum Advantage via Bell Sampling
2023-07-11Verifiable Quantum Supremacy: What I Hope Will Be Done
2023-07-01Representation Theory in TCS and Extremal Combinatorics
2023-07-01On Perfectly Friendly Bisections of Random Graphs


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Quantum Summer Cluster Workshop
Chinmay Nirkhe