Stay Informed:
Baskin Engineering COVID-19 Information and Resources
Campus Roadmap to Recovery
Zoom Links: Zoom Help | Teaching with Zoom | Zoom Quick Guide

Quantum Constraint Satisfaction Problems: Entanglement and Hardness-of-Approximation

Speaker Name: 
Anurag Anshu
Speaker Title: 
Postdoctoral Researcher
Speaker Organization: 
UC Berkeley
Start Time: 
Wednesday, March 31, 2021 - 11:00am
End Time: 
Wednesday, March 31, 2021 - 12:15pm
Via Zoom Link
Daniel Fremont


Quantum many-body systems are the generalizations of the constraint satisfaction problems to the quantum domain. The properties of these systems are largely determined by their ground states, which are analogous to solutions of the constraints satisfaction problems.  The ground states exhibit novel quantum features which are important in quantum computing and low-temperature physics. However, these states can be highly complex, potentially requiring exponentially many bits in their description. The efforts to gain insights into this complexity have led to the far-reaching area law and quantum PCP conjectures. In this talk, we will discuss recent progress on these conjectures and on the goal of characterizing ground states that admit a short description. 

The area law conjecture suggests a short description in physically relevant ground states, by postulating that such ground states hold limited entanglement. We describe a path towards this using computational tools inspired by polynomial approximations to Boolean functions. The quantum PCP conjecture, on the other hand, proposes that a short description does not exist for the most general ground states and their low energy approximations. Freedman and Hastings put forward an important step towards this, focusing on quantum circuits as the descriptions of many-body quantum states. We highlight a progress on their pivotal conjecture, which sets limitations on the ability of shallow quantum circuits to capture the low energy states. We will also discuss the problem of learnability of an important approximation to the ground states -- the quantum Gibbs state -- and provide the first sample-efficient algorithm for the task. This is a step towards the general problem of learning and verifying many-body quantum states arising naturally in quantum devices.



Anurag Anshu is a postdoctoral researcher at the University of California, Berkeley. Prior to this, he was a joint postdoctoral researcher at the Institute for Quantum Computing and the Perimeter Institute for Theoretical Physics, Waterloo. He obtained his PhD from the Centre for Quantum Technologies, National University of Singapore, on August 31, 2018, in Computer Science. He is interested in quantum complexity theory, quantum many-body physics, quantum communication and quantum learning theory. 

Zoom Link: 


Event Type: