Seminars & Colloquia
University of California, Berkeley
"Quantum constraint satisfaction problems: entanglement and hardness-of-approximation"
Friday March 05, 2021 02:30 PM
Location: zoom, EB2 NCSU Centennial Campus
Zoom Meeting Info (Visitor parking instructions)
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 a path towards 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.
Host: Frank Mueller, CSC