Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputational hardness of spin-glass problems with tile-planted solutions
84
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The availability of quantum annealing devices with hundreds of qubits has made the experimental demonstration of a quantum speedup for optimization problems a coveted, albeit elusive goal. Going beyond earlier studies of random Ising problems, here we introduce a method to construct a set of frustrated Ising-model optimization problems with tunable hardness. We study the performance of a D-Wave Two device (DW2) with up to 503 qubits on these problems and compare it to a suite of classical algorithms, including a highly optimized algorithm designed to compete directly with the DW2. The problems are generated around predetermined ground-state configurations, called planted solutions, which makes them particularly suitable for benchmarking purposes. The problem set exhibits properties familiar from constraint satisfaction (SAT) problems, such as a peak in the typical hardness of the problems, determined by a tunable clause density parameter. We bound the hardness regime where the DW2 device either does not or might exhibit a quantum speedup for our problem set. While we do not find evidence for a speedup for the hardest and most frustrated problems in our problem set, we cannot rule out that a speedup might exist for some of the easier, less frustrated problems. Our empirical findings pertain to the specific D-Wave processor and problem set we studied and leave open the possibility that future processors might exhibit a quantum speedup on the same problem set.
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.
We present a methodology for generating Ising Hamiltonians of tunable complexity and with a priori known ground states based on a decomposition of the model graph into edge-disjoint subgraphs. The idea is illustrated with a spin-glass model defined on a cubic lattice, where subproblems, whose couplers are restricted to the two values {-1,+1}, are specified on unit cubes and are parametrized by their local degeneracy. The construction is shown to be equivalent to a type of three-dimensional constraint satisfaction problem known as the tiling puzzle. By varying the proportions of subproblem types, the Hamiltonian can span a dramatic range of typical computational complexity, from fairly easy to many orders of magnitude more difficult than prototypical bimodal and Gaussian spin glasses in three space dimensions. We corroborate this behavior via experiments with different algorithms and discuss generalizations and extensions to different types of graphs.
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.
Spin Glasses (SG) are paradigmatic models for physical, computer science, biological and social systems. The problem of studying the dynamics for SG models is NP hard, i.e., no algorithm solves it in polynomial time. Here we implement the optical simulation of a SG, exploiting the N segments of a wavefront shaping device to play the role of the spin variables, combining the interference at downstream of a scattering material to implement the random couplings between the spins (the J ij matrix) and measuring the light intensity on a number P of targets to retrieve the energy of the system. By implementing a plain Metropolis algorithm, we are able to simulate the spin model dynamics, while the degree of complexity of the potential energy landscape and the region of phase diagram explored is user-defined acting on the ratio the P/N = alpha. We study experimentally, numerically and analytically this peculiar system displaying a paramagnetic, a ferromagnetic and a SG phase, and we demonstrate that the transition temperature T g to the glassy phase from the paramagnetic phase grows with alpha. With respect to standard in silico approach, in the optical SG interaction terms are realized simultaneously when the independent light rays interferes at the target screen, enabling inherently parallel measurements of the energy, rather than computations scaling with N as in purely in silico simulations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
