Combinatorial Optimization with Physics-Inspired Graph Neural Networks

We demonstrate how graph neural networks can be used to solve combinatorial optimization problems. Our approach is broadly applicable to canonical NP-hard problems in the form of quadratic unconstrained binary optimization problems, such as maximum cut, minimum vertex cover, maximum independent set, as well as Ising spin glasses and higher-order generalizations thereof in the form of polynomial unconstrained binary optimization problems. We apply a relaxation strategy to the problem Hamiltonian to generate a differentiable loss function with which we train the graph neural network and apply a simple projection to integer variables once the unsupervised training process has completed. We showcase our approach with numerical results for the canonical maximum cut and maximum independent set problems. We find that the graph neural network optimizer performs on par or outperforms existing solvers, with the ability to scale beyond the state of the art to problems with millions of variables.

Scaling overhead of embedding optimization problems in quantum annealing

In order to treat all-to-all connected quadratic binary optimization problems (QUBO) with hardware quantum annealers, an embedding of the original problem is required due to the sparsity of the hardwares topology. Embedding 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 minor embedding on a square lattice, minor embedding on a Chimera graph, and the Lechner-Hauke-Zoller scheme using simulated quantum annealing on classical hardware. Large-scale quantum Monte Carlo simulation suggest 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 benchmark for improvements of the standard quantum annealing protocol.

Griffiths-McCoy singularity on the diluted Chimera graph: Monte Carlo simulations and experiments on the quantum hardware

The Griffiths-McCoy singularity is a phenomenon characteristic of low-dimensional disordered quantum spin systems, in which the magnetic susceptibility shows singular behavior as a function of the external field even within the paramagnetic phase. We study whether this phenomenon is observed in the transverse-field Ising model with disordered ferromagnetic interactions on the quasi-two-dimensional diluted Chimera graph both by quantum Monte Carlo simulations and by extensive experiments on the D-Wave quantum annealer used as a quantum simulator. From quantum Monte Carlo simulations, evidence is found for the existence of the Griffiths-McCoy singularity in the paramagnetic phase. The experimental approach on the quantum hardware produces results that are less clear-cut due to the intrinsic noise and errors in the analog quantum device but can nonetheless be interpreted to be consistent with the existence of the Griffiths-McCoy singularity as in the Monte Carlo case. This is the first experimental approach based on an analog quantum simulator to study the subtle phenomenon of Griffiths-McCoy singularities in a disordered quantum spin system, through which we have clarified the capabilities and limitations of the D-Wave quantum annealer as a quantum simulator.

Adding color: Visualization of energy landscapes in spin glasses

Disconnectivity graphs are used to visualize the minima and the lowest energy barriers between the minima of complex systems. They give an easy and intuitive understanding of the underlying energy landscape and, as such, are excellent tools for understanding the complexity involved in finding low-lying or global minima of such systems. We have developed a classification scheme that categorizes highly-degenerate minima of spin glasses based on similarity and accessibility of the individual states. This classification allows us to condense the information pertained in different dales of the energy landscape to a single representation using color to distinguish its type and a bar chart to indicate the average size of the dales at their respective energy levels. We use this classification to visualize disconnectivity graphs of small representations of different tile-planted models of spin glasses. An analysis of the results shows that different models have distinctly different features in the total number of minima, the distribution of the minima with respect to the ground state, the barrier height and in the occurrence of the different types of minimum energy dales.

Machine learning in physics: The pitfalls of poisoned training sets

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.

Learning to find order in disorder

We introduce the use of neural networks as classifiers on classical disordered systems with no spatial ordering. In this study, we implement a convolutional neural network trained to identify the spin-glass state in the three-dimensional Edwards-Anderson Ising spin-glass model from an input of Monte Carlo sampled configurations at a given temperature. The neural network is designed to be flexible with the input size and can accurately perform inference over a small sample of the instances in the test set. Using the neural network to classify instances of the three-dimensional Edwards-Anderson Ising spin-glass in a (random) field we show that the inferred phase boundary is consistent with the absence of an Almeida-Thouless line.

Distribution of interevent avalanche times in disordered and frustrated spin systems

Hysteresis loops and the associated avalanche statistics of spin systems, such as the random-field Ising and Edwards-Anderson spin-glass models, have been extensively studied. A particular focus has been on self-organized criticality, manifest in power-law distributions of avalanche sizes. Considerably less work has been done on the statistics of the times between avalanches. This paper considers this issue, generalizing the work of Nampoothiri et al. [Phys. Rev. E 96, 032107 (2017)] in one space dimension to higher space dimensions. In addition to the interevent statistics of all avalanches, we also consider what happens when events are restricted to those exceeding a certain threshold size. Doing so raises the possibility of altering the definition of time to count the number of small events between the large ones, which provides for an analog to the concept of natural time introduced by the geophysics community with the goal of predicting patterns in seismic events. We analyze the distribution of time and natural time intervals both in the case of models that include only nearest-neighbor interactions, as well as models with (sparse) long-range couplings.

Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly

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 work 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: Glassy Chimeras Could Be Blind to Quantum Speedup. . . [Phys. Rev. X 4, 021008 (2014)]

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.

Low-temperature behavior of the statistics of the overlap distribution in Ising spin-glass models

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 dimensions, 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.