Complexity of Local Hamiltonians via Polynomial Approximations to AND Function

Speaker: Anurag Anshu , Berkeley

Date: Tuesday, March 29, 2022

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G449 (Kiva)

Event Type: Seminar

Room Description: 32-G449 (Kiva)

Host: Sam Hopkins & Dor Minzer, CSAIL MIT

Contact: Nathan Higgins, nhiggins@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: theory-seminars@lists.csail.mit.edu, seminars@lists.csail.mit.edu

Reminder Subject: 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. [1996]; Burhman et. al. [1999]). 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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2022.

Created by Nathan Higgins at Wednesday, March 09, 2022 at 9:33 AM.