Quantum Constraint Satisfaction Problems: Entanglement and Hardness-of-Approximation
Thursday, March 11, 2021 3pm
About this Event
Please register here to join us for the CS Colloquium Series 2020-21 via Zoom. Once you register, you will receive a recurring Zoom link. You only need to register once to be able to attend any of the seminars.
---
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 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.