NLTS Hamiltonians from Codes | Quantum Colloquium

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


Duration: 1:04:45
1,803 views
27

Chinmay Nirkhe (IBM Research)
https://simons.berkeley.edu/events/quantum-colloquium-nlts-hamiltonians-codes
Quantum Colloquium

The quantum PCP conjecture is one of the central open questions in quantum complexity theory. It asserts that calculating even a rough approximation to the ground energy of a local Hamiltonian is intractable even for quantum devices. The widely believed separation between the complexity classes NP and QMA necessitates that polynomial length classical proofs do not exist for calculating the ground energy. This further implies that low-energy states of local Hamiltonians cannot be described by constant-depth quantum circuits.

The "No low-energy trivial states (NLTS)" conjecture by Freedman and Hastings posited the existence of such Hamiltonians. This talk will describe a line of research culminating in proofs of the NLTS conjecture by Anshu, Breuckmann, and Nirkhe and a recent simplification by He and Nirkhe. The construction is based on quantum error correction and in the talk, I will elaborate on how error correction, local Hamiltonians, and low-depth quantum circuits are related.



Other Videos By Simons Institute for the Theory of Computing


2022-10-26The Effect of Restrictive Interactions between Susceptible and Infected Individuals...
2022-10-26Linear Growth of Quantum Circuit Complexity
2022-10-26Mathematics of the COVID-19 Pandemics: Lessons Learned and How to Mitigate the Next One
2022-10-25Efficient and Targeted COVID-19 Border Testing via Reinforcement Learning
2022-10-25Random Walks on Simplicial Complexes for Exploring Networks
2022-10-25Functional Law of Large Numbers and PDEs for Spatial Epidemic Models with...
2022-10-25Algorithms Using Local Graph Features to Predict Epidemics
2022-10-24Epidemic Models with Manual and Digital Contact Tracing
2022-10-21Pandora’s Box: Learning to Leverage Costly Information
2022-10-20Thresholds
2022-10-19NLTS Hamiltonians from Codes | Quantum Colloquium
2022-10-15Learning to Control Safety-Critical Systems
2022-10-14Near-Optimal No-Regret Learning for General Convex Games
2022-10-14The Power of Adaptivity in Representation Learning: From Meta-Learning to Federated Learning
2022-10-14When Matching Meets Batching: Optimal Multi-stage Algorithms and Applications
2022-10-13Optimal Learning for Structured Bandits
2022-10-13Dynamic Spatial Matching
2022-10-13New Results on Primal-Dual Algorithms for Online Allocation Problems With Applications to ...
2022-10-12Learning Across Bandits in High Dimension via Robust Statistics
2022-10-12Are Multicriteria MDPs Harder to Solve Than Single-Criteria MDPs?
2022-10-12A Game-Theoretic Approach to Offline Reinforcement Learning


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