We study the approximation complexity of the partition function of the eight-vertex model on general 4-regular graphs. For the first time, we relate the approximability of the eight-vertex model to the complexity of approximately counting perfect matchings, a central open problem in this field. Our results extend those in [Jin-Yi Cai et al., 2018]. In a region of the parameter space where no previous approximation complexity was known, we show that approximating the partition function is at least as hard as approximately counting perfect matchings via approximation-preserving reductions. In another region of the parameter space which is larger than the region that is previously known to admit Fully Polynomial Randomized Approximation Scheme (FPRAS), we show that computing the partition function can be reduced to counting perfect matchings (which is valid for both exact and approximate counting). Moreover, we give a complete characterization of nonnegatively weighted (not necessarily planar) 4-ary matchgates, which has been open for several years. The key ingredient of our proof is a geometric lemma. We also identify a region of the parameter space where approximating the partition function on planar 4-regular graphs is feasible but on general 4-regular graphs is equivalent to approximately counting perfect matchings. To our best knowledge, these are the first problems that exhibit this dichotomic behavior between the planar and the nonplanar settings in approximate counting.We study the approximation complexity of the partition function of the eight-vertex model on general 4-regular graphs. For the first time, we relate the approximability of the eight-vertex model to the complexity of approximately counting perfect matchings, a central open problem in this field. Our results extend those in [Jin-Yi Cai et al., 2018]. In a region of the parameter space where no previous approximation complexity was known, we show that approximating the partition function is at least as hard as approximately counting perfect matchings via approximation-preserving reductions. In another region of the parameter space which is larger than the region that is previously known to admit Fully Polynomial Randomized Approximation Scheme (FPRAS), we show that computing the partition function can be reduced to counting perfect matchings (which is valid for both exact and approximate counting). Moreover, we give a complete characterization of nonnegatively weighted (not necessarily planar) 4-ary matchgates, which has been open for several years. The key ingredient of our proof is a geometric lemma. We also identify a region of the parameter space where approximating the partition function on planar 4-regular graphs is feasible but on general 4-regular graphs is equivalent to approximately counting perfect matchings. To our best knowledge, these are the first problems that exhibit this dichotomic behavior between the planar and the nonplanar settings in approximate counting.

Jan 1, 20201 citation

A Complexity Trichotomy for the Six-Vertex Model.

Jin‐Yi Cai, Zhiguo Fu, Shuai Shao

We prove a complexity classification theorem that divides the six-vertex model on graphs into exactly three types. For every setting of the parameters of the model, the computation of the partition function is precisely: Either (1) solvable in polynomial time for every graph, or (2) #P-hard for general graphs but solvable in polynomial time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. In addition to matchgates and matchgates-transformable signatures, we discover previously unknown families of planar-tractable partition functions by a non-local connection to #CSP, defined in terms of a loop space. For the proof of #P-hardness, we introduce the use of M\obius transformations as a powerful new tool to prove that certain complexity reductions succeed in polynomial time.We prove a complexity classification theorem that divides the six-vertex model on graphs into exactly three types. For every setting of the parameters of the model, the computation of the partition function is precisely: Either (1) solvable in polynomial time for every graph, or (2) #P-hard for general graphs but solvable in polynomial time for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. In addition to matchgates and matchgates-transformable signatures, we discover previously unknown families of planar-tractable partition functions by a non-local connection to #CSP, defined in terms of a loop space. For the proof of #P-hardness, we introduce the use of M\obius transformations as a powerful new tool to prove that certain complexity reductions succeed in polynomial time.

Apr 5, 20172 citations

The complexity of approximating the complex-valued Potts model

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

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 $\geq$ ≥ 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.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 $$\geq$$ ≥ 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.

Computational ComplexityFeb 2, 20225 citations

Near-Optimal Parallel Approximate Counting via Sampling

David G. Harris, Vladimir Kolmogorov, Hongyang Liu +2 more

The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is achieved via simulated annealing, where the counting problem is formulated in terms of estimating the ratio $Q={Z(β_{\max})}/{Z(β_{\min})}$ between partition functions $Z(β)=\sum_{x\in Ω} \exp(βH(x))$ of Gibbs distributions $μ_β$ over $Ω$ with Hamiltonian $H$ , given access to a sampling oracle that produces samples from $μ_β$ for $β\in [β_{\min}, β_{\max}]$ . The best bound achieved by known annealing algorithms with relative error $\varepsilon$ is $O(q \log h / \varepsilon^2)$ , where $q, h$ are parameters which respectively bound $\ln Q$ and $H$ . However, all known algorithms attaining this near-optimal complexity are inherently sequential, or *adaptive*: the queried parameters $β$ depend on previous samples. We develop a simple non-adaptive algorithm for approximate counting using $O(q \log^2 h / \varepsilon^2)$ samples, as well as an algorithm that achieves $O(q \log h / \varepsilon^2)$ samples with just two rounds of adaptivity, matching the best sample complexity of sequential algorithms. These algorithms naturally give rise to work-efficient parallel (RNC) counting algorithms. We discuss applications to RNC counting algorithms for several classic models, including the anti-ferromagnetic 2-spin, monomer-dimer and ferromagnetic Ising models.The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is achieved via simulated annealing, where the counting problem is formulated in terms of estimating the ratio $Q={Z(β_{\max})}/{Z(β_{\min})}$ between partition functions $Z(β)=\sum_{x\in Ω} \exp(βH(x))$ of Gibbs distributions $μ_β$ over $Ω$ with Hamiltonian $H$, given access to a sampling oracle that produces samples from $μ_β$ for $β\in [β_{\min}, β_{\max}]$. The best bound achieved by known annealing algorithms with relative error $\varepsilon$ is $O(q \log h / \varepsilon^2)$, where $q, h$ are parameters which respectively bound $\ln Q$ and $H$. However, all known algorithms attaining this near-optimal complexity are inherently sequential, or *adaptive*: the queried parameters $β$ depend on previous samples. We develop a simple non-adaptive algorithm for approximate counting using $O(q \log^2 h / \varepsilon^2)$ samples, as well as an algorithm that achieves $O(q \log h / \varepsilon^2)$ samples with just two rounds of adaptivity, matching the best sample complexity of sequential algorithms. These algorithms naturally give rise to work-efficient parallel (RNC) counting algorithms. We discuss applications to RNC counting algorithms for several classic models, including the anti-ferromagnetic 2-spin, monomer-dimer and ferromagnetic Ising models.

arXiv:2604.01263Apr 1, 20260 citations

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

Annual Symposium on Foundations of Computer ScienceOct 1, 201050 citations

Quantum algorithms for classical lattice models

Gemma De las Cuevas, Wolfgang Dür, M Van den Nest +1 more

We give efficient quantum algorithms to estimate the partition function of (i) the six-vertex model on a two-dimensional (2D) square lattice, (ii) the Ising model with magnetic fields on a planar graph, (iii) the Potts model on a quasi-2D square lattice and (iv) the Z 2 lattice gauge theory on a 3D square lattice.Moreover, we prove that these problems are BQP-complete, that is, that estimating these partition functions is as hard as simulating arbitrary quantum computation.The results are proven for a complex parameter regime of the models.The proofs are based on a mapping relating partition functions to quantum circuits introduced by Van den Nest et al (2009 Phys.Rev. A 80 052334) and extended here.We give efficient quantum algorithms to estimate the partition function of (i) the six-vertex model on a two-dimensional (2D) square lattice, (ii) the Ising model with magnetic fields on a planar graph, (iii) the Potts model on a quasi-2D square lattice and (iv) the Z 2 lattice gauge theory on a 3D square lattice.Moreover, we prove that these problems are BQP-complete, that is, that estimating these partition functions is as hard as simulating arbitrary quantum computation.The results are proven for a complex parameter regime of the models.The proofs are based on a mapping relating partition functions to quantum circuits introduced by Van den Nest et al (2009 Phys.Rev. A 80 052334) and extended here.

arXiv:1104.2517New Journal of PhysicsSep 9, 201140 citations

\geq

≥ 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.

Q={Z(β_{\max})}/{Z(β_{\min})}

between partition functions

Z(β)=\sum_{x\in Ω} \exp(βH(x))

of Gibbs distributions

μ_β

over

Ω

with Hamiltonian

H

, given access to a sampling oracle that produces samples from

μ_β

for

β\in [β_{\min}, β_{\max}]

. The best bound achieved by known annealing algorithms with relative error

\varepsilon

O(q \log h / \varepsilon^2)

, where

q, h

are parameters which respectively bound

\ln Q

and

H

. However, all known algorithms attaining this near-optimal complexity are inherently sequential, or *adaptive*: the queried parameters

β

depend on previous samples. We develop a simple non-adaptive algorithm for approximate counting using

O(q \log^2 h / \varepsilon^2)

samples, as well as an algorithm that achieves

O(q \log h / \varepsilon^2)

samples with just two rounds of adaptivity, matching the best sample complexity of sequential algorithms. These algorithms naturally give rise to work-efficient parallel (RNC) counting algorithms. We discuss applications to RNC counting algorithms for several classic models, including the anti-ferromagnetic 2-spin, monomer-dimer and ferromagnetic Ising models.