Experimental investigation of performance differences between coherent Ising machines and a quantum annealer.

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.

Combinatorial optimization using dynamical phase transitions in driven-dissipative systems.

The dynamics of driven-dissipative systems is shown to be well-fitted for achieving efficient combinatorial optimization. The proposed method can be applied to solve any combinatorial optimization problem that is equivalent to minimizing an Ising Hamiltonian. Moreover, the dynamics considered can be implemented using various physical systems as it is based on generic dynamics-the normal form of the supercritical pitchfork bifurcation. The computational principle of the proposed method relies on an hybrid analog-digital representation of the binary Ising spins by considering the gradient descent of a Lyapunov function that is the sum of an analog Ising Hamiltonian and archetypal single or double-well potentials. By gradually changing the shape of the latter potentials from a single to double well shape, it can be shown that the first nonzero steady states to become stable are associated with global minima of the Ising Hamiltonian, under the approximation that all analog spins have the same amplitude. In the more general case, the heterogeneity in amplitude between analog spins induces the stabilization of local minima, which reduces the quality of solutions to combinatorial optimization problems. However, we show that the heterogeneity in amplitude can be reduced by setting the parameters of the driving signal near a regime, called the dynamic phase transition, where the analog spins' DC components map more accurately the global minima of the Ising Hamiltonian which, in turn, increases the quality of solutions found. Last, we discuss the possibility of a physical implementation of the proposed method using networks of degenerate optical parametric oscillators.

A coherent Ising machine for 2000-node optimization problems.

The analysis and optimization of complex systems can be reduced to mathematical problems collectively known as combinatorial optimization. Many such problems can be mapped onto ground-state search problems of the Ising model, and various artificial spin systems are now emerging as promising approaches. However, physical Ising machines have suffered from limited numbers of spin-spin couplings because of implementations based on localized spins, resulting in severe scalability problems. We report a 2000-spin network with all-to-all spin-spin couplings. Using a measurement and feedback scheme, we coupled time-multiplexed degenerate optical parametric oscillators to implement maximum cut problems on arbitrary graph topologies with up to 2000 nodes. Our coherent Ising machine outperformed simulated annealing in terms of accuracy and computation time for a 2000-node complete graph.

A fully programmable 100-spin coherent Ising machine with all-to-all connections.

Unconventional, special-purpose machines may aid in accelerating the solution of some of the hardest problems in computing, such as large-scale combinatorial optimizations, by exploiting different operating mechanisms than those of standard digital computers. We present a scalable optical processor with electronic feedback that can be realized at large scale with room-temperature technology. Our prototype machine is able to find exact solutions of, or sample good approximate solutions to, a variety of hard instances of Ising problems with up to 100 spins and 10,000 spin-spin connections.

A 16-bit Coherent Ising Machine for One-Dimensional Ring and Cubic Graph Problems.

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.

Binary phase oscillation of two mutually coupled semiconductor lasers.

A two-site Ising model is implemented as an injection-locked laser network consisting of a single master laser and two mutually coupled slave lasers. We observed ferromagnetic and antiferromagnetic orders in the in-phase and out-of-phase couplings between the two slave lasers. Their phase difference is locked to either 0 or π even if the coupling path is continuously modulated. The system automatically selects the oscillation frequency to satisfy the in-phase or out-of-phase coupling condition, when the mutual coupling dominates over the injection-locking by the master laser.

Mapping of Ising models onto injection-locked laser systems.

We propose a mapping protocol to implement Ising models in injection-locked laser systems. The proposed scheme is based on optical coherent feedback and can be potentially applied for large-scale Ising problems.

Quantum simulator for the hubbard model with long-range coulomb interactions using surface acoustic waves.

An experimental scheme for a quantum simulator of strongly correlated electrons is proposed. Our scheme employs electrons confined in a two-dimensional electron gas in a GaAs/AlGaAs heterojunction. Two surface acoustic waves are then induced in the substrate, creating a two-dimensional "egg-carton" potential. The dynamics of the electrons in this potential are described by a Hubbard model with long-range Coulomb interactions. Estimates of the Hubbard parameters suggest that observations of quantum phase transition phenomena are within experimental reach.