The complexity of approximating complex-valued partition functions

Lead Research Organisation: University of Oxford
Department Name: Computer Science

Abstract

Context of research and potential impact

Partition functions encode information of physical systems that arise in statistical mechanics, such as the Potts model or the hard-core model. Studying the computational complexity of evaluating a partition function at fixed parameters is a popular topic in complexity theory. In the case of the Potts model, this problem has been shown to be #P-hard but in some trivial parameters. Recent work mostly focuses on the complexity of approximating partition functions, where more interesting classifications arise. For example, the Potts model with parameters (q, y) is known to have a fully polynomial-time randomised approximation scheme when q = 2 and y > 1, but approximating this partition function can be even #P-hard at other values of q and y.

Due to the difficulty of completely resolving the complexity of the approximation problem, most of the work on the Potts model has restricted attention to real parameters. However, applications in quantum computation and statistical mechanics require consideration of complex numbers. This motivated the work of Goldberg and Guo, who studied the complexity of approximating the Potts model for q = 2. They proved that the problem is NP-hard when y is a non-real algebraic number other than i and -i, and #P-hard in some curves of the complex plane.

Aims, objectives and research methodology

1. We aim to extend the work of Goldberg and Guo and show that the approximation problem for the Potts model is #P-hard when q = 2 and y is a non-real algebraic number other than i and -i. Our approach consists in studying how to implement approximations of specific edges interactions when the original weight is a complex number. Results of this nature can be found in the literature only when the original weight is real. We hope that the tools developed can also be applied to other values of q and allow us to completely map the complexity of approximating this partition function.

2. We aim to determine the complexity of approximating the partition function of the Potts model when the considered graphs have bounded degree. To do so, we are going to adapt the techniques developed for the hard-core model in to the Potts model. These techniques are based on iterative multivariate rational maps.

This project falls within the EPSRC theoretical computer science research area.

Publications

10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509711/1 01/10/2016 30/09/2021
2218953 Studentship EP/N509711/1 01/10/2019 30/09/2022 Andres Herrera Poyatos
EP/R513295/1 01/10/2018 30/09/2023
2218953 Studentship EP/R513295/1 01/10/2019 30/09/2022 Andres Herrera Poyatos