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

Phase and frequency-resolved microscopy of operating spin Hall nano-oscillator arrays

Coherent optical detection is a powerful technique for characterizing a wide range of physical excitations. Here, we use two optical approaches (fundamental and parametric pumping) to microscopically characterize the high-frequency auto-oscillations of single and multiple nano-constriction spin Hall nano-oscillators (SHNOs). To validate the technique and demonstrate its robustness, we study SHNOs made from two different material stacks, NiFe/Pt and W/CoFeB/MgO, and investigate the influence of both the RF injection power and the laser power on the measurements, comparing the optical results to conventional electrical measurements. To demonstrate the key features of direct, non-invasive, submicron, spatial, and phase-resolved characterization of the SHNO magnetodynamics, we map out the auto-oscillation magnitude and phase of two phase-binarized SHNOs used in Ising machines. This proof-of-concept platform establishes a strong foundation for further extensions, contributing to the ongoing development of crucial characterization techniques for emerging computing technologies based on spintronics devices.

Training an Ising machine with equilibrium propagation

Ising machines, which are hardware implementations of the Ising model of coupled spins, have been influential in the development of unsupervised learning algorithms at the origins of Artificial Intelligence (AI). However, their application to AI has been limited due to the complexities in matching supervised training methods with Ising machine physics, even though these methods are essential for achieving high accuracy. In this study, we demonstrate an efficient approach to train Ising machines in a supervised way through the Equilibrium Propagation algorithm, achieving comparable results to software-based implementations. We employ the quantum annealing procedure of the D-Wave Ising machine to train a fully-connected neural network on the MNIST dataset. Furthermore, we demonstrate that the machine's connectivity supports convolution operations, enabling the training of a compact convolutional network with minimal spins per neuron. Our findings establish Ising machines as a promising trainable hardware platform for AI, with the potential to enhance machine learning applications.

Energy-efficient superparamagnetic Ising machine and its application to traveling salesman problems

The growth of artificial intelligence leads to a computational burden in solving non-deterministic polynomial-time (NP)-hard problems. The Ising computer, which aims to solve NP-hard problems faces challenges such as high power consumption and limited scalability. Here, we experimentally present an Ising annealing computer based on 80 superparamagnetic tunnel junctions (SMTJs) with all-to-all connections, which solves a 70-city traveling salesman problem (TSP, 4761-node Ising problem). By taking advantage of the intrinsic randomness of SMTJs, implementing global annealing scheme, and using efficient algorithm, our SMTJ-based Ising annealer outperforms other Ising schemes in terms of power consumption and energy efficiency. Additionally, our approach provides a promising way to solve complex problems with limited hardware resources. Moreover, we propose a cross-bar array architecture for scalable integration using conventional magnetic random-access memories. Our results demonstrate that the SMTJ-based Ising computer with high energy efficiency, speed, and scalability is a strong candidate for future unconventional computing schemes.

Oscillatory Neural Network-Based Ising Machine Using 2D Memristors

Neural networks are increasingly used to solve optimization problems in various fields, including operations research, design automation, and gene sequencing. However, these networks face challenges due to the nondeterministic polynomial time (NP)-hard issue, which results in exponentially increasing computational complexity as the problem size grows. Conventional digital hardware struggles with the von Neumann bottleneck, the slowdown of Moore's law, and the complexity arising from heterogeneous system design. Two-dimensional (2D) memristors offer a potential solution to these hardware challenges, with their in-memory computing, decent scalability, and rich dynamic behaviors. In this study, we explore the use of nonvolatile 2D memristors to emulate synapses in a discrete-time Hopfield neural network, enabling the network to solve continuous optimization problems, like finding the minimum value of a quadratic polynomial, and tackle combinatorial optimization problems like Max-Cut. Additionally, we coupled volatile memristor-based oscillators with nonvolatile memristor synapses to create an oscillatory neural network-based Ising machine, a continuous-time analog dynamic system capable of solving combinatorial optimization problems including Max-Cut and map coloring through phase synchronization. Our findings demonstrate that 2D memristors have the potential to significantly enhance the efficiency, compactness, and homogeneity of integrated Ising machines, which is useful for future advances in neural networks for optimization problems.

How to experimentally evaluate the adiabatic condition for quantum annealing

We propose an experimental method for evaluating the adiabatic condition during quantum annealing (QA), which will be essential for solving practical problems. The adiabatic condition consists of the transition matrix element and the energy gap, and our method simultaneously provides information about these components without diagonalizing the Hamiltonian. The key idea is to measure the power spectrum of a time domain signal by adding an oscillating field during QA, and we can estimate the values of the transition matrix element and energy gap from the measurement output. Our results provides a powerful experimental basis for analyzing the performance of QA.

Parametric Frequency Divider Based Ising Machines

We report on a new class of Ising machines (IMs) that rely on coupled parametric frequency dividers (PFDs) as macroscopic artificial spins. Unlike the IM counterparts based on subharmonic-injection locking (SHIL), PFD IMs do not require strong injected continuous-wave signals or applied dc voltages. Therefore, they show a significantly lower power consumption per spin compared to SHIL-based IMs, making it feasible to accurately solve large-scale combinatorial optimization problems that are hard or even impossible to solve by using the current von Neumann computing architectures. Furthermore, using high quality factor resonators in the PFD design makes PFD IMs able to exhibit a nanowatt-level power per spin. Also, it remarkably allows a speedup of the phase synchronization among the PFDs, resulting in shorter time to solution and lower energy to solution despite the resonators' longer relaxation time. As a proof of concept, a 4-node PFD IM has been demonstrated. This IM correctly solves a set of Max-Cut problems while consuming just 600 nanowatts per spin. This power consumption is 2 orders of magnitude lower than the power per spin of state-of-the-art SHIL-based IMs operating at the same frequency.

Ferroelectric compute-in-memory annealer for combinatorial optimization problems

Computationally hard combinatorial optimization problems (COPs) are ubiquitous in many applications. Various digital annealers, dynamical Ising machines, and quantum/photonic systems have been developed for solving COPs, but they still suffer from the memory access issue, scalability, restricted applicability to certain types of COPs, and VLSI-incompatibility, respectively. Here we report a ferroelectric field effect transistor (FeFET) based compute-in-memory (CiM) annealer for solving larger-scale COPs efficiently. Our CiM annealer converts COPs into quadratic unconstrained binary optimization (QUBO) formulations, and uniquely accelerates in-situ the core vector-matrix-vector (VMV) multiplication operations of QUBO formulations in a single step. Specifically, the three-terminal FeFET structure allows for lossless compression of the stored QUBO matrix, achieving a remarkably 75% chip size saving when solving Max-Cut problems. A multi-epoch simulated annealing (MESA) algorithm is proposed for efficient annealing, achieving up to 27% better solution and ~ 2X speedup than conventional simulated annealing. Experimental validation is performed using the first integrated FeFET chip on 28nm HKMG CMOS technology, indicating great promise of FeFET CiM array in solving general COPs.

Hyperscaling in the Coherent Hyperspin Machine

Classical and quantum systems are used to simulate the Ising Hamiltonian, an essential component in large-scale optimization and machine learning. However, as the system size increases, devices like quantum annealers and coherent Ising machines face an exponential drop in their success rate. Here, we introduce a novel approach involving high-dimensional embeddings of the Ising Hamiltonian and a technique called "dimensional annealing" to counteract the decrease in performance. This approach leads to an exponential improvement in the success rate and other performance metrics, slowing down the decline in performance as the system size grows. A thorough examination of convergence dynamics in high-performance computing validates the new methodology. Additionally, we suggest practical implementations using technologies like coherent Ising machines, all-optical systems, and hybrid digital systems. The proposed hyperscaling heuristics can also be applied to other quantum or classical Ising devices by adjusting parameters such as nonlinear gain, loss, and nonlocal couplings.

Augmenting an electronic Ising machine to effectively solve boolean satisfiability

With the slowdown of improvement in conventional von Neumann systems, increasing attention is paid to novel paradigms such as Ising machines. They have very different approach to solving combinatorial optimization problems. Ising machines have shown great potential in solving binary optimization problems like MaxCut. In this paper, we present an analysis of these systems in boolean satisfiability (SAT) problems. We demonstrate that, in the case of 3-SAT, a basic architecture fails to produce meaningful acceleration, largely due to the relentless progress made in conventional SAT solvers. Nevertheless, careful analysis attributes part of the failure to the lack of two important components: cubic interactions and efficient randomization heuristics. To overcome these limitations, we add proper architectural support for cubic interaction on a state-of-the-art Ising machine. More importantly, we propose a novel semantic-aware annealing schedule that makes the search-space navigation much more efficient than existing annealing heuristics. Using numerical simulations, we show that such an "Augmented" Ising Machine for SAT is projected to outperform state-of-the-art software-based, GPU-based and conventional hardware SAT solvers by orders of magnitude.

Wavelength-division multiplexing optical Ising simulator enabling fully programmable spin couplings and external magnetic fields

Recently various physical systems have been proposed for modeling Ising spin Hamiltonians appealing to solve combinatorial optimization problems with remarkable performance. However, how to implement arbitrary spin-spin interactions is a critical and challenging problem in unconventional Ising machines. Here, we propose a general gauge transformation scheme to enable arbitrary spin-spin interactions and external magnetic fields as well, by decomposing an Ising Hamiltonian into multiple Mattis-type interactions. With this scheme, a wavelength-division multiplexing spatial photonic Ising machine (SPIM) is developed to show the programmable capability of general spin coupling interactions. We exploit the wavelength-division multiplexing SPIM to simulate three spin systems: ±J models, Sherrington-Kirkpatrick models, and only locally connected J1-J2 models and observe the phase transitions. We also demonstrate the ground-state search for solving Max-Cut problem with the wavelength-division multiplexing SPIM. These results promise the realization of ultrafast-speed and high-power efficiency Boltzmann sampling to a generalized large-scale Ising model.

Effective implementation of [Formula: see text]-regularised compressed sensing with chaotic-amplitude-controlled coherent Ising machines

Coherent Ising machine (CIM) is a network of optical parametric oscillators that can solve large-scale combinatorial optimisation problems by finding the ground state of an Ising Hamiltonian. As a practical application of CIM, Aonishi et al., proposed a quantum-classical hybrid system to solve optimisation problems of [Formula: see text]-regularisation-based compressed sensing. In the hybrid system, the CIM was an open-loop system without an amplitude control feedback loop. In this case, the hybrid system is enhanced by using a closed-loop CIM to achieve chaotic behaviour around the target amplitude, which would enable escaping from local minima in the energy landscape. Both artificial and magnetic resonance image data were used for the testing of our proposed closed-loop system. Compared with the open-loop system, the results of this study demonstrate an improved degree of accuracy and a wider range of effectiveness.

Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar

Combinatorial optimization problems are prevalent in various fields, but obtaining exact solutions remains challenging due to the combinatorial explosion with increasing problem size. Special-purpose hardware such as Ising machines, particularly memristor-based analog Ising machines, have emerged as promising solutions. However, existing simulate-annealing-based implementations have not fully exploited the inherent parallelism and analog storage/processing features of memristor crossbar arrays. This work proposes a quantum-inspired parallel annealing method that enables full parallelism and improves solution quality, resulting in significant speed and energy improvement when implemented in analog memristor crossbars. We experimentally solved tasks, including unweighted and weighted Max-Cut and traveling salesman problem, using our integrated memristor chip. The quantum-inspired parallel annealing method implemented in memristor-based hardware has demonstrated significant improvements in time- and energy-efficiency compared to previously reported simulated annealing and Ising machine implemented on other technologies. This is because our approach effectively exploits the natural parallelism, analog conductance states, and all-to-all connection provided by memristor technology, promising its potential for solving complex optimization problems with greater efficiency.

Persistent dynamics in coupled non-degenerate parametric oscillators: pump saturation prevents mode competition

The coherent dynamics in networks of coupled oscillators is of great interest in wave-physics since the coupling produces various dynamical effects, such as coherent energy exchange (beats) between the oscillators. However, it is common wisdom that these coherent dynamics are transients that quickly decay in active oscillators (e.g. lasers) since pump saturation causes mode competition that results, for homogeneous gain, in the prevalence of the single winning mode. We observe that pump saturation in coupled parametric oscillators counter-intuitively encourages the multi-mode dynamics of beating and indefinitely preserves it, despite the existence of mode competition. We explore in detail the coherent dynamics of a pair of coupled parametric oscillators with a shared pump and arbitrary coupling in a radio frequency (RF) experiment, as well as in simulation. Specifically, we realize two parametric oscillators as different frequency-modes of a single RF cavity and couple them arbitrarily using a digital high-bandwidth FPGA. We observe persistent coherent beats that are maintained at any pump level, even high above the threshold. The simulation highlights how the interplay of pump depletion between the two oscillators prevents them from synchronizing, even when the oscillation is deeply saturated.

Highly reconfigurable oscillator-based Ising Machine through quasiperiodic modulation of coupling strength

Ising Machines (IMs) have the potential to outperform conventional Von-Neuman architectures in notoriously difficult optimization problems. Various IM implementations have been proposed based on quantum, optical, digital and analog CMOS, as well as emerging technologies. Networks of coupled electronic oscillators have recently been shown to exhibit characteristics required for implementing IMs. However, for this approach to successfully solve complex optimization problems, a highly reconfigurable implementation is needed. In this work, the possibility of implementing highly reconfigurable oscillator-based IMs is explored. An implementation based on quasiperiodically modulated coupling strength through a common medium is proposed and its potential is demonstrated through numerical simulations. Moreover, a proof-of-concept implementation based on CMOS coupled ring oscillators is proposed and its functionality is demonstrated. Simulation results show that our proposed architecture can consistently find the Max-Cut solution and demonstrate the potential to greatly simplify the physical implementation of highly reconfigurable oscillator-based IMs.

Speed-up coherent Ising machine with a spiking neural network

Coherent Ising machine (CIM) is a hardware solver that simulates the Ising model and finds optimal solutions to combinatorial optimization problems. However, for practical tasks, the computational process may be trapped in local minima, which is a key challenge for CIM. In this work, we design a CIM structure with a spiking neural network by adding dissipative pulses, which are anti-symmetrically coupled to the degenerate optical parametric oscillator pulses in CIM with a measurement feedback system. We find that the unstable oscillatory region of the spiking neural network could assist the CIM to escape from the trapped local minima. Moreover, we show that the machine has a different search mechanism than CIM, which can achieve a higher solution success probability and speed-up effect.

CMOS-compatible ising machines built using bistable latches coupled through ferroelectric transistor arrays

Realizing compact and scalable Ising machines that are compatible with CMOS-process technology is crucial to the effectiveness and practicality of using such hardware platforms for accelerating computationally intractable problems. Besides the need for realizing compact Ising spins, the implementation of the coupling network, which describes the spin interaction, is also a potential bottleneck in the scalability of such platforms. Therefore, in this work, we propose an Ising machine platform that exploits the novel behavior of compact bi-stable CMOS-latches (cross-coupled inverters) as classical Ising spins interacting through highly scalable and CMOS-process compatible ferroelectric-HfO₂-based Ferroelectric FETs (FeFETs) which act as coupling elements. We experimentally demonstrate the prototype building blocks of this system, and evaluate the scaling behavior of the system using simulations. Our work not only provides a pathway to realizing CMOS-compatible designs but also to overcoming their scaling challenges.

Optimization with photonic wave-based annealers

Many NP-hard combinatorial optimization (CO) problems can be cast as a quadratic unconstrained binary optimization model, which maps naturally to an Ising model. The final spin configuration in the Ising model can adiabatically arrive at a solution to a Hamiltonian, given a known set of interactions between spins. We enhance two photonic Ising machines (PIMs) and compare their performance against classical (Gurobi) and quantum (D-Wave) solvers. The temporal multiplexed coherent Ising machine (TMCIM) uses the bistable response of an electro-optic modulator to mimic the spin up and down states. We compare TMCIM performance on Max-cut problems. A spatial photonic Ising machine (SPIM) convolves the wavefront of a coherent laser beam with the pixel distribution of a spatial light modulator to adiabatically achieve a minimum energy configuration, and solve a number partitioning problem (NPP). Our computational results on Max-cut indicate that classical solvers are still a better choice, while our NPP results show that SPIM is better as the problem size increases. In both cases, connectivity in Ising hardware is crucial for performance. Our results also highlight the importance of better understanding which CO problems are most likely to benefit from which type of PIM. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'.

Quantum Annealing in the NISQ Era: Railway Conflict Management

We are in the noisy intermediate-scale quantum (NISQ) devices' era, in which quantum hardware has become available for application in real-world problems. However, demonstrations of the usefulness of such NISQ devices are still rare. In this work, we consider a practical railway dispatching problem: delay and conflict management on single-track railway lines. We examine the train dispatching consequences of the arrival of an already delayed train to a given network segment. This problem is computationally hard and needs to be solved almost in real time. We introduce a quadratic unconstrained binary optimization (QUBO) model of this problem, which is compatible with the emerging quantum annealing technology. The model's instances can be executed on present-day quantum annealers. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers. As a reference, we also provide solutions calculated with classical methods, including the conventional solution of a linear integer version of the model as well as the solution of the QUBO model using a tensor network-based algorithm. Our preliminary results illustrate the degree of difficulty of real-life railway instances for the current quantum annealing technology. Moreover, our analysis shows that the new generation of quantum annealers (the advantage system) does not perform well on those instances, either.

Multidimensional hyperspin machine

From condensed matter to quantum chromodynamics, multidimensional spins are a fundamental paradigm, with a pivotal role in combinatorial optimization and machine learning. Machines formed by coupled parametric oscillators can simulate spin models, but only for Ising or low-dimensional spins. Currently, machines implementing arbitrary dimensions remain a challenge. Here, we introduce and validate a hyperspin machine to simulate multidimensional continuous spin models. We realize high-dimensional spins by pumping groups of parametric oscillators, and show that the hyperspin machine finds to a very good approximation the ground state of complex graphs. The hyperspin machine can interpolate between different dimensions by tuning the coupling topology, a strategy that we call "dimensional annealing". When interpolating between the XY and the Ising model, the dimensional annealing substantially increases the success probability compared to conventional Ising simulators. Hyperspin machines are a new computational model for combinatorial optimization. They can be realized by off-the-shelf hardware for ultrafast, large-scale applications in classical and quantum computing, condensed-matter physics, and fundamental studies.

Large-scale coherent Ising machine based on optoelectronic parametric oscillator

Ising machines based on analog systems have the potential to accelerate the solution of ubiquitous combinatorial optimization problems. Although some artificial spins to support large-scale Ising machines have been reported, e.g., superconducting qubits in quantum annealers and short optical pulses in coherent Ising machines, the spin stability is fragile due to the ultra-low equivalent temperature or optical phase sensitivity. In this paper, we propose to use short microwave pulses generated from an optoelectronic parametric oscillator as the spins to implement a large-scale Ising machine with high stability. The proposed machine supports 25,600 spins and can operate continuously and stably for hours. Moreover, the proposed Ising machine is highly compatible with high-speed electronic devices for programmability, paving a low-cost, accurate, and easy-to-implement way toward solving real-world optimization problems.

A tree search algorithm towards solving Ising formulated combinatorial optimization problems

Simulated annealing (SA) attracts more attention among classical heuristic algorithms because many combinatorial optimization problems can be easily recast as the ground state search problem of the Ising Hamiltonian. However, for practical implementation, the annealing process cannot be arbitrarily slow and hence, it may deviate from the expected stationary Boltzmann distribution and become trapped in a local energy minimum. To overcome this problem, this paper proposes a heuristic search algorithm by expanding search space from a Markov chain to a recursive depth limited tree based on SA, where the parent and child nodes represent the current and future spin states. At each iteration, the algorithm selects the best near-optimal solution within the feasible search space by exploring along the tree in the sense of “look ahead”. Furthermore, motivated by the coherent Ising machine (CIM), the discrete representation of spin states is relaxed to a continuous representation with a regularization term, which enables the use of the reduced dynamics of the oscillators to explore the surrounding neighborhood of the selected tree nodes. We tested our algorithm on a representative NP-hard problem (MAX-CUT) to illustrate the effectiveness of the proposed algorithm compared to semi-definite programming (SDP), SA, and simulated CIM. Our results show that with the primal heuristics SA and CIM, our high-level tree search strategy is able to provide solutions within fewer epochs for Ising formulated combinatorial optimization problems.

Mean field approximation for solving QUBO problems

The Quadratic Unconstrained Binary Optimization (QUBO) problem is NP-hard. Some exact methods like the Branch-and-Bound algorithm are suitable for small problems. Some approximations like stochastic simulated annealing for discrete variables or mean-field annealing for continuous variables exist for larger ones, and quantum computers based on the quantum adiabatic annealing principle have also been developed. Here we show that the mean-field approximation of the quantum adiabatic annealing leads to equations similar to those of thermal mean-field annealing. However, a new type of sigmoid function replaces the thermal one. The new mean-field quantum adiabatic annealing can replicate the best-known cut values on some of the popular benchmark Maximum Cut problems.

Solving large break minimization problems in a mirrored double round-robin tournament using quantum annealing

Quantum annealing has gained considerable attention because it can be applied to combinatorial optimization problems, which have numerous applications in logistics, scheduling, and finance. In recent years, with the technical development of quantum annealers, research on solving practical combinatorial optimization problems using them has accelerated. However, researchers struggle to find practical combinatorial optimization problems, for which quantum annealers outperform mathematical optimization solvers. Moreover, there are only a few studies that compare the performance of quantum annealers with the state-of-the-art solvers, such as Gurobi and CPLEX. This study determines that quantum annealing demonstrates better performance than the solvers in that the solvers take longer to reach the objective function value of the solution obtained by the quantum annealers for the break minimization problem in a mirrored double round-robin tournament. We also explain the desirable performance of quantum annealing for the sparse interaction between variables and a problem without constraints. In this process, we demonstrate that this problem can be expressed as a 4-regular graph. Through computational experiments, we solve this problem using our quantum annealing approach and two-integer programming approaches, which were performed using the latest quantum annealer D-Wave Advantage, and Gurobi, respectively. Further, we compare the quality of the solutions and the computational time. Quantum annealing was able to determine the exact solution in 0.05 seconds for problems with 20 teams, which is a practical size. In the case of 36 teams, it took 84.8 s for the integer programming method to reach the objective function value, which was obtained by the quantum annealer in 0.05 s. These results not only present the break minimization problem in a mirrored double round-robin tournament as an example of applying quantum annealing to practical optimization problems, but also contribute to find problems that can be effectively solved by quantum annealing.

Parallel quantum annealing

Quantum annealers of D-Wave Systems, Inc., offer an efficient way to compute high quality solutions of NP-hard problems. This is done by mapping a problem onto the physical qubits of the quantum chip, from which a solution is obtained after quantum annealing. However, since the connectivity of the physical qubits on the chip is limited, a minor embedding of the problem structure onto the chip is required. In this process, and especially for smaller problems, many qubits will stay unused. We propose a novel method, called parallel quantum annealing, to make better use of available qubits, wherein either the same or several independent problems are solved in the same annealing cycle of a quantum annealer, assuming enough physical qubits are available to embed more than one problem. Although the individual solution quality may be slightly decreased when solving several problems in parallel (as opposed to solving each problem separately), we demonstrate that our method may give dramatic speed-ups in terms of the Time-To-Solution (TTS) metric for solving instances of the Maximum Clique problem when compared to solving each problem sequentially on the quantum annealer. Additionally, we show that solving a single Maximum Clique problem using parallel quantum annealing reduces the TTS significantly.

Distance-based clustering using QUBO formulations

In computer science, clustering is a technique for grouping data. Ising machines can solve distance-based clustering problems described by quadratic unconstrained binary optimization (QUBO) formulations. A typical simple method using an Ising machine makes each cluster size equal and is not suitable for clustering unevenly distributed data. We propose a new clustering method that provides better performance than the simple method, especially for unevenly distributed data. The proposed method is a hybrid algorithm including an iterative process that comprises solving a discrete optimization problem with an Ising machine and calculating parameters with a general-purpose computer. To minimize the communication overhead between the Ising machine and the general-purpose computer, we employed a low-latency Ising machine implementing the simulated bifurcation algorithm with a field-programmable gate array attached to a local server. The proposed method results in clustering 200 unevenly distributed data points with a clustering score 18% higher than that of the simple method. The discrete optimization with 2000 variables is performed 100 times per iteration, and the overhead time is reduced to approximately 20% of the total execution time. These results suggest that hybrid algorithms using Ising machines can efficiently solve practical optimization problems.

Phase-space simulations of feedback coherent Ising machines

A new, to the best of our knowledge, technique is demonstrated for carrying out exact positive-P phase-space simulations of the coherent Ising machine quantum computer. By suitable design of the coupling matrix, general hard optimization problems can be solved. Here, computational quantum simulations of a feedback type of photonic parametric network are carried out, which is the implementation of the coherent Ising machine. Results for success rates are obtained using this scalable phase-space algorithm for quantum simulations of quantum feedback devices.

100,000-spin coherent Ising machine

Computers based on physical systems are increasingly anticipated to overcome the impending limitations on digital computer performance. One such computer is a coherent Ising machine (CIM) for solving combinatorial optimization problems. Here, we report a CIM with 100,512 degenerate optical parametric oscillator pulses working as the Ising spins. We show that the CIM delivers fine solutions to maximum cut problems of 100,000-node graphs drastically faster than standard simulated annealing. Moreover, the CIM, when operated near the phase transition point, provides some extremely good solutions and a very broad distribution. This characteristic will be useful for applications that require fast random sampling such as machine learning.

Accuracy-enhanced coherent Ising machine using the quantum adiabatic theorem

The coherent Ising machine (CIM) implemented by degenerate optical parametric oscillator (DOPO) networks is a novel optical platform to accelerate computation of hard combinatorial optimization problems. Nevertheless, with the increase of the problem size, the probability of the machine being trapped by local minima increases exponentially. According to the quantum adiabatic theorem, a physical system will remain in its instantaneous ground state if the time-dependent Hamiltonian varies slowly enough. Here, we propose a method to help the machine partially avoid getting stuck in local minima by introducing quantum adiabatic evolution to the ground-state-search process of the CIM, which we call A-CIM. Numerical simulation results demonstrate that A-CIM can obtain improved solution accuracy in solving MAXCUT problems of vertices ranging from 10 to 2000 than CIM. The proposed machine that is based on quantum adiabatic theorem is expected to solve optimization problems more correctly.

Entanglement and Photon Anti-Bunching in Coupled Non-Degenerate Parametric Oscillators

We analytically and numerically show that the Hillery-Zubairy's entanglement criterion is satisfied both below and above the threshold of coupled non-degenerate optical parametric oscillators (NOPOs) with strong nonlinear gain saturation and dissipative linear coupling. We investigated two cases: for large pump mode dissipation, below-threshold entanglement is possible only when the parametric interaction has an enough detuning among the signal, idler, and pump photon modes. On the other hand, for a large dissipative coupling, below-threshold entanglement is possible even when there is no detuning in the parametric interaction. In both cases, a non-Gaussian state entanglement criterion is satisfied even at the threshold. Recent progress in nano-photonic devices might make it possible to experimentally demonstrate this phase transition in a coherent XY machine with quantum correlations.

Collective and synchronous dynamics of photonic spiking neurons

Nonlinear dynamics of spiking neural networks have recently attracted much interest as an approach to understand possible information processing in the brain and apply it to artificial intelligence. Since information can be processed by collective spiking dynamics of neurons, the fine control of spiking dynamics is desirable for neuromorphic devices. Here we show that photonic spiking neurons implemented with paired nonlinear optical oscillators can be controlled to generate two modes of bio-realistic spiking dynamics by changing optical-pump amplitude. When the photonic neurons are coupled in a network, the interaction between them induces an effective change in the pump amplitude depending on the order parameter that characterizes synchronization. The experimental results show that the effective change causes spontaneous modification of the spiking modes and firing rates of clustered neurons, and such collective dynamics can be utilized to realize efficient heuristics for solving NP-hard combinatorial optimization problems.

Can Nonlinear Parametric Oscillators Solve Random Ising Models?

We study large networks of parametric oscillators as heuristic solvers of random Ising models. In these networks, known as coherent Ising machines, the model to be solved is encoded in the coupling between the oscillators, and a solution is offered by the steady state of the network. This approach relies on the assumption that mode competition steers the network to the ground-state solution of the Ising model. By considering a broad family of frustrated Ising models, we show that the most efficient mode does not correspond generically to the ground state of the Ising model. We infer that networks of parametric oscillators close to threshold are intrinsically not Ising solvers. Nevertheless, the network can find the correct solution if the oscillators are driven sufficiently above threshold, in a regime where nonlinearities play a predominant role. We find that for all probed instances of the model, the network converges to the ground state of the Ising model with a finite probability.

Traffic signal optimization on a square lattice with quantum annealing

The spread of intelligent transportation systems in urban cities has caused heavy computational loads, requiring a novel architecture for managing large-scale traffic. In this study, we develop a method for globally controlling traffic signals arranged on a square lattice by means of a quantum annealing machine, namely the D-Wave quantum annealer. We first formulate a signal optimization problem that minimizes the imbalance of traffic flows in two orthogonal directions. Then we reformulate this problem as an Ising Hamiltonian, which is compatible with quantum annealers. The new control method is compared with a conventional local control method for a large 50-by-50 city, and the results exhibit the superiority of our global control method in suppressing traffic imbalance over wide parameter ranges. Furthermore, the solutions to the global control method obtained with the quantum annealing machine are better than those obtained with conventional simulated annealing. In addition, we prove analytically that the local and the global control methods converge at the limit where cars have equal probabilities for turning and going straight. These results are verified with numerical experiments.

Discrete Polynomial Optimization with Coherent Networks of Condensates and Complex Coupling Switching

Gain-dissipative platforms consisting of lasers, optical parametric oscillators and nonequilibrium condensates operating at the condensation or coherence threshold have been recently proposed as efficient analog simulators of the two-local spin Hamiltonians with continuous or discrete degrees of freedom. We show that nonequilibrium condensates above the threshold arranged in an interacting network may realize k-local Hamiltonians with k>2 and lead to nontrivial phase configurations. Similarly, many gain-dissipative systems that can be manipulated by optical means can bring about the ground state of the k-local Hamiltonians and solve higher-order binary optimization problems. We show how to facilitate the search for the global solution by invoking complex couplings in the system and demonstrate the efficiency of the method on the sets of complex problems. This approach offers a highly flexible new kind of computation based on gain-dissipative simulators with complex coupling switching.

Spectral phase transitions in optical parametric oscillators

Driven nonlinear resonators provide a fertile ground for phenomena related to phase transitions far from equilibrium, which can open opportunities unattainable in their linear counterparts. Here, we show that optical parametric oscillators (OPOs) can undergo second-order phase transitions in the spectral domain between degenerate and non-degenerate regimes. This abrupt change in the spectral response follows a square-root dependence around the critical point, exhibiting high sensitivity to parameter variation akin to systems around an exceptional point. We experimentally demonstrate such a phase transition in a quadratic OPO. We show that the divergent susceptibility of the critical point is accompanied by spontaneous symmetry breaking and distinct phase noise properties in the two regimes, indicating the importance of a beyond nonlinear bifurcation interpretation. We also predict the occurrence of first-order spectral phase transitions in coupled OPOs. Our results on non-equilibrium spectral behaviors can be utilized for enhanced sensing, advanced computing, and quantum information processing.

High-performance combinatorial optimization based on classical mechanics

Quickly obtaining optimal solutions of combinatorial optimization problems has tremendous value but is extremely difficult. Thus, various kinds of machines specially designed for combinatorial optimization have recently been proposed and developed. Toward the realization of higher-performance machines, here, we propose an algorithm based on classical mechanics, which is obtained by modifying a previously proposed algorithm called simulated bifurcation. Our proposed algorithm allows us to achieve not only high speed by parallel computing but also high solution accuracy for problems with up to one million binary variables. Benchmarking shows that our machine based on the algorithm achieves high performance compared to recently developed machines, including a quantum annealer using a superconducting circuit, a coherent Ising machine using a laser, and digital processors based on various algorithms. Thus, high-performance combinatorial optimization is realized by massively parallel implementations of the proposed algorithm based on classical mechanics.

Continuous and long-term stabilization of degenerate optical parametric oscillators for large-scale optical hybrid computers

The minimum requirements for an optical reservoir computer, a recent paradigm for computation using simple algorithms, are nonlinearity and internal interactions. A promising optical system satisfying these requirements is a platform based on coupled degenerate optical parametric oscillators (DOPOs) in a fiber ring cavity. We can expect advantages using DOPOs for reservoir computing with respect to scalability and reduction of excess noise; however, the continuous stabilization required for reservoir computing has not yet been demonstrated. Here, we report the continuous and long-term stabilization of an optical system by introducing periodical phase modulation patterns for DOPOs and a local oscillator. We observed that the Allan variance of the optical phase up to 100 ms was suppressed and that the homodyne measurement signal had a relative standard deviation of 1.4% over 62,500 round trips. The proposed methods represent important technical bases for realizing stable computation on large-scale optical hybrid computers.

Amoeba-inspired analog electronic computing system integrating resistance crossbar for solving the travelling salesman problem

Combinatorial optimization to search for the best solution across a vast number of legal candidates requires the development of a domain-specific computing architecture that can exploit the computational power of physical processes, as conventional general-purpose computers are not powerful enough. Recently, Ising machines that execute quantum annealing or related mechanisms for rapid search have attracted attention. These machines, however, are hard to map application problems into their architecture, and often converge even at an illegal candidate. Here, we demonstrate an analogue electronic computing system for solving the travelling salesman problem, which mimics efficient foraging behaviour of an amoeboid organism by the spontaneous dynamics of an electric current in its core and enables a high problem-mapping flexibility and resilience using a resistance crossbar circuit. The system has high application potential, as it can determine a high-quality legal solution in a time that grows proportionally to the problem size without suffering from the weaknesses of Ising machines.

Third-order nanocircuit elements for neuromorphic engineering

Current hardware approaches to biomimetic or neuromorphic artificial intelligence rely on elaborate transistor circuits to simulate biological functions. However, these can instead be more faithfully emulated by higher-order circuit elements that naturally express neuromorphic nonlinear dynamics^1-4. Generating neuromorphic action potentials in a circuit element theoretically requires a minimum of third-order complexity (for example, three dynamical electrophysical processes)⁵, but there have been few examples of second-order neuromorphic elements, and no previous demonstration of any isolated third-order element^6-8. Using both experiments and modelling, here we show how multiple electrophysical processes-including Mott transition dynamics-form a nanoscale third-order circuit element. We demonstrate simple transistorless networks of third-order elements that perform Boolean operations and find analogue solutions to a computationally hard graph-partitioning problem. This work paves a way towards very compact and densely functional neuromorphic computing primitives, and energy-efficient validation of neuroscientific models.

Demonstration of chip-based coupled degenerate optical parametric oscillators for realizing a nanophotonic spin-glass

The need for solving optimization problems is prevalent in various physical applications, including neuroscience, network design, biological systems, socio-economics, and chemical reactions. Many of these are classified as non-deterministic polynomial-time hard and thus become intractable to solve as the system scales to a large number of elements. Recent research advances in photonics have sparked interest in using a network of coupled degenerate optical parametric oscillators (DOPOs) to effectively find the ground state of the Ising Hamiltonian, which can be used to solve other combinatorial optimization problems through polynomial-time mapping. Here, using the nanophotonic silicon-nitride platform, we demonstrate a spatial-multiplexed DOPO system using continuous-wave pumping. We experimentally demonstrate the generation and coupling of two microresonator-based DOPOs on a single chip. Through a reconfigurable phase link, we achieve both in-phase and out-of-phase operation, which can be deterministically achieved at a fast regeneration speed of 400 kHz with a large phase tolerance.

Observation of binary phase states of time-multiplexed degenerate optical parametric oscillator pulses generated using a nonlinear fiber Sagnac loop

We generated time-multiplexed degenerate optical parametric oscillator (DOPO) pulses using a nonlinear fiber Sagnac loop as a phase-sensitive amplifier (PSA), where the pump and amplified light in pump-signal-idler degenerate four-wave mixing can be spatially separated. By placing the PSA in a fiber cavity, we successfully generated more than 5000 time-multiplexed DOPO pulses. We confirmed the bifurcation of pulse phases to 0 or π relative to the pump phase, which makes them useful for representing Ising spins in an Ising model solver based on coherent optical oscillator networks. We also confirmed inherent randomness of the DOPO phases using the National Institute of Standards and Technology random number test.

Parallel in time dynamics with quantum annealers

Recent years have witnessed an unprecedented increase in experiments and hybrid simulations involving quantum computers. In particular, quantum annealers. There exist a plethora of algorithms promising to outperform classical computers in the near-term future. Here, we propose a parallel in time approach to simulate dynamical systems designed to be executed already on present-day quantum annealers. In essence, purely classical methods for solving dynamics systems are serial. Therefore, their parallelization is substantially limited. In the presented approach, however, the time evolution is rephrased as a ground-state search of a classical Ising model. Such a problem is solved intrinsically in parallel by quantum computers. The main idea is exemplified by simulating the Rabi oscillations generated by a two-level quantum system (i.e. qubit) experimentally.

Computational hardness of spin-glass problems with tile-planted solutions

We investigate the computational hardness of spin-glass instances on a square lattice, generated via a recently introduced tunable and scalable approach for planting solutions. The method relies on partitioning the problem graph into edge-disjoint subgraphs and planting frustrated, elementary subproblems that share a common local ground state, which guarantees that the ground state of the entire problem is known a priori. Using population annealing Monte Carlo, we compare the typical hardness of problem classes over a large region of the multidimensional tuning parameter space. Our results show that the problems have a wide range of tunable hardness. Moreover, we observe multiple transitions in the hardness phase space, which we further corroborate using simulated annealing and simulated quantum annealing. By investigating thermodynamic properties of these planted systems, we demonstrate that the harder samples undergo magnetic ordering transitions which are also ultimately responsible for the observed hardness transitions on changing the sample composition.

Model Predictive Control for Finite Input Systems using the D-Wave Quantum Annealer

The D-Wave quantum annealer has emerged as a novel computational architecture that is attracting significant interest, but there have been only a few practical algorithms exploiting the power of quantum annealers. Here we present a model predictive control (MPC) algorithm using a quantum annealer for a system allowing a finite number of input values. Such an MPC problem is classified as a non-deterministic polynomial-time-hard combinatorial problem, and thus real-time sequential optimization is difficult to obtain with conventional computational systems. We circumvent this difficulty by converting the original MPC problem into a quadratic unconstrained binary optimization problem, which is then solved by the D-Wave quantum annealer. Two practical applications, namely stabilization of a spring-mass-damper system and dynamic audio quantization, are demonstrated. For both, the D-Wave method exhibits better performance than the classical simulated annealing method. Our results suggest new applications of quantum annealers in the direction of dynamic control problems.

Heuristic recurrent algorithms for photonic Ising machines

The inability of conventional electronic architectures to efficiently solve large combinatorial problems motivates the development of novel computational hardware. There has been much effort toward developing application-specific hardware across many different fields of engineering, such as integrated circuits, memristors, and photonics. However, unleashing the potential of such architectures requires the development of algorithms which optimally exploit their fundamental properties. Here, we present the Photonic Recurrent Ising Sampler (PRIS), a heuristic method tailored for parallel architectures allowing fast and efficient sampling from distributions of arbitrary Ising problems. Since the PRIS relies on vector-to-fixed matrix multiplications, we suggest the implementation of the PRIS in photonic parallel networks, which realize these operations at an unprecedented speed. The PRIS provides sample solutions to the ground state of Ising models, by converging in probability to their associated Gibbs distribution. The PRIS also relies on intrinsic dynamic noise and eigenvalue dropout to find ground states more efficiently. Our work suggests speedups in heuristic methods via photonic implementations of the PRIS.

Analog Coupled Oscillator Based Weighted Ising Machine

We report on an analog computing system with coupled non-linear oscillators which is capable of solving complex combinatorial optimization problems using the weighted Ising model. The circuit is composed of a fully-connected 4-node LC oscillator network with low-cost electronic components and compatible with traditional integrated circuit technologies. We present the theoretical modeling, experimental characterization, and statistical analysis our system, demonstrating single-run ground state accuracies of 98% on randomized MAX-CUT problem sets with binary weights and 84% with 5-bit weight resolutions. Solutions are obtained within 5 oscillator cycles, and the time-to-solution has been demonstrated to scale directly with oscillator frequency. We present scaling analysis which suggests that large coupled oscillator networks may be used to solve computationally intensive problems faster and more efficiently than conventional algorithms. The proof-of-concept system presented here provides the foundation for realizing such larger scale systems using existing hardware technologies and could pave the way towards an entirely novel computing paradigm.

Persistent Coherent Beating in Coupled Parametric Oscillators

Coupled parametric oscillators were recently employed as simulators of artificial Ising networks, with the potential to solve computationally hard minimization problems. We demonstrate a new dynamical regime within the simplest network-two coupled parametric oscillators, where the oscillators never reach a steady state, but show persistent, full-scale, coherent beats, whose frequency reflects the coupling properties and strength. We present a detailed theoretical and experimental study and show that this new dynamical regime appears over a wide range of parameters near the oscillation threshold and depends on the nature of the coupling (dissipative or energy preserving). Thus, a system of coupled parametric oscillators transcends the Ising description and manifests unique coherent dynamics, which may have important implications for coherent computation machines.

A poor man's coherent Ising machine based on opto-electronic feedback systems for solving optimization problems

Coherent Ising machines (CIMs) constitute a promising approach to solve computationally hard optimization problems by mapping them to ground state searches of the Ising model and implementing them with optical artificial spin-networks. However, while CIMs promise speed-ups over conventional digital computers, they are still challenging to build and operate. Here, we propose and test a concept for a fully programmable CIM, which is based on opto-electronic oscillators subjected to self-feedback. Contrary to current CIM designs, the artificial spins are generated in a feedback induced bifurcation and encoded in the intensity of coherent states. This removes the necessity for nonlinear optical processes or large external cavities and offers significant advantages regarding stability, size and cost. We demonstrate a compact setup for solving MAXCUT optimization problems on regular and frustrated graphs with 100 spins and can report similar or better performance compared to CIMs based on degenerate optical parametric oscillators.