# On the complexity of quantum many-body systems

## Abstract

The quantum many-body system is a generalization of a classical constraint satisfaction problem, with the constraints described by its Hamiltonian. Central to its study are the ground states and their low energy approximations, the descriptions of which can potentially be exponentially long in the size of the system (number of particles). A fundamental question is to identify the conditions under which this description can be polynomial in the size. I will address this in three ways:

1) It has been conjectured that the ground states of physically relevant systems have a small description complexity. This is formalized in the far-reaching area law conjecture, which postulates limited entanglement in the ground states that live on low dimensional lattices. We describe a path towards this conjecture on two dimensional lattices, drawing tools from the theory of polynomial approximations to Boolean functions.

2) A small description complexity is not expected to hold in the most general ground states and their low energy approximations, which is the core of the conjectured quantum analogue of the PCP theorem. We provide evidence for the conjecture by deriving quantum circuit lower bounds on all quantum states that well-approximate the ground states of a large family of Hamiltonians derived from quantum codes. From a physics point-of-view, this shows that large entanglement and description complexity persist at fairly high temperatures in several many-body systems.

3) A large description complexity can be an obstacle to the study of future quantum devices. We discuss this in the context of learning and verification of an important family of quantum states -- the quantum Gibbs states -- and provide the first sample-efficient and rigorous algorithm for the task.

Bio:

The speaker is a postdoctoral researcher at the University of California, Berkeley, working in the field of quantum information and computation. Prior to this, he was a joint postdoctoral researcher at the Institute for Quantum Computing and the Perimeter Institute for Theoretical Physics. He obtained his PhD in Computer Science from the Center for Quantum Technologies, National University of Singapore.

Please join meeting in Sococo VH 102, or Zoom.

Join Zoom Meeting: https://tufts.zoom.us/j/91780023486

PASSWORD: see colloquium email

Dial-in option not available.