Document Open Access Logo

Polynomial-Time Approximation of Zero-Free Partition Functions

Authors Penghui Yao, Yitong Yin, Xinyuan Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.108.pdf
  • Filesize: 0.72 MB
  • 20 pages

Document Identifiers

Author Details

Penghui Yao
  • State Key Laboratory for Novel Software Technology, Nanjing University, China
Yitong Yin
  • State Key Laboratory for Novel Software Technology, Nanjing University, China
Xinyuan Zhang
  • State Key Laboratory for Novel Software Technology, Nanjing University, China

Funding

This research was supported by National Natural Science Foundation of China (Grant No. 61972191) and the Program for Innovative Talents and Entrepreneur in Jiangsu and Anhui Initiative in Quantum Information Technologies Grant No. AHY150100.

Cite AsGet BibTex

Penghui Yao, Yitong Yin, and Xinyuan Zhang. Polynomial-Time Approximation of Zero-Free Partition Functions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 108:1-108:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.108

Abstract

Zero-free based algorithms are a major technique for deterministic approximate counting. In Barvinok’s original framework [Barvinok, 2017], by calculating truncated Taylor expansions, a quasi-polynomial time algorithm was given for estimating zero-free partition functions. Patel and Regts [Patel and Regts, 2017] later gave a refinement of Barvinok’s framework, which gave a polynomial-time algorithm for a class of zero-free graph polynomials that can be expressed as counting induced subgraphs in bounded-degree graphs. In this paper, we give a polynomial-time algorithm for estimating classical and quantum partition functions specified by local Hamiltonians with bounded maximum degree, assuming a zero-free property for the temperature. Consequently, when the inverse temperature is close enough to zero by a constant gap, we have a polynomial-time approximation algorithm for all such partition functions. Our result is based on a new abstract framework that extends and generalizes the approach of Patel and Regts.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • partition function
  • zero-freeness
  • local Hamiltonian

Metrics

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

Related Versions

References

  1. Alexander Barvinok. Computing the partition function for cliques in a graph. Theory of Computing, 11(13):339-355, 2015. Google Scholar
  2. Alexander Barvinok. Computing the permanent of (some) complex matrices. Foundations of Computational Mathematics, 16(2):329-342, 2016. Google Scholar
  3. Alexander Barvinok. Approximating permanents and hafnians. Discrete Analysis, page 1244, 2017. Google Scholar
  4. Alexander Barvinok. Combinatorics and Complexity of Partition Functions. Springer Publishing Company, Incorporated, 1st edition, 2017. Google Scholar
  5. Alexander Barvinok. Computing the partition function of a polynomial on the boolean cube. In A Journey Through Discrete Mathematics, pages 135-164. Springer, 2017. Google Scholar
  6. Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič. Inapproximability of the independent set polynomial in the complex plane. SIAM J. Comput., 49(5), 2020. Google Scholar
  7. Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič. The complexity of approximating the matching polynomial in the complex plane. ACM Trans. Comput. Theory, 13(2):13:1-13:37, 2021. Google Scholar
  8. Christian Borgs, Jennifer Chayes, Jeff Kahn, and László Lovász. Left and right convergence of graphs with bounded degree. Random Struct. Algorithms, 42(1):1-28, January 2013. Google Scholar
  9. Pjotr Buys, Andreas Galanis, Viresh Patel, and Guus Regts. Lee-yang zeros and the complexity of the ferromagnetic ising model on bounded-degree graphs. In SODA, pages 1508-1519. SIAM, 2021. Google Scholar
  10. Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion. In STOC, pages 1537-1550, 2021. Google Scholar
  11. Zongchen Chen, Kuikui Liu, and Eric Vigoda. Spectral independence via stability and applications to holant-type problems. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.03366.
  12. Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts. Statistical physics approaches to unique games. In 35th Computational Complexity Conference (CCC), volume 169 of LIPIcs, pages 13:1-13:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  13. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. J. ACM, 62(6):Art. 50, 60, 2015. Google Scholar
  14. Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin. Quantum hamiltonian complexity. Found. Trends Theor. Comput. Sci., 10(3):159-282, 2015. Google Scholar
  15. Leslie Ann Goldberg, Mark Jerrum, and Mike Paterson. The computational complexity of two-state spin systems. Random Structures Algorithms, 23(2):133-154, 2003. Google Scholar
  16. Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang. Zeros of holant problems: locations and algorithms. ACM Transactions on Algorithms (TALG), 17(1):1-25, 2020. Google Scholar
  17. Heng Guo, Jingcheng Liu, and Pinyan Lu. Zeros of ferromagnetic 2-spin systems. In SODA, pages 181-192. SIAM, 2020. Google Scholar
  18. Aram W Harrow, Saeed Mehraban, and Mehdi Soleimanifar. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. In STOC, pages 378-386, 2020. Google Scholar
  19. Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic pirogov-sinai theory. Probability Theory and Related Fields, 176(3):851-895, 2020. Google Scholar
  20. Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing, 22(5):1087-1116, 1993. Google Scholar
  21. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM (JACM), 51(4):671-697, 2004. Google Scholar
  22. Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. Classical and quantum computation. American Mathematical Soc., 2002. Google Scholar
  23. Tomotaka Kuwahara, Kohtaro Kato, and Fernando GSL Brandão. Clustering of conditional mutual information for quantum gibbs states above a threshold temperature. Physical review letters, 124(22):220601, 2020. Google Scholar
  24. Tsung-Dao Lee and Chen-Ning Yang. Statistical theory of equations of state and phase transitions. ii. lattice gas and ising model. Physical Review, 87(3):410, 1952. Google Scholar
  25. Liang Li, Pinyan Lu, and Yitong Yin. Correlation decay up to uniqueness in spin systems. In SODA, pages 67-84. SIAM, 2013. Google Scholar
  26. Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. Correlation decay and partition function zeros: Algorithms and phase transitions. arXiv preprint, 2019. URL: http://arxiv.org/abs/1906.01228.
  27. Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. The ising partition function: Zeros and deterministic approximation. Journal of Statistical Physics, 174:287-315, 2019. Google Scholar
  28. Ryan L Mann and Tyler Helmuth. Efficient algorithms for approximating quantum partition functions. Journal of Mathematical Physics, 62(2):022201, 2021. Google Scholar
  29. Viresh Patel and Guus Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM Journal on Computing, 46(6):1893-1919, January 2017. Google Scholar
  30. Han Peters and Guus Regts. On a conjecture of sokal concerning roots of the independence polynomial. Michigan Math. J., 68(1):33-35, 2019. Google Scholar
  31. Guus Regts. Zero-free regions of partition functions with applications to algorithms and graph limits. Combinatorica, 38(4):987-1015, 2018. Google Scholar
  32. Jesús Salas and Alan D Sokal. Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J. Stat. Phys., 86(3):551-579, 1997. Google Scholar
  33. Shuai Shao and Yuxin Sun. Contraction: A unified perspective of correlation decay and zero-freeness of 2-spin systems. In ICALP, volume 168 of LIPIcs, pages 96:1-96:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  34. Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. Journal of Statistical Physics, 155(4):666-686, 2014. (conference version in SODA'12). Google Scholar
  35. Allan Sly. Computational transition at the uniqueness threshold. In FOCS, pages 287-296, 2010. Google Scholar
  36. Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In FOCS, pages 361-369, 2012. Google Scholar
  37. Daniel Štefankovič, Santosh S. Vempala, and Eric Vigoda. Adaptive simulated annealing: A near-optimal connection between sampling and counting. J. ACM, 56(3):18:1-18:36, 2009. Google Scholar
  38. E.M. Stein and R. Shakarchi. Complex Analysis. Princeton lectures in analysis. Princeton University Press, 2010. Google Scholar
  39. Dror Weitz. Counting independent sets up to the tree threshold. In STOC, pages 140-149, 2006. 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