ترغب بنشر مسار تعليمي؟ اضغط هنا

The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition

110   0   0.0 ( 0 )
 نشر من قبل Helmut Katzgraber
 تاريخ النشر 2019
  مجال البحث فيزياء
والبحث باللغة English




اسأل ChatGPT حول البحث

We propose the Wishart planted ensemble, a class of zero-field Ising models with tunable algorithmic hardness and specifiable (or planted) ground state. The problem class arises from a simple procedure for generating a family of random integer programming problems with specific statistical symmetry properties, but turns out to have intimate connections to a sign-inverted variant of the Hopfield model. The Hamiltonian contains only 2-spin interactions, with the coupler matrix following a type of Wishart distribution. The class exhibits a classical first-order phase transition in temperature. For some parameter settings the model has a locally-stable paramagnetic state, a feature which correlates strongly with difficulty in finding the ground state and suggests an extremely rugged energy landscape. We analytically probe the ensemble thermodynamic properties by deriving the Thouless-Anderson-Palmer equations and free energy and corroborate the results with a replica and annealed approximation analysis; extensive Monte Carlo simulations confirm our predictions of the first-order transition temperature. The class exhibits a wide variation in algorithmic hardness as a generation parameter is varied, with a pronounced easy-hard-easy profile and peak in solution time towering many orders of magnitude over that of the easy regimes. By deriving the ensemble-averaged energy distribution and taking into account finite-precision representation, we propose an analytical expression for the location of the hardness peak and show that at fixed precision, the number of constraints in the integer program must increase with system size to yield truly hard problems. The Wishart planted ensemble is interesting for its peculiar physical properties and provides a useful and analytically-transparent set of problems for benchmarking optimization algorithms.



قيم البحث

اقرأ أيضاً

We investigate the behavior of the Ising model on two connected Barabasi-Albert scale-free networks. We extend previous analysis and show that a first order temperature-driven phase transition occurs in such system. The transition between antiparalel ly ordered networks to paralelly ordered networks is shown to be discontinuous. We calculate the critical temperature. We confirm the calculations with numeric simulations using Monte-Carlo methods.
We perform intensive numerical simulations of the three-dimensional site-diluted Ising antiferromagnet in a magnetic field at high values of the external applied field. Even if data for small lattice sizes are compatible with second-order criticality , the critical behavior of the system shows a crossover from second-order to first-order behavior for large system sizes, where signals of latent heat appear. We propose apparent critical exponents for the dependence of some observables with the lattice size for a generic (disordered) first-order phase transition.
We investigate the computational hardness of spin-glass instances on a square lattice, generated via a recently introduced tunable and scalable approach for planting solutions. The method relies on partitioning the problem graph into edge-disjoint su bgraphs, and planting frustrated, elementary subproblems that share a common local ground state, which guarantees that the ground state of the entire problem is known a priori. Using population annealing Monte Carlo, we compare the typical hardness of problem classes over a large region of the multi-dimensional tuning parameter space. Our results show that the problems have a wide range of tunable hardness. Moreover, we observe multiple transitions in the hardness phase space, which we further corroborate using simulated annealing and simulated quantum annealing. By investigating thermodynamic properties of these planted systems, we demonstrate that the harder samples undergo magnetic ordering transitions which are also ultimately responsible for the observed hardness transitions on changing the sample composition.
72 - Zi-Yong Ge , Heng Fan 2020
We focus on the many-body eigenstates across a localization-delocalization phase transition. To characterize the robustness of the eigenstates, we introduce the eigenstate overlaps $mathcal{O}$ with respect to the different boundary conditions. In th e ergodic phase, the average of eigenstate overlaps $bar{mathcal{O}}$ is exponential decay with the increase of the system size indicating the fragility of its eigenstates, and this can be considered as an eigenstate-version butterfly effect of the chaotic systems. For localized systems, $bar{mathcal{O}}$ is almost size-independent showing the strong robustness of the eigenstates and the broken of eigenstate thermalization hypothesis. In addition, we find that the response of eigenstates to the change of boundary conditions in many-body localized systems is identified with the single-particle wave functions in Anderson localized systems. This indicates that the eigenstates of the many-body localized systems, as the many-body wave functions, may be independent of each other. We demonstrate that this is consistent with the existence of a large number of quasilocal integrals of motion in the many-body localized phase. Our results provide a new method to study localized and delocalized systems from the perspective of eigenstates.
The intriguing phenomenon of many-body localization (MBL) has attracted significant interest recently, but a complete characterization is still lacking. In this work, we introduce the total correlations, a concept from quantum information theory capt uring multi-partite correlations, to the study of this phenomenon. We demonstrate that the total correlations of the diagonal ensemble provides a meaningful diagnostic tool to pin-down, probe, and better understand the MBL transition and ergodicity breaking in quantum systems. In particular, we show that the total correlations has sub-linear dependence on the system size in delocalized, ergodic phases, whereas we find that it scales extensively in the localized phase developing a pronounced peak at the transition. We exemplify the power of our approach by means of an exact diagonalization study of a Heisenberg spin chain in a disordered field.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا