Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStrong Spatial Mixing and Approximating Partition Functions of Two-State Spin Systems without Hard Constrains
90
0
0.0
(
0
)
Added by
Jinshan Zhang
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Authors
Jinshan Zhang
Ask ChatGPT about the research
No Arabic abstract
We prove Gibbs distribution of two-state spin systems(also known as binary Markov random fields) without hard constrains on a tree exhibits strong spatial mixing(also known as strong correlation decay), under the assumption that, for arbitrary `external field, the absolute value of `inverse temperature is small, or the `external field is uniformly large or small. The first condition on `inverse temperature is tight if the distribution is restricted to ferromagnetic or antiferromagnetic Ising models. Thanks to Weitzs self-avoiding tree, we extends the result for sparse on average graphs, which generalizes part of the recent work of Mossel and Slycite{MS08}, who proved the strong spatial mixing property for ferromagnetic Ising model. Our proof yields a different approach, carefully exploiting the monotonicity of local recursion. To our best knowledge, the second condition of `external field for strong spatial mixing in this paper is first considered and stated in term of `maximum average degree and `interaction energy. As an application, we present an FPTAS for partition functions of two-state spin models without hard constrains under the above assumptions in a general family of graphs including interesting bounded degree graphs.
rate research
Read More
We achieve a quantum speed-up of fully polynomial randomized approximation schemes (FPRAS) for estimating partition functions that combine simulated annealing with the Monte-Carlo Markov Chain method and use non-adaptive cooling schedules. The improvement in time complexity is twofold: a quadratic reduction with respect to the spectral gap of the underlying Markov chains and a quadratic reduction with respect to the parameter characterizing the desired accuracy of the estimate output by the FPRAS. Both reductions are intimately related and cannot be achieved separately. First, we use Grovers fixed point search, quantum walks and phase estimation to efficiently prepare approximate coherent encodings of stationary distributions of the Markov chains. The speed-up we obtain in this way is due to the quadratic relation between the spectral and phase gaps of classical and quantum walks. Second, we generalize the method of quantum counting, showing how to estimate expected values of quantum observables. Using this method instead of classical sampling, we obtain the speed-up with respect to accuracy.
We establish a polynomial-time approximation algorithm for partition functions of quantum spin models at high temperature. Our algorithm is based on the quantum cluster expansion of Netov{c}ny and Redig and the cluster expansion approach to designing algorithms due to Helmuth, Perkins, and Regts. Similar results have previously been obtained by related methods, and our main contribution is a simple and slightly sharper analysis for the case of pairwise interactions on bounded-degree graphs.
We observe that the partition function of the set of all free massless higher spins s=0,1,2,3,... in flat space is equal to one: the ghost determinants cancel against the physical ones or, equivalently, the (regularized) total number of degrees of freedom vanishes. This reflects large underlying gauge symmetry and suggests analogy with supersymmetric or topological theory. The Z=1 property extends also to the AdS background, i.e. the 1-loop vacuum partition function of Vasiliev theory is equal to 1 (assuming a particular regularization of the sum over spins); this was noticed earlier as a consistency requirement for the vectorial AdS/CFT duality. We find that Z=1 is also true in the conformal higher spin theory (with higher-derivative d^{2s} kinetic terms) expanded near flat or conformally flat S^4 background. We also consider the partition function of free conformal theory of symmetric traceless rank s tensor field which has 2-derivative kinetic term but only scalar gauge invariance in flat 4d space. This non-unitary theory has a Weyl-invariant action in curved background and corresponds to partially massless field in AdS_5. We discuss in detail the special case of s=2 (or conformal graviton), compute the corresponding conformal anomaly coefficients and compare them with previously found expressions for generic representations of conformal group in 4 dimensions.
We introduce a new mathematical object, the fermionant ${mathrm{Ferm}}_N(G)$, of type $N$ of an $n times n$ matrix $G$. It represents certain $n$-point functions involving $N$ species of free fermions. When N=1, the fermionant reduces to the determinant. The partition function of the repulsive Hubbard model, of geometrically frustrated quantum antiferromagnets, and of Kondo lattice models can be expressed as fermionants of type N=2, which naturally incorporates infinite on-site repulsion. A computation of the fermionant in polynomial time would solve many interesting fermion sign problems.
Let $G$ be an $n$-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC17) for bimodular integer programs can be used to find a maximum weight stable set in $G$ in strongly polynomial time. Building on structural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size-$O(n^2)$ extended formulation for the stable set polytope of $G$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
