SPECIAL SEMINAR: Anurag Anshu, "Quantum Constraint Satisfaction Problems: Entanglement and Hardness-of-Approximation"

Event Type

Seminar/Symposium

Sponsor

Illinois Computer Science

Virtual

Date

Apr 2, 2021   10:00 am  

Contact

Kim Baker

E-Mail

kabaker@illinois.edu

Views

122

Originating Calendar

Computer Science Speakers Calendar

Abstract:  

Quantum many-body systems are the generalizations of constraint satisfaction problems (CSPs) to the quantum domain. The properties of these systems are largely determined by their ground states, which are analogous to solutions of CSPs.  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. 

1) The area law conjecture suggests a polynomial size of description in physically relevant ground states, by postulating that such ground states hold limited entanglement. We describe progress on this using computational tools: polynomial approximations to Boolean functions. 

2) The quantum PCP conjecture, on the other hand, proposes that a polynomial sized 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.

Bio: 

The speaker 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. He is interested in quantum complexity theory, quantum many-body physics, quantum communication and quantum learning theory. A unifying theme of his research in these areas is the interplay between computation and physics.

Faculty Host: Edgar Solomonik