Abstract:
We study the stability of solid- and supersolid (SS) phases of a three-dimensional spin- and a hardcore-Bose-Hubbard models on a body-centered cubic lattice. To see the quantum effects on the stability of the SS phase, we model the vacancies (interstitials) introduced in the solid, which are believed responsible for the appearance of the SS phase, by spinwave bosons and adopt the interaction between the condensed bosons as a criterion. A repulsive nature of the low-energy effective interaction is the necessary condition for a second-order solid-SS transition and, when this condition is met, normally the SS phase is expected. In calculating the effective interaction, we use expansions from the semiclassical- (i.e. large-S) and the Ising limit combined with the ladder approximation. The impact of quantum fluctuations crucially depends on the energy of the solid phase and that of the superfluid phase at half filling. As an application to 4He, we study the parameter region in the vicinity of the fitting parameter set given by Liu and Fisher. For this parameters set, quantum fluctuations at the second order in 1/S destabilize the solid phase, which is supposed to be stable within the mean field theory.

Abstract:
Motivated by recent interest in 2+1 dimensional quantum dimer models, we revisit Fisher's mapping of two dimensional Ising models to hardcore dimer models. First, we note that the symmetry breaking transition of the ferromagetic Ising model maps onto a non-symmetry breaking transition in dimer language -- instead it becomes a deconfinement transition for test monomers. Next, we introduce a modification of Fisher's mapping in which a second dimer model, also equivalent to the Ising model, is defined on a generically different lattice derived from the dual. In contrast to Fisher's original mapping, this enables us to reformulate frustrated Ising models as dimer models with positive weights and we illustrate this by providing a new solution of the fully frustrated Ising model on the square lattice. Finally, by means of the modified mapping we show that a large class of three-dimensional Ising models are precisely equivalent, in the time continuum limit, to particular quantum dimer models. As Ising models in three dimensions are dual to Ising gauge theories, this further yields an exact map between the latter and the quantum dimer models. The paramagnetic phase in Ising language maps onto a deconfined, topologically ordered phase in the dimer models. Using this set of ideas, we also construct an exactly soluble quantum eight vertex model.

Abstract:
A monotone CNF formula is a Boolean formula in conjunctive normal form where each variable appears positively. We design a deterministic fully polynomial-time approximation scheme (FPTAS) for counting the number of satisfying assignments for a given monotone CNF formula when each variable appears in at most $5$ clauses. Equivalently, this is also an FPTAS for counting set covers where each set contains at most $5$ elements. If we allow variables to appear in a maximum of $6$ clauses (or sets to contain $6$ elements), it is NP-hard to approximate it. Thus, this gives a complete understanding of the approximability of counting for monotone CNF formulas. It is also an important step towards a complete characterization of the approximability for all bounded degree Boolean #CSP problems. In addition, we study the hypergraph matching problem, which arises naturally towards a complete classification of bounded degree Boolean #CSP problems, and show an FPTAS for counting 3D matchings of hypergraphs with maximum degree $4$. Our main technique is correlation decay, a powerful tool to design deterministic FPTAS for counting problems defined by local constraints among a number of variables. All previous uses of this design technique fall into two categories: each constraint involves at most two variables, such as independent set, coloring, and spin systems in general; or each variable appears in at most two constraints, such as matching, edge cover, and holant problem in general. The CNF problems studied here have more complicated structures than these problems and require new design and proof techniques. As it turns out, the technique we developed for the CNF problem also works for the hypergraph matching problem. We believe that it may also find applications in other CSP or more general counting problems.

Abstract:
Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006) establish a beautiful picture for the computational complexity of approximating the partition function of the hard-core model. Let $\lambda_c(T_\Delta)$ denote the critical activity for the hard-model on the infinite $\Delta$-regular tree. Weitz presented an FPTAS for the partition function when $\lambda<\lambda_c(T_\Delta)$ for graphs with constant maximum degree $\Delta$. In contrast, Sly showed that for all $\Delta\geq 3$, there exists $\epsilon_\Delta>0$ such that (unless RP=NP) there is no FPRAS for approximating the partition function on graphs of maximum degree $\Delta$ for activities $\lambda$ satisfying $\lambda_c(T_\Delta)<\lambda<\lambda_c(T_\Delta)+\epsilon_\Delta$. We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Recent results of Li et al. and Sinclair et al. extend Weitz's approach to any 2-spin model, which includes the antiferromagnetic Ising model, to yield an FPTAS for the partition function for all graphs of constant maximum degree $\Delta$ when the parameters of the model lie in the uniqueness regime of the infinite tree $T_\Delta$. We prove the complementary result that for the antiferrogmanetic Ising model without external field that, unless RP=NP, for all $\Delta\geq 3$, there is no FPRAS for approximating the partition function on graphs of maximum degree $\Delta$ when the inverse temperature lies in the non-uniqueness regime of the infinite tree $T_\Delta$. Our results extend to a region of the parameter space for general 2-spin models. Our proof works by relating certain second moment calculations for random $\Delta$-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.

Abstract:
We introduce a quantum generalization of classical kinetic Ising models, described by a certain class of quantum many body master equations. Similarly to kinetic Ising models with detailed balance that are equivalent to certain Hamiltonian systems, our models reduce to a set of Hamiltonian systems determining the dynamics of the elements of the many body density matrix. The ground states of these Hamiltonians are well described by matrix product, or pair entangled projected states. We discuss critical properties of such Hamiltonians, as well as entanglement properties of their low energy states.

Abstract:
This paper rests to a large extend on a paper I wrote some time ago on 'Duality in generalized Ising models and phase transitions without local order parameter'. It deals with Ising models with interactions containing products of more than two spins. In contrast to the old paper I will first give examples before I come to the general statements. Of particular interest is a gauge invariant Ising model in four dimensions. It has important properties in common with models for quantum chromodynamics as developed by Ken Wilson. One phase yields an area law for the Wilson-loop yielding an interaction increasing proportional to the distance and thus corresponding to quark-confinement. The other phase yields a perimeter law allowing for a quark-gluon plasma.

Abstract:
We study the problem of approximately counting hypergraph matchings with an activity parameter $\lambda$ in hypergraphs of bounded maximum degree and bounded maximum size of hyperedges. This problem unifies two important statistical physics models in approximate counting: the hardcore model (graph independent sets) and the monomer-dimer model (graph matchings). We show for this model the critical activity $\lambda_c= \frac{d^d}{k (d-1)^{d+1}}$ is the threshold for the uniqueness of Gibbs measures on the infinite $(d+1)$-uniform $(k+1)$-regular hypertree. And we show that when $\lambda<\lambda_c$ the model exhibits strong spatial mixing at an exponential rate and there is an FPTAS for the partition function of the model on all hypergraphs of maximum degree at most $k+1$ and maximum edge size at most $d+1$. Assuming NP$\neq$RP, there is no FPRAS for the partition function of the model when $\lambda > 2\lambda_c$ on above family of hypergraphs . Towards closing this gap and obtaining a tight transition of approximability, we study the local weak convergence from an infinite sequence of random finite hypergraphs to the infinite uniform regular hypertree with specified symmetry, and prove a surprising result: the existence of such local convergence is fully characterized by the reversibility of the uniform random walk on the infinite hypertree projected on the symmetry classes. We also give an explicit construction for the sequence of random finite hypergraphs with proper local convergence property when the reversibility condition is satisfied.

Abstract:
An integral representation of the partition function for general $n$-dimensional Ising models with nearest or non-nearest neighbours interactions is given. The representation is used to derive some properties of the partition function. An exact solution is given in a particular case.

Abstract:
We consider several aspects of non-periodic Ising models in one and two dimensions. Here we are not interested in random systems, but rather in models with intrinsic long-range aperiodic order. The most prominent examples in one dimension are sequences generated by substitution rules on a finite alphabet. The classical one-dimensional Ising chain as well as the Ising quantum chain with coupling constants modulated according to substitution sequences are considered. Both the distribution of Lee-Yang zeros on the unit circle in the classical case and that of fermion frequencies in the quantum model show characteristic gap structures which follow the gap labeling theorem of Bellissard. We also investigate the zero-field Ising model on two-dimensional aperiodic graphs, which are constructed from rectangular grids in the same spirit as the so-called Labyrinth. Here, duality arguments and exact solutions in the sense of commuting transfer matrices are used to gain information about the critical behaviour.

Abstract:
Inference and learning of graphical models are both well-studied problems in statistics and machine learning that have found many applications in science and engineering. However, exact inference is intractable in general graphical models, which suggests the problem of seeking the best approximation to a collection of random variables within some tractable family of graphical models. In this paper, we focus our attention on the class of planar Ising models, for which inference is tractable using techniques of statistical physics [Kac and Ward; Kasteleyn]. Based on these techniques and recent methods for planarity testing and planar embedding [Chrobak and Payne], we propose a simple greedy algorithm for learning the best planar Ising model to approximate an arbitrary collection of binary random variables (possibly from sample data). Given the set of all pairwise correlations among variables, we select a planar graph and optimal planar Ising model defined on this graph to best approximate that set of correlations. We demonstrate our method in some simulations and for the application of modeling senate voting records.