A 16-bit Coherent Ising Machine for One-Dimensional Ring and Cubic Graph Problems.
ABSTRACT: Many tasks in our modern life, such as planning an efficient travel, image processing and optimizing integrated circuit design, are modeled as complex combinatorial optimization problems with binary variables. Such problems can be mapped to finding a ground state of the Ising Hamiltonian, thus various physical systems have been studied to emulate and solve this Ising problem. Recently, networks of mutually injected optical oscillators, called coherent Ising machines, have been developed as promising solvers for the problem, benefiting from programmability, scalability and room temperature operation. Here, we report a 16-bit coherent Ising machine based on a network of time-division-multiplexed femtosecond degenerate optical parametric oscillators. The system experimentally gives more than 99.6% of success rates for one-dimensional Ising ring and nondeterministic polynomial-time (NP) hard instances. The experimental and numerical results indicate that gradual pumping of the network combined with multiple spectral and temporal modes of the femtosecond pulses can improve the computational performance of the Ising machine, offering a new path for tackling larger and more complex instances.
Project description:Physical annealing systems provide heuristic approaches to solving combinatorial optimization problems. Here, we benchmark two types of annealing machines-a quantum annealer built by D-Wave Systems and measurement-feedback coherent Ising machines (CIMs) based on optical parametric oscillators-on two problem classes, the Sherrington-Kirkpatrick (SK) model and MAX-CUT. The D-Wave quantum annealer outperforms the CIMs on MAX-CUT on cubic graphs. On denser problems, however, we observe an exponential penalty for the quantum annealer [exp(-αDW N 2)] relative to CIMs [exp(-αCIM N)] for fixed anneal times, both on the SK model and on 50% edge density MAX-CUT. This leads to a several orders of magnitude time-to-solution difference for instances with over 50 vertices. An optimal-annealing time analysis is also consistent with a substantial projected performance difference. The difference in performance between the sparsely connected D-Wave machine and the fully-connected CIMs provides strong experimental support for efforts to increase the connectivity of quantum annealers.
Project description:Combinatorial optimization problems over large and complex systems have many applications in social networks, image processing, artificial intelligence, computational biology and a variety of other areas. Finding the optimized solution for such problems in general are usually in non-deterministic polynomial time (NP)-hard complexity class. Some NP-hard problems can be easily mapped to minimizing an Ising energy function. Here, we present an analog all-optical implementation of a coherent Ising machine (CIM) based on a network of injection-locked multicore fiber (MCF) lasers. The Zeeman terms and the mutual couplings appearing in the Ising Hamiltonians are implemented using spatial light modulators (SLMs). As a proof-of-principle, we demonstrate the use of optics to solve several Ising Hamiltonians for up to thirteen nodes. Overall, the average accuracy of the CIM to find the ground state energy was ~90% for 120 trials. The fundamental bottlenecks for the scalability and programmability of the presented CIM are discussed as well.
Project description:Reconstruction of the structure and parameters of an Ising model from binary samples is a problem of practical importance in a variety of disciplines, ranging from statistical physics and computational biology to image processing and machine learning. The focus of the research community shifted toward developing universal reconstruction algorithms that are both computationally efficient and require the minimal amount of expensive data. We introduce a new method, interaction screening, which accurately estimates model parameters using local optimization problems. The algorithm provably achieves perfect graph structure recovery with an information-theoretically optimal number of samples, notably in the low-temperature regime, which is known to be the hardest for learning. The efficacy of interaction screening is assessed through extensive numerical tests on synthetic Ising models of various topologies with different types of interactions, as well as on real data produced by a D-Wave quantum computer. This study shows that the interaction screening method is an exact, tractable, and optimal technique that universally solves the inverse Ising problem.
Project description:A network of Kerr-nonlinear parametric oscillators without dissipation has recently been proposed for solving combinatorial optimization problems via quantum adiabatic evolution through its bifurcation point. Here we investigate the behavior of the quantum bifurcation machine (QbM) in the presence of dissipation. Our numerical study suggests that the output probability distribution of the dissipative QbM is Boltzmann-like, where the energy in the Boltzmann distribution corresponds to the cost function of the optimization problem. We explain the Boltzmann distribution by generalizing the concept of quantum heating in a single nonlinear oscillator to the case of multiple coupled nonlinear oscillators. The present result also suggests that such driven dissipative nonlinear oscillator networks can be applied to Boltzmann sampling, which is used, e.g., for Boltzmann machine learning in the field of artificial intelligence.
Project description:The spin wave interference is studied in two dimensional Ising ferromagnet driven by two coherent spherical magnetic field waves by Monte Carlo simulation. The spin waves are found to propagate and interfere according to the classic rule of interference pattern generated by two point sources. The interference pattern of spin wave is observed in one boundary of the lattice. The interference pattern is detected and studied by spin flip statistics at high and low temperatures. The destructive interference is manifested as the large number of spin flips and vice versa.
Project description:We implement the Ising model on a structural connectivity matrix describing the brain at two different resolutions. Tuning the model temperature to its critical value, i.e. at the susceptibility peak, we find a maximal amount of total information transfer between the spin variables. At this point the amount of information that can be redistributed by some nodes reaches a limit and the net dynamics exhibits signature of the law of diminishing marginal returns, a fundamental principle connected to saturated levels of production. Our results extend the recent analysis of dynamical oscillators models on the connectome structure, taking into account lagged and directional influences, focusing only on the nodes that are more prone to became bottlenecks of information. The ratio between the outgoing and the incoming information at each node is related to the the sum of the weights to that node and to the average time between consecutive time flips of spins. The results for the connectome of 66 nodes and for that of 998 nodes are similar, thus suggesting that these properties are scale-independent. Finally, we also find that the brain dynamics at criticality is organized maximally to a rich-club w.r.t. the network of information flows.
Project description:The Ising model-in which degrees of freedom (spins) are binary valued (up/down)-is a cornerstone of statistical physics that shows rich behaviour when spins occupy a highly frustrated lattice such as kagome. Here we show that the layered Ising magnet Dy3Mg2Sb3O14 hosts an emergent order predicted theoretically for individual kagome layers of in-plane Ising spins. Neutron-scattering and bulk thermomagnetic measurements reveal a phase transition at ?0.3?K from a disordered spin-ice-like regime to an emergent charge ordered state, in which emergent magnetic charge degrees of freedom exhibit three-dimensional order while spins remain partially disordered. Monte Carlo simulations show that an interplay of inter-layer interactions, spin canting and chemical disorder stabilizes this state. Our results establish Dy3Mg2Sb3O14 as a tuneable system to study interacting emergent charges arising from kagome Ising frustration.
Project description:There is accumulating evidence that spontaneous fluctuations of the brain are sustained by a structural architecture of axonal fiber bundles. Various models have been used to investigate this structure-function relationship. In this work, we implemented the Ising model using the number of fibers between each pair of brain regions as input. The output of the Ising model simulations on a structural connectome was then compared with empirical functional connectivity data. A simpler two-dimensional classical Ising model was used as the baseline model for comparison purpose. Thermodynamic properties, such as the magnetic susceptibility and the specific heat, illustrated a phase transition from an ordered phase to a disordered phase at the critical temperature. Despite the differences between the two models, the lattice Ising model and the Ising model implemented on a structural connectome (the generalized Ising model) exhibited similar patterns of global properties. To study the behavior of the generalized Ising model around criticality, calculation of the dimensionality and critical exponents was performed for the first time, by introducing a new concept of distance based on structural connectivity. Same value inside the fitting error was found for the dimensionality in both models suggesting similar behavior of the models around criticality.
Project description:There has been a lot of work fitting Ising models to multivariate binary data in order to understand the conditional dependency relationships between the variables. However, additional covariates are frequently recorded together with the binary data, and may influence the dependence relationships. Motivated by such a dataset on genomic instability collected from tumor samples of several types, we propose a sparse covariate dependent Ising model to study both the conditional dependency within the binary data and its relationship with the additional covariates. This results in subject-specific Ising models, where the subject's covariates influence the strength of association between the genes. As in all exploratory data analysis, interpretability of results is important, and we use ?1 penalties to induce sparsity in the fitted graphs and in the number of selected covariates. Two algorithms to fit the model are proposed and compared on a set of simulated data, and asymptotic results are established. The results on the tumor dataset and their biological significance are discussed in detail.
Project description:Solving intractable mathematical problems in simulators composed of atoms, ions, photons, or electrons has recently emerged as a subject of intense interest. We extend this concept to phonons that are localized in spectrally pure resonances in an electromechanical system that enables their interactions to be exquisitely fashioned via electrical means. We harness this platform to emulate the Ising Hamiltonian whose spin 1/2 particles are replicated by the phase bistable vibrations from the parametric resonances of multiple modes. The coupling between the mechanical spins is created by generating two-mode squeezed states, which impart correlations between modes that can imitate a random, ferromagnetic state or an antiferromagnetic state on demand. These results suggest that an electromechanical simulator could be built for the Ising Hamiltonian in a nontrivial configuration, namely, for a large number of spins with multiple degrees of coupling.