Complexity of Local Hamiltonians via Polynomial Approximations to AND Function
Date: Tuesday, March 29, 2022
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Location: 32-G449 (Kiva)
Event Type: Seminar
Room Description: 32-G449 (Kiva)
Host: Sam Hopkins & Dor Minzer, CSAIL MIT
Contact: Nathan Higgins, email@example.com
Speaker URL: None
TALK: Complexity of Local Hamiltonians via Polynomial Approximations to AND Function
Local hamiltonians are the quantum analogues of constraint satisfaction problems. Two central questions in quantum complexity theory and quantum many-body physics concern the hardness of approximating ground energy of generic local hamiltonians (the quantum PCP conjecture) and the structure of ground states of gapped local hamiltonians (the area law conjecture). We will discuss seemingly unrelated progress on these conjectures that end up using the same tool: optimal polynomial approximations to the AND function (Linial et. al. ; Burhman et. al. ). In the first case, these polynomial approximations are used to obtain quantum circuit lower bounds on low energy states of quantum error correcting codes. Such quantum circuit lower bounds are a necessary consequence of the quantum PCP conjecture. In the second case, a non-commutative generalization of these polynomial approximations is obtained, which helps prove that two dimensional `frustration-free locally gapped' ground states possess limited entanglement. Based on the works arxiv:2011.02044 and arxiv:2103.02492.
Milk & Cookies will be served.
Created by Nathan Higgins at Wednesday, March 09, 2022 at 9:33 AM.