CSE Colloquium: On the complexity of quantum many-body systems

Zoom Information: Join from PC, Mac, Linux, iOS or Android: https://psu.zoom.us/j/94951223472?pwd=bFlCNXZ1R0V2bzRsazZKZ284aUlOdz09 Password: 245822 

or iPhone one-tap (US Toll): +13017158592,94951223472# or +13126266799,94951223472# 

or Telephone: Dial: +1 301 715 8592 (US Toll) +1 312 626 6799 (US Toll) +1 646 876 9923 (US Toll) +1 253 215 8782 (US Toll) +1 346 248 7799 (US Toll) +1 669 900 6833 (US Toll) Meeting ID: 949 5122 3472 Password: 245822 International numbers available: https://psu.zoom.us/u/acpRFx1PDD 

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. 

BIOGRAPHY: The speaker is a postdoctoral researcher at the University of California, Berkeley. Prior to this, he was a joint postdoctoral researcher at the Institute for Quantum Computing and the Perimeter Institute for Theoretical Physics, Waterloo. He obtained his Ph D from the Centre for Quantum Technologies, National University of Singapore. He is interested in quantum complexity theory, quantum many-body physics, quantum communication and quantum learning theory. A unifying theme of his research in these areas is the interplay between computation and physics.