Document Open Access Logo

The Complexity of Approximating the Complex-Valued Potts Model

Authors Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.36.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Andreas Galanis
  • Department of Computer Science, University of Oxford, UK
Leslie Ann Goldberg
  • Department of Computer Science, University of Oxford, UK
Andrés Herrera-Poyatos
  • Department of Computer Science, University of Oxford, UK

Funding

  • Herrera-Poyatos, Andrés: This author is supported by an Oxford-DeepMind Graduate Scholarship and a EPSRC Doctoral Training Partnership.

Acknowledgements

We thank Ben Green, Joel Ouaknine and Oliver Riordan for useful discussions which helped us to lower bound Z_{Tutte}(G; q, γ). We also thank Miriam Backens for useful conversations and suggestions about this work.

Cite AsGet BibTex

Andreas Galanis, Leslie Ann Goldberg, and Andrés Herrera-Poyatos. The Complexity of Approximating the Complex-Valued Potts Model. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.36

Abstract

We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q ≥ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Mathematics of computing → Discrete mathematics
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • approximate counting
  • Potts model
  • Tutte polynomial
  • partition function
  • complex numbers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • A full version of the paper is available at https://arxiv.org/abs/2005.01076. The theorem numbers here match those in the full version. Proof sketches here refer to lemmas in the full version without restating them in detail.

References

  1. A. Barvinok. Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics. Springer International Publishing, 2017. Google Scholar
  2. A. Barvinok and G. Regts. Weighted counting of solutions to sparse systems of equations. Combinatorics, Probability and Computing, 28(5):696-719, 2019. Google Scholar
  3. I. Bena, M. Droz, and A. Lipowski. Statistical mechanics of equilibrium and nonequilibrium phase transitions: the Yang-Lee formalism. International Journal of Modern Physics B, 19(29):4269-4329, 2005. Google Scholar
  4. I. Bezáková, A. Galanis, L. A. Goldberg, and D. Štefankovič. Inapproximability of the independent set polynomial in the complex plane. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1234-1240, 2018. Google Scholar
  5. I. Bezáková, A. Galanis, L. A. Goldberg, and D. Štefankovič. The Complexity of Approximating the Matching Polynomial in the Complex Plane. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1-22:13, 2019. Google Scholar
  6. M. Bordewich, M. Freedman, L. Lovász, and D. Welsh. Approximate counting and quantum computation. Combinatorics, Probability and Computing, 14(5-6):737-754, 2005. Google Scholar
  7. R. J. Bradford and J. H. Davenport. Effective tests for cyclotomic polynomials. In Symbolic and algebraic computation, volume 358 of Lecture Notes in Comput. Sci., pages 244-251. Springer, Berlin, 1989. Google Scholar
  8. A. Brandstädt, V. B. Le, and J. P. Spinrad. Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. Google Scholar
  9. M. Brin and G. Stuck. Introduction to Dynamical Systems. Cambridge University Press, 2002. Google Scholar
  10. J. I. Brown, C. Hickman, A. D. Sokal, and D. G. Wagner. On the chromatic roots of generalized theta graphs. Journal of Combinatorial Theory. Series B, 83(2):272-297, 2001. Google Scholar
  11. L. A. Goldberg and H. Guo. The complexity of approximating complex-valued Ising and Tutte partition functions. Computational Complexity, 26(4):765-833, 2017. Google Scholar
  12. L. A. Goldberg and M. Jerrum. Inapproximability of the Tutte polynomial. Information and Computation, 206(7):908-929, 2008. Google Scholar
  13. L. A. Goldberg and M. Jerrum. Approximating the partition function of the ferromagnetic Potts model. J. ACM, 59(5):Art. 25, 31, 2012. Google Scholar
  14. L. A. Goldberg and M. Jerrum. Inapproximability of the Tutte polynomial of a planar graph. Computational Complexity, 21(4):605-642, 2012. Google Scholar
  15. L. A. Goldberg and M. Jerrum. The complexity of computing the sign of the Tutte polynomial. SIAM Journal on Computing, 43(6):1921-1952, 2014. Google Scholar
  16. H. Guo, C. Liao, P. Lu, and C. Zhang. Zeros of Holant problems: Locations and algorithms. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, pages 2262-2278, USA, 2019. Google Scholar
  17. H. Guo, J. Liu, and P. Lu. Zeros of ferromagnetic 2-spin systems. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, pages 181-192, USA, 2020. Google Scholar
  18. A. Harrow, S. Mehraban, and M. Soleimanifar. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems, 2019. URL: http://arxiv.org/abs/1910.09071.
  19. O. J. Heilmann and E. H. Lieb. Theory of monomer-dimer systems. Communications in Mathematical Physics, 25(3):190-232, 1972. Google Scholar
  20. F. Jaeger, D. L. Vertigan, and D. J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials. Mathematical Proceedings of the Cambridge Philosophical Society, 108(1):35-53, 1990. Google Scholar
  21. M. Jerrum and A. Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing, 22(5):1087-1116, 1993. Google Scholar
  22. R. Kannan, A. K. Lenstra, and L. Lovász. Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. Mathematics of Computation, 50(181):235-250, 1988. Google Scholar
  23. K.-I Ko. Complexity theory of real functions. Progress in Theoretical Computer Science. Birkhäuser Boston, Inc., Boston, MA, 1991. Google Scholar
  24. G. Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing, 11:183-219, 2015. Google Scholar
  25. E. H. Lieb and A. D. Sokal. A general Lee-Yang theorem for one-component and multicomponent ferromagnets. Communications in Mathematical Physics, 80(2):153-179, 1981. Google Scholar
  26. J. Liu, A. Sinclair, and P. Srivastava. A deterministic algorithm for counting colorings with 2-Delta colors. In IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019), pages 1380-1404, 2019. Google Scholar
  27. J. Liu, A. Sinclair, and P. Srivastava. Fisher zeros and correlation decay in the Ising model. Journal of Mathematical Physics, 60(10):103304, 2019. Google Scholar
  28. J. Liu, A. Sinclair, and P. Srivastava. The Ising partition function: Zeros and deterministic approximation. Journal of Statistical Physics, 174(2):287-315, 2019. Google Scholar
  29. V. Patel and G. Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM Journal on Computing, 46(6):1893-1919, 2017. Google Scholar
  30. H. Peters and G. Regts. Location of zeros for the partition function of the Ising model on bounded degree graphs. Journal of the London Mathematical Society, 2018. Google Scholar
  31. H. Peters and G. Regts. On a conjecture of sokal concerning roots of the independence polynomial. Michigan Mathematical Journal, 68(1):33-55, 2019. Google Scholar
  32. R. B. Potts. Some generalized order-disorder transformations. Proceedings of the Cambridge Philosophical Society, 48:106-109, 1952. Google Scholar
  33. J. S. Provan and M. O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12(4):777-788, 1983. Google Scholar
  34. A. D. Sokal. The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In Surveys in combinatorics 2005, volume 327 of London Math. Soc. Lecture Note Ser., pages 173-226. Cambridge Univ. Press, Cambridge, 2005. Google Scholar
  35. M. B. Thistlethwaite. A spanning tree expansion of the Jones polynomial. Topology, 26(3):297-309, 1987. Google Scholar
  36. D. Vertigan. The computational complexity of Tutte invariants for planar graphs. SIAM Journal on Computing, 35(3):690-712, 2005. Google Scholar
  37. D. J. A. Welsh. Complexity: knots, colourings and counting, volume 186 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1993. Google Scholar
  38. C.-N. Yang and T.-D. Lee. Statistical theory of equations of state and phase transitions. I. theory of condensation. Physical Review, 87(3):404, 1952. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact