ON-LINE TensorTalk: Quantum techniques for Holant problems

Speaker: Radu Curticapean

Title: Quantum techniques for Holant problems

This talk presents recent work by Miriam Backens on connections between quantum information theory and the complexity of Holant problems, a particular class of combinatorial counting problems. Holant problems include the permanent and the partition functions of all vertex models in statistical physics. They can also be interpreted as contractions of tensor networks. 

By identifying previously unknown connections between QIT and Holant problems, Miriam's work contributed towards a dichotomy theorem for Holant problems, that is, a full classification into polynomial-time solvable versus #P-hard cases.

After an introduction to counting complexity, Holant problems, and previous techniques, this talk will outline the main ideas of the proofs, with an emphasis on connections to QIT. The talk is based on the following papers by Miriam Backens:

 https://drops.dagstuhl.de/opus/volltexte/2017/7438/pdf/LIPIcs-ICALP-2017-16.pdf

Join Zoom Meeting:

https://ucph-ku.zoom.us/j/520799911

Meeting ID: 520 799 911