Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComplexity of Ising Polynomials
230
0
0.0
(
0
)
Authors
Tomer Kotek
Ask ChatGPT about the research
No Arabic abstract
This paper deals with the partition function of the Ising model from statistical mechanics, which is used to study phase transitions in physical systems. A special case of interest is that of the Ising model with constant energies and external field. One may consider such an Ising system as a simple graph together with vertex and edge weights. When these weights are considered indeterminates, the partition function for the constant case is a trivariate polynomial Z(G;x,y,z). This polynomial was studied with respect to its approximability by L. A. Goldberg, M. Jerrum and M. Paterson in 2003. Z(G;x,y,z) generalizes a bivariate polynomial Z(G;t,y), which was studied by D. Andr{e}n and K. Markstr{o}m in 2009. We consider the complexity of Z(G;t,y) and Z(G;x,y,z) in comparison to that of the Tutte polynomial, which is well-known to be closely related to the Potts model in the absence of an external field. We show that Z(G;x,y,z) is #P-hard to evaluate at all points in $mathbb{Q}^3$, except those in an exception set of low dimension, even when restricted to simple graphs which are bipartite and planar. A counting version of the Exponential Time Hypothesis, #ETH, was introduced by H. Dell, T. Husfeldt and M. Wahl{e}n in 2010 in order to study the complexity of the Tutte polynomial. In analogy to their results, we give a dichotomy theorem stating that evaluations of Z(G;t,y) either take exponential time in the number of vertices of $G$ to compute, or can be done in polynomial time. Finally, we give an algorithm for computing Z(G;x,y,z) in polynomial time on graphs of bounded clique-width, which is not known in the case of the Tutte polynomial.
rate research
Read More
We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f circ textsf{XOR}$, called an $textsf{XOR}$ function. Using this duality, we develop polynomial based techniques for understanding the bounded error ($textsf{BPP}$) and the weakly-unbounded error ($textsf{PP}$) communication complexities of $textsf{XOR}$ functions. We show the following. A weak form of an interesting conjecture of Zhang and Shi (Quantum Information and Computation, 2009) (The full conjecture has just been reported to be independently settled by Hatami and Qian (Arxiv, 2017). However, their techniques are quite different and are not known to yield many of the results we obtain here). Zhang and Shi assert that for symmetric functions $f : {0, 1}^n rightarrow {-1, 1}$, the weakly unbounded-error complexity of $f circ textsf{XOR}$ is essentially characterized by the number of points $i$ in the set ${0,1, dots,n-2}$ for which $D_f(i) eq D_f(i+2)$, where $D_f$ is the predicate corresponding to $f$. The number of such points is called the odd-even degree of $f$. We show that the $textsf{PP}$ complexity of $f circ textsf{XOR}$ is $Omega(k/ log(n/k))$. We resolve a conjecture of a different Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree. We obtain a new proof of the exponential separation between $textsf{PP}^{cc}$ and $textsf{UPP}^{cc}$ via an $textsf{XOR}$ function. We provide a characterization of the approximate spectral norm of symmetric functions, affirming a conjecture of Ada et al. (APPROX-RANDOM, 2012) which has several consequences. Additionally, we prove strong $textsf{UPP}$ lower bounds for $f circ textsf{XOR}$, when $f$ is symmetric and periodic with period $O(n^{1/2-epsilon})$, for any constant $epsilon > 0$.
We discuss the 4pt function of the critical 3d Ising model, extracted from recent conformal bootstrap results. We focus on the non-gaussianity Q - the ratio of the 4pt function to its gaussian part given by three Wick contractions. This ratio reveals significant non-gaussianity of the critical fluctuations. The bootstrap results are consistent with a rigorous inequality due to Lebowitz and Aizenman, which limits Q to lie between 1/3 and 1.
We describe all linear operators on spaces of multivariate polynomials preserving the property of being non-vanishing in open circular domains. This completes the multivariate generalization of the classification program initiated by Polya-Schur for univariate real polynomials and provides a natural framework for dealing in a uniform way with Lee-Yang type problems in statistical mechanics, combinatorics, and geometric function theory. This is an announcement with some of the main results in arXiv:0809.0401 and arXiv:0809.3087.
The ZX-calculus is a graphical language which allows for reasoning about suitably represented tensor networks - namely ZX-diagrams - in terms of rewrite rules. Here, we focus on problems which amount to exactly computing a scalar encoded as a closed tensor network. In general, such problems are #P-hard. However, there are families of such problems which are known to be in P when the dimension is below a certain value. By expressing problem instances from these families as ZX-diagrams, we see that the easy instances belong to the stabilizer fragment of the ZX-calculus. Building on previous work on efficient simplification of qubit stabilizer diagrams, we present simplifying rewrites for the case of qutrits, which are of independent interest in the field of quantum circuit optimisation. Finally, we look at the specific examples of evaluating the Jones polynomial and of counting graph-colourings. Our exposition further champions the ZX-calculus as a suitable and unifying language for studying the complexity of a broad range of classical and quantum problems.
We consider ferromagnetic Ising models on graphs that converge locally to trees. Examples include random regular graphs with bounded degree and uniformly random graphs with bounded average degree. We prove that the cavity prediction for the limiting free energy per spin is correct for any positive temperature and external field. Further, local marginals can be approximated by iterating a set of mean field (cavity) equations. Both results are achieved by proving the local convergence of the Boltzmann distribution on the original graph to the Boltzmann distribution on the appropriate infinite random tree.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
