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

Advances in Optics and Photonics

Coherent SAT solvers: a tutorial

Sam Reifenstein, Timothee G. Leleu, Timothy P. McKenna, Marc Jankowski, Myoung‐Gyun Suh, Edwin Ng, Farad Khoyratee, Zoltán Toroczkai, Y. Yamamoto

Published Mar 22, 2023• 18 citations
Publisher

Abstract

The coherent Ising machine (CIM) is designed to solve the NP-hard Ising problem quickly and energy efficiently. Boolean satisfiability (SAT) and maximum satisfiability (Max-SAT) are classes of NP-complete and NP-hard problems that are equally important and more practically relevant combinatorial optimization problems. Many approaches exist for solving Boolean SAT, such as quantum annealing and classical stochastic local search (SLS) solvers; however, they all are expected to require many steps to solve hard SAT problems and, thus, require large amounts of time and energy. In addition, a SAT problem can be converted into an Ising problem and solved by an Ising machine; however, we have found that this approach has drawbacks. As well as reviewing existing approaches to solving the SAT problem, we have extended the CIM algorithm and architecture to solve SAT and Max-SAT problems directly. This new technique is termed a coherent SAT solver (CSS). We have studied three implementations of the CSS, all-optical, hybrid optical–digital and all digital (cyber-CSS), and have compared the time-to-solution and energy-to-solution of three machines. The cyber-CSS, which is already implemented using a graphics processing unit (GPU), demonstrates competitive performance against existing SLS solvers such as probSAT. The CSS is also compared with another continuous-time SAT solver known as the CTDS, and the scaling behavior is evaluated for random 3-SAT problems. The hybrid optical–digital CSS is a more performant and practical machine that can be realized in a short term. Finally, the all-optical CSS promises the best energy-to-solution cost; however various technical challenges in nonlinear optics await us in order to build this machine.

DOI
10.1364/aop.475823

Related papers

A coherent Ising machine with quantum measurement and feedback control

Yoshitaka Haribara, Y. Yamamoto, Ken‐ichi Kawarabayashi +1 more

Combinatorial optimization problems are computationally hard in general, but they are ubiquitous in our modern life. A coherent Ising machine (CIM) based on a multiple-pulse degenerate optical parametric oscillator (DOPO) is an alternative approach to solve these problems by a specialized physical computing system. To evaluate its potential performance, computational experiments are performed on maximum cut (MAX-CUT) problems against traditional algorithms such as semidefinite programming relaxation of Goemans-Williamson and simulated annealing by Kirkpatrick, et al. The numerical results empirically suggest that the almost constant computation time is required to obtain the reasonably accurate solutions of MAX-CUT problems on a CIM with the number of vertices up to $2 \times 10^4$ and the number of edges up to $10^8$.

•Jan 28, 2015•6 citations

A Comparative Study of Coherent Ising Machine Architectures Through a Unified Simulation Model

Vidisha Singhal, Peter A. Bermel

Coherent Ising Machines (CIMs) have emerged as promising hardware solvers for NP-hard combinatorial optimization problems, potentially offering energy-efficiency, accuracy, speed, and scalability. These problems span applications including scheduling, routing, resource allocation, and machine learning. Spin amplitude inhomogeneity (an artifact of its analog nature) can hinder CIM convergence to the ground state. Several CIM modifications have been proposed to address this issue. However, no prior work has systematically compared the performance of these concepts. This paper presents the first side-by-side evaluation of six promising CIM architectures using a unified simulation model. We develop stochastic differential equations, find optimal hyperparameters via Bayesian optimization per problem-architecture pair, and assess the performance on multiple metrics using MaxCut instances from the Gset and BiqMac datasets. CIM-SNN outperforms the rest on most metrics, with a 54.21% average success probability (SP) improvement and 1.36× less time-to-solution (TTS) at 96% GS energy compared to the Standard CIM on BiqMac graphs. Other CIMs show some advantages on certain Gset graphs. CIM-QA is usually the worst-performing, with an 18.55% average SP loss and a 1.30× higher TTS at 96% GS compared to the Standard CIM on BiqMac graphs. CIM-SNN demonstrates the greatest noise robustness and promise for further tuning via a linear pump schedule. CIM-QA benefits from high noise levels. This study makes two key contributions: (1) identifying promising CIM architectures to guide targeted research and accelerate practical adoption, and (2) providing a unified framework for evaluating future architectural modifications against existing ones.

IEEE Access•Jan 1, 2025•0 citations

Quantum Annealing and the Satisfiability Problem

Kristen L. Pudenz, Tallant Gregory S., Todd R. Belote +1 more

The utility of satisfiability (SAT) as an application focused hard computational problem is well established. We explore the potential of quantum annealing to enhance classical SAT solving, especially where sampling from the space of all possible solutions is of interest. We address the formulation of SAT problems to make them suitable for commercial quantum annealers, practical concerns in their implementation, and how the performance of the resulting quantum solver compares to and complements classical SAT solvers.

arXiv:1612.07258•Advances in parallel computing•Jan 1, 2017•7 citations

Quantum Approaches to NP-Hard Combinatorial Optimization Problems: A Review

Charan Karnati, P. Venkata Subba Reddy

NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.

•Aug 5, 2025•0 citations

Augmenting an electronic Ising machine to effectively solve boolean satisfiability

Anshujit Sharma, Matthew Burns, Andrew Hahn +1 more

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.

arXiv:2305.01623•Scientific Reports•Dec 21, 2023•27 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
The coherent Ising machine (CIM) is designed to solve the NP-hard Ising problem quickly and energy efficiently. Boolean satisfiability (SAT) and maximum satisfiability (Max-SAT) are classes of NP-complete and NP-hard problems that are equally important and more practically relevant combinatorial optimization problems. Many approaches exist for solving Boolean SAT, such as quantum annealing and classical stochastic local search (SLS) solvers; however, they all are expected to require many steps to solve hard SAT problems and, thus, require large amounts of time and energy. In addition, a SAT problem can be converted into an Ising problem and solved by an Ising machine; however, we have found that this approach has drawbacks. As well as reviewing existing approaches to solving the SAT problem, we have extended the CIM algorithm and architecture to solve SAT and Max-SAT problems directly. This new technique is termed a coherent SAT solver (CSS). We have studied three implementations of the CSS, all-optical, hybrid optical–digital and all digital (cyber-CSS), and have compared the time-to-solution and energy-to-solution of three machines. The cyber-CSS, which is already implemented using a graphics processing unit (GPU), demonstrates competitive performance against existing SLS solvers such as probSAT. The CSS is also compared with another continuous-time SAT solver known as the CTDS, and the scaling behavior is evaluated for random 3-SAT problems. The hybrid optical–digital CSS is a more performant and practical machine that can be realized in a short term. Finally, the all-optical CSS promises the best energy-to-solution cost; however various technical challenges in nonlinear optics await us in order to build this machine.
Combinatorial optimization problems are computationally hard in general, but they are ubiquitous in our modern life. A coherent Ising machine (CIM) based on a multiple-pulse degenerate optical parametric oscillator (DOPO) is an alternative approach to solve these problems by a specialized physical computing system. To evaluate its potential performance, computational experiments are performed on maximum cut (MAX-CUT) problems against traditional algorithms such as semidefinite programming relaxation of Goemans-Williamson and simulated annealing by Kirkpatrick, et al. The numerical results empirically suggest that the almost constant computation time is required to obtain the reasonably accurate solutions of MAX-CUT problems on a CIM with the number of vertices up to 2×1042 \times 10^42×104 and the number of edges up to 10810^8108.
Coherent Ising Machines (CIMs) have emerged as promising hardware solvers for NP-hard combinatorial optimization problems, potentially offering energy-efficiency, accuracy, speed, and scalability. These problems span applications including scheduling, routing, resource allocation, and machine learning. Spin amplitude inhomogeneity (an artifact of its analog nature) can hinder CIM convergence to the ground state. Several CIM modifications have been proposed to address this issue. However, no prior work has systematically compared the performance of these concepts. This paper presents the first side-by-side evaluation of six promising CIM architectures using a unified simulation model. We develop stochastic differential equations, find optimal hyperparameters via Bayesian optimization per problem-architecture pair, and assess the performance on multiple metrics using MaxCut instances from the Gset and BiqMac datasets. CIM-SNN outperforms the rest on most metrics, with a 54.21% average success probability (SP) improvement and 1.36× less time-to-solution (TTS) at 96% GS energy compared to the Standard CIM on BiqMac graphs. Other CIMs show some advantages on certain Gset graphs. CIM-QA is usually the worst-performing, with an 18.55% average SP loss and a 1.30× higher TTS at 96% GS compared to the Standard CIM on BiqMac graphs. CIM-SNN demonstrates the greatest noise robustness and promise for further tuning via a linear pump schedule. CIM-QA benefits from high noise levels. This study makes two key contributions: (1) identifying promising CIM architectures to guide targeted research and accelerate practical adoption, and (2) providing a unified framework for evaluating future architectural modifications against existing ones.
The utility of satisfiability (SAT) as an application focused hard computational problem is well established. We explore the potential of quantum annealing to enhance classical SAT solving, especially where sampling from the space of all possible solutions is of interest. We address the formulation of SAT problems to make them suitable for commercial quantum annealers, practical concerns in their implementation, and how the performance of the resulting quantum solver compares to and complements classical SAT solvers.
NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.
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.
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.