Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSelf-Sustained Clusters as Drivers of Computational Hardness in $p$-spin Models
109
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
While macroscopic properties of spin glasses have been thoroughly investigated, their manifestation in the corresponding microscopic configurations is much less understood. Cases where both descriptions have been provided, such as constraint satisfaction problems, are limited to their ground state properties. To identify the emerging microscopic structures with macroscopic phases at different temperatures, we study the $p$-spin model with $p!=!3$. We investigate the properties of self-sustained clusters, defined as variable sets where in-cluster induced fields dominate over the field induced by out-cluster spins, giving rise to stable configurations with respect to fluctuations. We compute the entropy of self-sustained clusters as a function of temperature and their sizes. In-cluster fields properties and the difference between in-cluster and out-cluster fields support the observation of slow-evolving spins in spin models. The findings are corroborated by observations in finite dimensional lattices at low temperatures.
rate research
Read More
To identify emerging microscopic structures in low temperature spin glasses, we study self-sustained clusters (SSC) in spin models defined on sparse random graphs. A message-passing algorithm is developed to determine the probability of individual spins to belong to SSC. Results for specific instances, which compare the predicted SSC associations with the dynamical properties of spins obtained from numerical simulations, show that SSC association identifies individual slow-evolving spins. This insight gives rise to a powerful approach for predicting individual spin dynamics from a single snapshot of an equilibrium spin configuration, namely from limited static information, which can be used to devise generic prediction tools applicable to a wide range of areas.
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 subgraphs, 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.
In this note, we provide a unifying framework to investigate the computational complexity of classical spin models and give the full classification on spin models in terms of system dimensions, randomness, external magnetic fields and types of spin coupling. We further discuss about the implications of NP-complete Hamiltonian models in physics and the fundamental limitations of all numerical methods imposed by such models. We conclude by a brief discussion on the picture when quantum computation and quantum complexity theory are included.
We consider the random fluctuations of the free energy in the $p$-spin version of the Sherrington-Kirkpatrick model in the high temperature regime. Using the martingale approach of Comets and Neveu as used in the standard SK model combined with truncation techniques inspired by a recent paper by Talagrand on the $p$-spin version, we prove that (for $p$ even) the random corrections to the free energy are on a scale $N^{-(p-2)/4}$ only, and after proper rescaling converge to a standard Gaussian random variable. This is shown to hold for all values of the inverse temperature, $b$, smaller than a critical $b_p$. We also show that $b_pto sqrt{2ln 2}$ as $puparrow +infty$. Additionally we study the formal $puparrow +infty$ limit of these models, the random energy model. Here we compute the precise limit theorem for the partition function at {it all} temperatures. For $b<sqrt{2ln2}$, fluctuations are found at an {it exponentially small} scale, with two distinct limit laws above and below a second critical value $sqrt{ln 2/2}$: For $b$ up to that value the rescaled fluctuations are Gaussian, while below that there are non-Gaussian fluctuations driven by the Poisson process of the extreme values of the random energies. For $b$ larger than the critical $sqrt{2ln 2}$, the fluctuations of the logarithm of the partition function are on scale one and are expressed in terms of the Poisson process of extremes. At the critical temperature, the partition function divided by its expectation converges to 1/2.
We study both classical and quantum algorithms to solve a hard optimization problem, namely 3-XORSAT on 3-regular random graphs. By introducing a new quasi-greedy algorithm that is not allowed to jump over large energy barriers, we show that the problem hardness is mainly due to entropic barriers. We study, both analytically and numerically, several optimization algorithms, finding that entropic barriers affect in a similar way classical local algorithms and quantum annealing. For the adiabatic algorithm, the difficulty we identify is distinct from that of tunnelling under large barriers, but does, nonetheless, give rise to exponential running (annealing) times.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
