The computational complexity of low-energy many-body quantum states

There is an inherent tension between the exponential complexity of quantum states and the possibility of studying quantum many-body physics. One of the important principles that makes quantum many-body physics tractable is that there are large classes of physical systems for which ground and low energy states are conjectured to have succinct classical descriptions. This is of course central to the issue of simulation of quantum systems. In recent decades, with the advent of quantum information and quantum computation, we have come to realize the importance of the entanglement structure in these systems for the complexity of simulating them. In particular, in 1D systems a complete picture has emerged, in which we now understand how ground states of gapped systems must satisfy an area-law of entanglement entropy. This has led to an efficient description of these states in terms of tensor networks.  This picture gives a formal justification for the enormous success of the DMRG algorithm for such 1D systems.

 

In 2D the problem is much more challenging: proving an area law for 2D systems is much harder than in 1D, and also calculations with 2D tensor-networks are much harder than in 1D - much like calculating the partition function of the 2D Ising model is much harder than the 1D case. Nevertheless, a sequence of improvements of the 1D results have led to a much better understanding of the entanglement structure of 2D systems, with a recent breakthrough of a proof of the 2D area law under some conditions. These recent results also motivate the search for new simulations of such 2D systems, with the hope of making many such 2D physical systems tractable, despite the fact that the problem in general is NP-hard.

 

In this talk I will describe this exciting story of the fruitful interaction between condensed-matter physics and quantum computation, which include ideas that span Computer Science, Math and Physics.

 

The talk will be in-person but also broadcasted through Zoom: https://technion.zoom.us/j/95179897101.