Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Computational Complexity

The complexity of approximating the complex-valued Potts model

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

Published Feb 2, 2022• 5 citations
Publisher

Abstract

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.

DOI
10.1007/s00037-021-00218-x

Related papers

Polynomial Quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane Preliminary Version

Dorit Aharonov, Itai Arad, Elad Eban +1 more

In the first part of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes an additive approximation of the partition function of the Potts model for any weighted planer graph at any temperature, as well as approximations to many other combinatorial graph properties described by the (multivariate or not) Tutte polynomial. To achieve these algorithms, we generalize the Temperley Lieb algebra representations, used in [6], to apply for any graph (not necessarily coming from a braid). Moreover, our representations are non-unitary, as are all representations of the Temperley Lieb algebra not corresponding to Jones polynomial related parameters. It might seem at first sight that this makes it impossible to apply them by a quantum circuit. We show how to do this nevertheless. The approximation window size turns out to be inverse polynomial in |G| times the product of the norms of the operators we apply. Additive approximations are tricky; the range of the possible outcomes, might be smaller than the size of the approximation window, in which case the outcome is meaningless. Unfortunately, ruling out this possibility is difficult: If we want to argue that our a are meaningful, we have to provide an estimate of the scale of the problem, which is difficult here exactly because no efficient algorithm for the problem exists! In the second part of the paper we provide an indirect but very convincing proof that our approximation is meaningful for a large range of parameters, by showing that in those cases, the problems

•Jan 1, 2008•1 citation

Polynomial Quantum Algorithms for Additive approximations of the Potts model and other Points of the Tutte Plane

Dorit Aharonov, Itai Arad, Elad Eban +1 more

In the first 36 pages of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes as special cases the AJL algorithm for the Jones polynomial, the partition function of the Potts model for any weighted planer graph at any temperature, and many other combinatorial graph properties. In the second part of the paper we prove the quantum universality of many of the problems for which we provide an algorithm, thus providing a large set of new quantum-complete problems. Unfortunately, we do not know that this holds for the Potts model case; this is left as an important open problem. The main progress in this work is in our ability to handle non-unitary representations of the Temperley Lieb algebra, both when applying them in the algorithm, and, more importantly, in the proof of universality, when encoding quantum circuits using non-unitary operators. To this end we develop many new tools, that allow proving density and applying the Solovay Kitaev theorem in the case of non-unitary matrices. We hope that these tools will open up new possibilities of using non-unitary reps in other quantum computation contexts.

arXiv:quant-ph/0702008•Feb 1, 2007•59 citations

Analytic Properties of Potts and Ising Model Partition Functions and the Relationship between Analytic Properties and Phase Transitions in Equilibrium Statistical Mechanics

Siti Fatimah Zakaria

The Ising and $Q$-state Potts models are statistical mechanical models of spins interaction on crystal lattices. \nWe study the partition functions on a range of lattices, particularly two- and three-dimensional cases. The study aims to investigate cooperative phenomena $-$ how higher level structure is affected by the detailed activity of a very large number of lower level structures. \nWe investigate the analytic properties of the partition functions and their relationship to physical observables in equilibrium near phase transition. \nOur study is focussed on describing the partition function and the distribution of zeros of the partition function in the complex-temperature plane close to phase transitions. \nHere we first consider the solved case of the Ising model on square lattice as a benchmark for checking our method of computation and analysis. \nThe partition function is computed using a transfer matrix approach and the zeros are found numerically by Newton-Raphson method. \nWe extend the study of $Q$-state Potts models to a more general case called the $Z_Q$-symmetric model. \nWe evidence the existence of multiple phase transitions for this model in case $Q=5,6,$ and discuss the possible connection to different stages of disordered state. \nGiven sufficient and efficient coding and computing resources, we extend many previously studied cases to larger lattice sizes. \nOur analysis of zeros distribution close to phase transition point is based on a certain power law relation which leads to critical exponent of physical observable. \nWe evidence for example, that our method can be used to give numerical estimates of the specific heat critical exponent $\\alpha$.

•Nov 1, 2016•3 citations

Density of states, Potts zeros, and Fisher zeros of theQ-state Potts model for continuousQ

Seung‐Yeon Kim, Richard J. Creswick

The Q-state Potts model can be extended to noninteger and even complex Q by expressing the partition function in the Fortuin-Kasteleyn (F-K) representation. In the F-K representation the partition function Z(Q,a) is a polynomial in Q and v=a-1 (a=e(betaJ)) and the coefficients of this polynomial, Phi(b,c), are the number of graphs on the lattice consisting of b bonds and c connected clusters. We introduce the random-cluster transfer matrix to compute Phi(b,c) exactly on finite square lattices with several types of boundary conditions. Given the F-K representation of the partition function we begin by studying the critical Potts model Z(CP)=Z(Q,a(c)(Q)), where a(c)(Q)=1+square root[Q]. We find a set of zeros in the complex w=square root[Q] plane that map to (or close to) the Beraha numbers for real positive Q. We also identify Q(c)(L), the value of Q for a lattice of width L above which the locus of zeros in the complex p=v/square root[Q] plane lies on the unit circle. By finite-size scaling we find that 1/Q(c)(L)-->0 as L-->infinity. We then study zeros of the antiferromagnetic (AF) Potts model in the complex Q plane and determine Q(c)(a), the largest value of Q for a fixed value of a below which there is AF order. We find excellent agreement with Baxter's conjecture Q(AF)(c)(a)=(1-a)(a+3). We also investigate the locus of zeros of the ferromagnetic Potts model in the complex Q plane and confirm that Q(FM)(c)(a)=(a-1)(2). We show that the edge singularity in the complex Q plane approaches Q(c) as Q(c)(L) approximately Q(c)+AL(-y(q)), and determine the scaling exponent y(q) for several values of Q. Finally, by finite-size scaling of the Fisher zeros near the antiferromagnetic critical point we determine the thermal exponent y(t) as a function of Q in the range 2</=Q</=3. Using data for lattices of size 3</=L</=8 we find that y(t) is a smooth function of Q and is well fitted by y(t)=(1+Au+Bu2)/(C+Du) where u=-(2/pi)cos(-1)(squareroot[Q]/2). For Q=3 we find y(t) approximately 0.6; however if we include lattices up to L=12 we find y(t) approximately 0.50(8) in rough agreement with a recent result of Ferreira and Sokal [J. Stat. Phys. 96, 461 (1999)].

arXiv:cond-mat/0102090•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•May 17, 2001•26 citations

Commuting quantum circuits and complexity of Ising partition functions

Keisuke Fujii, Tomoyuki Morimae

Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy collapses to the third level, which is highly implausible. However, the origin of the classical intractability is still less understood. Here we establish a relationship between IQP and computational complexity of calculating the imaginary-valued partition functions of Ising models. We apply the established relationship in two opposite directions. One direction is to find subclasses of IQP that are classically efficiently simulatable by using exact solvability of certain types of Ising models. Another direction is applying quantum computational complexity of IQP to investigate (im)possibility of efficient classical approximations of Ising partition functions with imaginary coupling constants. Specifically, we show that a multiplicative approximation of Ising partition functions is #P-hard for almost all imaginary coupling constants even on planar lattices of a bounded degree.

arXiv:1311.2128•New Journal of Physics•Feb 10, 2017•48 citations

Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs

Ryan L. Mann, Michael J. Bremner

We study the problem of approximating the Ising model partition function with complex parameters on bounded degree graphs. We establish a deterministic polynomial-time approximation scheme for the partition function when the interactions and external fields are absolutely bounded close to zero. Furthermore, we prove that for this class of Ising models the partition function does not vanish. Our algorithm is based on an approach due to Barvinok for approximating evaluations of a polynomial based on the location of the complex zeros and a technique due to Patel and Regts for efficiently computing the leading coefficients of graph polynomials on bounded degree graphs. Finally, we show how our algorithm can be extended to approximate certain output probability amplitudes of quantum circuits.

arXiv:1806.11282•Quantum•Jul 11, 2019•8 citations
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.
In the first part of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes an additive approximation of the partition function of the Potts model for any weighted planer graph at any temperature, as well as approximations to many other combinatorial graph properties described by the (multivariate or not) Tutte polynomial. To achieve these algorithms, we generalize the Temperley Lieb algebra representations, used in [6], to apply for any graph (not necessarily coming from a braid). Moreover, our representations are non-unitary, as are all representations of the Temperley Lieb algebra not corresponding to Jones polynomial related parameters. It might seem at first sight that this makes it impossible to apply them by a quantum circuit. We show how to do this nevertheless. The approximation window size turns out to be inverse polynomial in |G| times the product of the norms of the operators we apply. Additive approximations are tricky; the range of the possible outcomes, might be smaller than the size of the approximation window, in which case the outcome is meaningless. Unfortunately, ruling out this possibility is difficult: If we want to argue that our a are meaningful, we have to provide an estimate of the scale of the problem, which is difficult here exactly because no efficient algorithm for the problem exists! In the second part of the paper we provide an indirect but very convincing proof that our approximation is meaningful for a large range of parameters, by showing that in those cases, the problems
In the first 36 pages of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes as special cases the AJL algorithm for the Jones polynomial, the partition function of the Potts model for any weighted planer graph at any temperature, and many other combinatorial graph properties. In the second part of the paper we prove the quantum universality of many of the problems for which we provide an algorithm, thus providing a large set of new quantum-complete problems. Unfortunately, we do not know that this holds for the Potts model case; this is left as an important open problem. The main progress in this work is in our ability to handle non-unitary representations of the Temperley Lieb algebra, both when applying them in the algorithm, and, more importantly, in the proof of universality, when encoding quantum circuits using non-unitary operators. To this end we develop many new tools, that allow proving density and applying the Solovay Kitaev theorem in the case of non-unitary matrices. We hope that these tools will open up new possibilities of using non-unitary reps in other quantum computation contexts.
The Ising and QQQ-state Potts models are statistical mechanical models of spins interaction on crystal lattices. \nWe study the partition functions on a range of lattices, particularly two- and three-dimensional cases. The study aims to investigate cooperative phenomena −-− how higher level structure is affected by the detailed activity of a very large number of lower level structures. \nWe investigate the analytic properties of the partition functions and their relationship to physical observables in equilibrium near phase transition. \nOur study is focussed on describing the partition function and the distribution of zeros of the partition function in the complex-temperature plane close to phase transitions. \nHere we first consider the solved case of the Ising model on square lattice as a benchmark for checking our method of computation and analysis. \nThe partition function is computed using a transfer matrix approach and the zeros are found numerically by Newton-Raphson method. \nWe extend the study of QQQ-state Potts models to a more general case called the ZQZ_QZQ​-symmetric model. \nWe evidence the existence of multiple phase transitions for this model in case Q=5,6,Q=5,6,Q=5,6, and discuss the possible connection to different stages of disordered state. \nGiven sufficient and efficient coding and computing resources, we extend many previously studied cases to larger lattice sizes. \nOur analysis of zeros distribution close to phase transition point is based on a certain power law relation which leads to critical exponent of physical observable. \nWe evidence for example, that our method can be used to give numerical estimates of the specific heat critical exponent alpha\\alphaalpha.
The Q-state Potts model can be extended to noninteger and even complex Q by expressing the partition function in the Fortuin-Kasteleyn (F-K) representation. In the F-K representation the partition function Z(Q,a) is a polynomial in Q and v=a-1 (a=e(betaJ)) and the coefficients of this polynomial, Phi(b,c), are the number of graphs on the lattice consisting of b bonds and c connected clusters. We introduce the random-cluster transfer matrix to compute Phi(b,c) exactly on finite square lattices with several types of boundary conditions. Given the F-K representation of the partition function we begin by studying the critical Potts model Z(CP)=Z(Q,a(c)(Q)), where a(c)(Q)=1+square root[Q]. We find a set of zeros in the complex w=square root[Q] plane that map to (or close to) the Beraha numbers for real positive Q. We also identify Q(c)(L), the value of Q for a lattice of width L above which the locus of zeros in the complex p=v/square root[Q] plane lies on the unit circle. By finite-size scaling we find that 1/Q(c)(L)-->0 as L-->infinity. We then study zeros of the antiferromagnetic (AF) Potts model in the complex Q plane and determine Q(c)(a), the largest value of Q for a fixed value of a below which there is AF order. We find excellent agreement with Baxter's conjecture Q(AF)(c)(a)=(1-a)(a+3). We also investigate the locus of zeros of the ferromagnetic Potts model in the complex Q plane and confirm that Q(FM)(c)(a)=(a-1)(2). We show that the edge singularity in the complex Q plane approaches Q(c) as Q(c)(L) approximately Q(c)+AL(-y(q)), and determine the scaling exponent y(q) for several values of Q. Finally, by finite-size scaling of the Fisher zeros near the antiferromagnetic critical point we determine the thermal exponent y(t) as a function of Q in the range 2</=Q</=3. Using data for lattices of size 3</=L</=8 we find that y(t) is a smooth function of Q and is well fitted by y(t)=(1+Au+Bu2)/(C+Du) where u=-(2/pi)cos(-1)(squareroot[Q]/2). For Q=3 we find y(t) approximately 0.6; however if we include lattices up to L=12 we find y(t) approximately 0.50(8) in rough agreement with a recent result of Ferreira and Sokal [J. Stat. Phys. 96, 461 (1999)].
Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy collapses to the third level, which is highly implausible. However, the origin of the classical intractability is still less understood. Here we establish a relationship between IQP and computational complexity of calculating the imaginary-valued partition functions of Ising models. We apply the established relationship in two opposite directions. One direction is to find subclasses of IQP that are classically efficiently simulatable by using exact solvability of certain types of Ising models. Another direction is applying quantum computational complexity of IQP to investigate (im)possibility of efficient classical approximations of Ising partition functions with imaginary coupling constants. Specifically, we show that a multiplicative approximation of Ising partition functions is #P-hard for almost all imaginary coupling constants even on planar lattices of a bounded degree.
We study the problem of approximating the Ising model partition function with complex parameters on bounded degree graphs. We establish a deterministic polynomial-time approximation scheme for the partition function when the interactions and external fields are absolutely bounded close to zero. Furthermore, we prove that for this class of Ising models the partition function does not vanish. Our algorithm is based on an approach due to Barvinok for approximating evaluations of a polynomial based on the location of the complex zeros and a technique due to Patel and Regts for efficiently computing the leading coefficients of graph polynomials on bounded degree graphs. Finally, we show how our algorithm can be extended to approximate certain output probability amplitudes of quantum circuits.