Recent tests performed on the D-Wave Two quantum annealer have revealed no clear evidence of speedup over conventional silicon-based technologies. Here, we present results from classical parallel-tempering Monte Carlo simulations combined with isoene
rgetic cluster moves of the archetypal benchmark problem-an Ising spin glass-on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, we study the best-case resilience, i.e., the probability that the ground-state configuration is not affected by random fields and random-bond fluctuations found on the chip. We thus compute classical upper-bound success probabilities for different types of disorder used in the benchmarks and predict that an increase in the number of qubits will require either error correction schemes or a drastic reduction of the intrinsic noise found in these devices. We outline strategies to develop robust, as well as hard benchmarks for quantum annealing devices, as well as any other computing paradigm affected by noise.
There has been considerable progress in the design and construction of quantum annealing devices. However, a conclusive detection of quantum speedup over traditional silicon-based machines remains elusive, despite multiple careful studies. In this wo
rk we outline strategies to design hard tunable benchmark instances based on insights from the study of spin glasses - the archetypal random benchmark problem for novel algorithms and optimization devices. We propose to complement head-to-head scaling studies that compare quantum annealing machines to state-of-the-art classical codes with an approach that compares the performance of different algorithms and/or computing architectures on different classes of computationally hard tunable spin-glass instances. The advantage of such an approach lies in having to only compare the performance hit felt by a given algorithm and/or architecture when the instance complexity is increased. Furthermore, we propose a methodology that might not directly translate into the detection of quantum speedup, but might elucidate whether quantum annealing has a `quantum advantage over corresponding classical algorithms like simulated annealing. Our results on a 496 qubit D-Wave Two quantum annealing device are compared to recently-used state-of-the-art thermal simulated annealing codes.
Erratum to Phys. Rev. X 4, 021008 (2014): The critical exponent associated with the ferromagnetic susceptibility was computed incorrectly. Furthermore, Ising ferromagnets on the Chimera topology have the same universality class as two-dimensional Ising ferromagnets.
Using Monte Carlo simulations, we study in detail the overlap distribution for individual samples for several spin-glass models including the infinite-range Sherrington-Kirkpatrick model, short-range Edwards-Anderson models in three and four space di
mensions, and one-dimensional long-range models with diluted power-law interactions. We study three long-range models with different powers as follows: the first is approximately equivalent to a short-range model in three dimensions, the second to a short-range model in four dimensions, and the third to a short-range model in the mean-field regime. We study an observable proposed earlier by some of us which aims to distinguish the replica symmetry breaking picture of the spin-glass phase from the droplet picture, finding that larger system sizes would be needed to unambiguously determine which of these pictures describes the low-temperature state of spin glasses best, except for the Sherrington-Kirkpatrick model which is unambiguously described by replica symmetry breaking. Finally, we also study the median integrated overlap probability distribution and a typical overlap distribution, finding that these observables are not particularly helpful in distinguishing the replica symmetry breaking and the droplet pictures.
In Phys. Rev. Lett. 110, 219701 (2013) [arXiv:1211.0843] Billoire et al. criticize the conclusions of our Letter [Phys. Rev. Lett. 109, 177204 (2012), arxiv:1206.0783]. They argue that considering the Edwards-Anderson and Sherrington-Kirkpatrick mode
ls at the same temperature is inappropriate and propose an interpretation based on the replica symmetry breaking theory. Here we show that the theory presented in the Comment does not explain our data on the Edwards-Anderson spin glass and we stand by our assertion that the low-temperature behavior of the Edwards-Anderson spin glass model does not appear to be mean-field like.
We reply to the Comment by Mobius and Richter [arXiv:0908.3092, Phys. Rev. Lett. 105, 039701 (2010)] on Density of States and Critical Behavior of the Coulomb Glass [arXiv:0805.4640, Phys. Rev. Lett. 102, 067205 (2009)] and address the issues raised
with our results on the density of states. In addition, we correct our statements about the random displacement version of the Coulomb glass model where the Wigner crystal is not as robust to disorder as stated. Still, our main result of a lack of a finite-temperature transition in the Coulomb glass remains unchallenged.
We test for the existence of a spin-glass phase transition, the de Almeida-Thouless line, in an externally-applied (random) magnetic field by performing Monte Carlo simulations on a power-law diluted one-dimensional Ising spin glass for very large sy
stem sizes. We find that an Almeida-Thouless line only occurs in the mean field regime, which corresponds, for a short-range spin glass, to dimension d larger than 6.
We present results from Monte Carlo simulations to test for ultrametricity and clustering properties in spin-glass models. By using a one-dimensional Ising spin glass with random power-law interactions where the universality class of the model can be
tuned by changing the power-law exponent, we find signatures of ultrametric behavior both in the mean-field and non-mean-field universality classes for large linear system sizes. Furthermore, we confirm the existence of nontrivial connected components in phase space via a clustering analysis of configurations.
The concept of replica symmetry breaking found in the solution of the mean-field Sherrington-Kirkpatrick spin-glass model has been applied to a variety of problems in science ranging from biological to computational and even financial analysis. Thus
it is of paramount importance to understand which predictions of the mean-field solution apply to non-mean-field systems, such as realistic short-range spin-glass models. The one-dimensional spin glass with random power-law interactions promises to be an ideal test-bed to answer this question: Not only can large system sizes-which are usually a shortcoming in simulations of high-dimensional short-range system-be studied, by tuning the power-law exponent of the interactions the universality class of the model can be continuously tuned from the mean-field to the short-range universality class. We present details of the model, as well as recent applications to some questions of the physics of spin glasses. First, we study the existence of a spin-glass state in an external field. In addition, we discuss the existence of ultrametricity in short-range spin glasses. Finally, because the range of interactions can be changed, the model is a formidable test-bed for optimization algorithms.
