2026-07-25T12:39:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16449 2024-03-06T10:57:31Z ddc:004 open_access

Polynomial-Time Approximation of Zero-Free Partition Functions Yao, Penghui Yin, Yitong Zhang, Xinyuan partition function zero-freeness local Hamiltonian 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Penghui Yao and Yitong Yin and Xinyuan Zhang 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.108 urn:nbn:de:0030-drops-164494 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.108 eng https://creativecommons.org/licenses/by/4.0/legalcode