We present and apply a general-purpose, multistart algorithm for improving the performance of low-energy samplers used for solving optimization problems. The algorithm iteratively fixes the value of ...a large portion of the variables to values that have a high probability of being optimal. The resulting problems are smaller and less connected, and samplers tend to give better low-energy samples for these problems. The algorithm is trivially parallelizable since each start in the multistart algorithm is independent, and could be applied to any heuristic solver that can be run multiple times to give a sample. We present results for several classes of hard problems solved using simulated annealing, path-integral quantum Monte Carlo, parallel tempering with isoenergetic cluster moves, and a quantum annealer, and show that the success metrics and the scaling are improved substantially. When combined with this algorithm, the quantum annealer's scaling was substantially improved for native Chimera graph problems. In addition, with this algorithm the scaling of the time to solution of the quantum annealer is comparable to the Hamze-de Freitas-Selby algorithm on the weak-strong cluster problems introduced by Boixo et al. Parallel tempering with isoenergetic cluster moves was able to consistently solve three-dimensional spin glass problems with 8000 variables when combined with our method, whereas without our method it could not solve any.
Population annealing is an efficient sequential Monte Carlo algorithm for simulating equilibrium states of systems with rough free-energy landscapes. The theory of population annealing is presented, ...and systematic and statistical errors are discussed. The behavior of the algorithm is studied in the context of large-scale simulations of the three-dimensional Ising spin glass and the performance of the algorithm is compared to parallel tempering. It is found that the two algorithms are similar in efficiency though with different strengths and weaknesses.
In order to treat all-to-all-connected quadratic binary optimization problems (QUBOs) with hardware quantum annealers, an embedding of the original problem is required due to the sparsity of the ...topology of the hardware. The embedding of fully connected graphs—typically found in industrial applications—incurs a quadratic space overhead and thus a significant overhead in the time to solution. Here, we investigate this embedding penalty of established planar embedding schemes such as square-lattice embedding, embedding on a chimera lattice, and the Lechner-Hauke-Zoller scheme, using simulated quantum annealing on classical hardware. Large-scale quantum Monte Carlo simulation suggests a polynomial time-to-solution overhead. Our results demonstrate that standard analog quantum annealing hardware is at a disadvantage in comparison to classical digital annealers, as well as gate-model quantum annealers, and could also serve as a benchmark for improvements of the standard quantum annealing protocol.
The nature of ordering in dilute dipolar interacting systems dates back to the work of Debye and is one of the most basic, oldest and as-of-yet unsettled problems in magnetism. While spin-glass order ...is readily observed in several RKKY-interacting systems, dipolar spin glasses are the subject of controversy and ongoing scrutiny, e.g., in LiHoxY1−xF4 , a rare-earth randomly diluted uniaxial (Ising) dipolar system. In particular, it is unclear if the spin-glass phase in these paradigmatic materials persists in the limit of zero concentration or not. We study an effective model of LiHoxY1−xF4 using large-scale Monte Carlo simulations that combine parallel tempering with a special cluster algorithm tailored to overcome the numerical difficulties that occur at extreme dilutions. We find a paramagnetic to spin-glass phase transition for all Ho+ ion concentrations down to the smallest concentration numerically accessible, 0.1%, and including Ho+ ion concentrations that coincide with those studied experimentally up to 16.7%. Our results suggest that randomly diluted dipolar Ising systems have a spin-glass phase in the limit of vanishing dipole concentration, with a critical temperature vanishing linearly with concentration. The agreement of our results with mean-field theory testifies to the irrelevance of fluctuations in interactions strengths, albeit being strong at small concentrations, to the nature of the low-temperature phase and the functional form of the critical temperature of dilute anisotropic dipolar systems. Deviations from linearity in experimental results at the lowest concentrations are discussed.
Known for their ability to identify hidden patterns in data, artificial neural networks are among the most powerful machine learning tools. Most notably, neural networks have played a central role in ...identifying states of matter and phase transitions across condensed matter physics. To date, most studies have focused on systems where different phases of matter and their phase transitions are known, and thus the performance of neural networks is well controlled. While neural networks present an exciting new tool to detect new phases of matter, here we demonstrate that when the training sets are poisoned (i.e. poor training data or mislabeled data) it is easy for neural networks to make misleading predictions.
PDF
