Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACCELERATED OPTIMIZATION USING COHERENT ISING MACHINES

Kai Yan

Published Sep 27, 2013• 0 citations
Publisher

Abstract

Quantum computation takes advantage of quantum physics such as quantum parallelism and quantum interference, to perform calculations in an exponentially parallel way.Quantum computation realizes an exponential speed up over classical computers in solving problems such as factorization.However, the application is severely limited due to the computation model using unitary transformation, and to implement a scalable system remains a challenging task.A new approach that benefits from a coherent quantum system to speed up the search of ground state of Ising model is proposed.The coherent Ising machine is based on one master laser and multiple mutually injection-locked slave lasers, where the master laser locks the optical frequency and phase of all slave lasers to keep the quantum coherence all over the system.The Ising model is implemented by coherent feedback network using optical interference circuits.The ground state of the Ising model corresponds to the polarization configuration with the minimal gain and loss, which emerges spontaneously through the natural mode competition induced by crossgain saturation.The open dissipative system is more robust against noise thus make it more practical to be implemented.A NP-complete problem can be reduced as the Ising model, which provides the proposed system a wider range of applications iv Abstract v compared to the unitary transformation system.In this thesis we introduce the coherent Ising machine using laser network.An efficient mapping of 3 Satisfiability problem (3SAT) to Ising model is proposed.The mapping method reduces a 3SAT problem with N variables to an Ising model with N spins, which can be implemented using a system with N slave lasers.We also propose a Binary search method to determine the optimal pumping power which provides the highest probability of finding the ground state in O(logM ) steps for a 3SAT problem with M clauses.Simulations using different sized 3SAT problems are investigated and from which we find the computation time scaling with input problem size is reduced to O(N 3 ) with the optimal pumping rate.

DOI
10.15083/00006443

Related papers

A coherent Ising machine for 2000-node optimization problems

Takahiro Inagaki, Yoshitaka Haribara, Koji Igarashi +14 more

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.

Science•Oct 21, 2016•835 citations

A single shot coherent Ising machine based on a network of injection-locked multicore fiber lasers

Masoud Babaeian, Dan Trung Nguyen, Veysi Demir +6 more

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.

Nature Communications•Aug 6, 2019•100 citations

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

Kenta Takata, Alireza Marandi, Ryan Hamerly +6 more

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.

arXiv:1605.03847•Scientific Reports•Sep 23, 2016•87 citations

Quest for quantum advantage: Monte Carlo wave-function simulations of the CIM

Manushan Thenabadu, Run Yan Teh, Jia Wang +3 more

Abstract The coherent Ising machine (CIM) is a quantum network of optical parametric oscillators intended to find ground states of the Ising model. This is an NP-hard problem, related to several important minimization problems, including the max-cut graph problem. In order to enhance its potential performance, we analyze the coherent coupling strategy for the CIM in a highly quantum regime. To explore this limit, without assuming Gaussianity, we employ accurate numerical simulations. Due to the inherent complexity of the system, the maximum network size is limited. While master equation methods can be used, their scalability diminishes rapidly for larger systems. Instead, we use Monte Carlo wave-function methods, which scale as the wave-function dimension, and use large numbers of samples. These simulations involve Hilbert spaces exceeding 10 7 dimensions. To evaluate success probabilities, we use quadrature probabilities. We demonstrate the potential for quantum computational advantage by reducing the time required to reach maximum success probability in a low-dissipation regime enabled by initial quantum superpositions and entanglement. Furthermore, we demonstrate that tailored time-dependent couplings can amplify these quantum effects. Comparisons with classical CIM models give evidence consistent with a quantum escape mechanism, possibly involving tunneling effects in this strong coupling limit, that can overcome trapping in false minima. This can greatly increase success rates, indicating a potential for quantum advantage. Finally, we perform a coherence analysis based on the state purity to examine the role of quantum coherence in CIM performance and to determine how state purity correlates with improved optimization outcomes.

arXiv:2501.02681•Quantum Science and Technology•Jul 15, 2026•1 citation

Frustration Elimination and Excited State Search in Coherent Ising Machines

Zheng-Yang Zhou, Clemens Gneiting, J. Q. You +1 more

Frustration, that is, the impossibility of satisfying the energetic preferences between all spin pairs simultaneously, underlies the complexity of many fundamental properties in spin systems, including the computational difficulty in determining their ground states. Coherent Ising machines (CIMs) have been proposed as a promising analog computational approach to efficiently find different degenerate ground states of large and complex Ising models. However, CIMs also face challenges in solving frustrated Ising models: frustration not only reduces the probability of finding good solutions, but it also prohibits the leveraging of quantum effects in doing so. To circumvent these detrimental effects of frustration, we show how frustrated Ising models can be mapped to frustration-free CIM configurations by including ancillary modes and modifying the coupling protocol used in current CIM designs. Such frustration elimination may empower current CIMs to benefit from quantum effects in dealing with frustrated Ising models. In addition, these ancillary modes can also enable error detection and searching for excited states.

arXiv:2402.15090•Physical Review Letters•Mar 5, 2025•8 citations

Accuracy-enhanced coherent Ising machine using the quantum adiabatic theorem

Lin Li, Hongjun Liu, Nan Huang +1 more

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.

Optics Express•May 17, 2021•9 citations
Quantum computation takes advantage of quantum physics such as quantum parallelism and quantum interference, to perform calculations in an exponentially parallel way.Quantum computation realizes an exponential speed up over classical computers in solving problems such as factorization.However, the application is severely limited due to the computation model using unitary transformation, and to implement a scalable system remains a challenging task.A new approach that benefits from a coherent quantum system to speed up the search of ground state of Ising model is proposed.The coherent Ising machine is based on one master laser and multiple mutually injection-locked slave lasers, where the master laser locks the optical frequency and phase of all slave lasers to keep the quantum coherence all over the system.The Ising model is implemented by coherent feedback network using optical interference circuits.The ground state of the Ising model corresponds to the polarization configuration with the minimal gain and loss, which emerges spontaneously through the natural mode competition induced by crossgain saturation.The open dissipative system is more robust against noise thus make it more practical to be implemented.A NP-complete problem can be reduced as the Ising model, which provides the proposed system a wider range of applications iv Abstract v compared to the unitary transformation system.In this thesis we introduce the coherent Ising machine using laser network.An efficient mapping of 3 Satisfiability problem (3SAT) to Ising model is proposed.The mapping method reduces a 3SAT problem with N variables to an Ising model with N spins, which can be implemented using a system with N slave lasers.We also propose a Binary search method to determine the optimal pumping power which provides the highest probability of finding the ground state in O(logM ) steps for a 3SAT problem with M clauses.Simulations using different sized 3SAT problems are investigated and from which we find the computation time scaling with input problem size is reduced to O(N 3 ) with the optimal pumping rate.
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.
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.
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.
Abstract The coherent Ising machine (CIM) is a quantum network of optical parametric oscillators intended to find ground states of the Ising model. This is an NP-hard problem, related to several important minimization problems, including the max-cut graph problem. In order to enhance its potential performance, we analyze the coherent coupling strategy for the CIM in a highly quantum regime. To explore this limit, without assuming Gaussianity, we employ accurate numerical simulations. Due to the inherent complexity of the system, the maximum network size is limited. While master equation methods can be used, their scalability diminishes rapidly for larger systems. Instead, we use Monte Carlo wave-function methods, which scale as the wave-function dimension, and use large numbers of samples. These simulations involve Hilbert spaces exceeding 10 7 dimensions. To evaluate success probabilities, we use quadrature probabilities. We demonstrate the potential for quantum computational advantage by reducing the time required to reach maximum success probability in a low-dissipation regime enabled by initial quantum superpositions and entanglement. Furthermore, we demonstrate that tailored time-dependent couplings can amplify these quantum effects. Comparisons with classical CIM models give evidence consistent with a quantum escape mechanism, possibly involving tunneling effects in this strong coupling limit, that can overcome trapping in false minima. This can greatly increase success rates, indicating a potential for quantum advantage. Finally, we perform a coherence analysis based on the state purity to examine the role of quantum coherence in CIM performance and to determine how state purity correlates with improved optimization outcomes.
Frustration, that is, the impossibility of satisfying the energetic preferences between all spin pairs simultaneously, underlies the complexity of many fundamental properties in spin systems, including the computational difficulty in determining their ground states. Coherent Ising machines (CIMs) have been proposed as a promising analog computational approach to efficiently find different degenerate ground states of large and complex Ising models. However, CIMs also face challenges in solving frustrated Ising models: frustration not only reduces the probability of finding good solutions, but it also prohibits the leveraging of quantum effects in doing so. To circumvent these detrimental effects of frustration, we show how frustrated Ising models can be mapped to frustration-free CIM configurations by including ancillary modes and modifying the coupling protocol used in current CIM designs. Such frustration elimination may empower current CIMs to benefit from quantum effects in dealing with frustrated Ising models. In addition, these ancillary modes can also enable error detection and searching for excited states.
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.