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

arXiv:2511.21046

On the Limits of Ising Machines for Circuit-Derived SAT

Ahmet Efe, Abhimanyu Kumar, Nafisa Sadaf Prova, Hüsrev Cılasun, Ziqing Zeng, Tahmida Islam, R.S. Yin, Chaohui Li, Peter Kreye, Chris H. Kim, Sachin S. Sapatnekar, Ulya R. Karpuzcu

Published Nov 26, 2025• 1 citation
arXivHTMLPDF

Abstract

Emerging Ising machines are promising for solving computationally hard optimization problems, yet their limits on structured, circuit-derived satisfiability (SAT) problems remain poorly understood. Using semiprime factorization as a representative benchmark, we show that tight constraints, when mapped into optimization form, fundamentally distort the energy landscape, and that these distortions are amplified when problems are decomposed to fit limited Ising machine capacity. To address this, we propose a hybrid flow that offloads Ising-harmful structure to lightweight preprocessing while reserving the genuinely hard search for the Ising machine. We further show that generic, circuit-structure-unaware decomposition is insufficient for circuit-derived instances, and that structure-aware partitioning is essential. These findings identify constraint handling as a central obstacle, highlighting hybrid hardware-software approaches as the path forward for scaling Ising machines to real-world SAT workloads. Evaluated on fabricated 45-spin all-to-all Ising chips, our flow extends solvable problem sizes from 8-bit (94 variables) to 11-bit (190 variables) without any hardware changes.

DOI
10.48550/arxiv.2511.21046

Related papers

Resource-Constrained Heuristic for Max-SAT

Brian Matejek, Daniel Elenius, Cale M. Gentry +2 more

We propose a resource-constrained heuristic for instances of Max-SAT that iteratively decomposes a larger problem into smaller subcomponents that can be solved by optimized solvers and hardware. The unconstrained outer loop maintains the state space of a given problem and selects a subset of the SAT variables for optimization independent of previous calls. The resource-constrained inner loop maximizes the number of satisfiable clauses in the "sub-SAT" problem. Our outer loop is agnostic to the mechanisms of the inner loop, allowing for the use of traditional solvers for the optimization step. However, we can also transform the selected "sub-SAT" problem into a quadratic unconstrained binary optimization (QUBO) one and use specialized hardware for optimization. In contrast to existing solutions that convert a SAT instance into a QUBO one before decomposition, we choose a subset of the SAT variables before QUBO optimization. We analyze a set of variable selection methods, including a novel graph-based method that exploits the structure of a given SAT instance. The number of QUBO variables needed to encode a (sub-)SAT problem varies, so we additionally learn a model that predicts the size of sub-SAT problems that will fit a fixed-size QUBO solver. We empirically demonstrate our results on a set of randomly generated Max-SAT instances as well as real world examples from the Max-SAT evaluation benchmarks and outperform existing QUBO decomposer solutions.

arXiv:2410.09173•Oct 11, 2024•1 citation

Self-Adaptive Ising Machines for Constrained Optimization

Corentin Delacour

Ising machines (IM) are physics-inspired alternatives to von Neumann architectures for solving hard optimization tasks. By mapping binary variables to coupled Ising spins, IMs can naturally solve unconstrained combinatorial optimization problems such as finding maximum cuts in graphs. However, despite their importance in practical applications, constrained problems remain challenging to solve for IMs that require large quadratic energy penalties to ensure the correspondence between energy ground states and constrained optimal solutions. To relax this requirement, we propose a self-adaptive IM that iteratively shapes its energy landscape using a Lagrange relaxation of constraints and avoids prior tuning of penalties. Using a probabilistic-bit (p-bit) IM emulated in software, we benchmark our algorithm with multidimensional knapsack problems (MKP) and quadratic knapsack problems (QKP), the latter being an Ising problem with linear constraints. For QKP with 300 variables, the proposed algorithm finds better solutions than state-of-the-art IMs such as Fujitsu's Digital Annealer and requires 7,500x fewer samples. Our results show that adapting the energy landscape during the search can speed up IMs for constrained optimization.

arXiv:2501.04971•Design, Automation, and Test in Europe•Mar 31, 2025•3 citations

SATIC: An Optimizing Ising Compiler for SAT(isfiability)

Ahmet Efe, Hüsrev Cılasun, Abhimanyu Kumar +9 more

Ising machines show great potential as hardware solvers for combinatorial optimization problems such as Boolean Satisfiability (SAT) - one of the hardest classic problems of practical importance. Unlocking this potential, however, is only possible by bridging the gap between SAT problem characteristics and Ising machine specifics. In this paper, we introduce a novel optimizing compiler featuring a bag of powerful heuristic tricks, SATIC, toward this goal. We evaluate SATIC on a representative manufactured Ising chip. Our measurements show that SATIC enables Ising machines to solve up to$\text{73} \times$larger SAT problems than the hardware capacity would otherwise allow, demonstrating unmatched performance and scalability.

Proceedings - International Symposium on Computer Architecture/Proceedings•Jun 1, 2026•1 citation

組合せ最適化へのイジングマシンの実用的な適用方法に関する研究

Kentaro Ohno

An emerging class of specialized hardware called Ising machines offers a novel approach to tackling computationally intractable combinatorial optimization problems.Specifically, Ising machines are designed to solve problems formulated as the quadratic unconstrained binary optimization (QUBO) problem.However, their widespread practical adoption is currently hindered by several critical obstacles, including the challenge of achieving high solution accuracy, the absence of fair and robust comparative frameworks against traditional optimization methods, and limitations in handling large-scale problems.This dissertation addresses these fundamental challenges through a software-centric approach centered on preprocessing and postprocessing techniques applied to the input and output of Ising machines.This work makes three key contributions.First, a novel preprocessing methodology is proposed to improve accuracy and scalability by linearizing QUBO problems.This technique reduces quadratic terms in the input problem through the extraction of variable ordering relationships, which simplifies the problem structure, enables compact embedding, and offers broader applicability than existing variable reduction methods.The method is successfully validated on QUBO and multi-dimensional knapsack problem instances.Second, a twostage postprocessing methodology is developed to yield feasible, high-quality solutions for constrained problems by adapting basic heuristic principles.This enabled the first fair benchmark of a state-of-the-art Ising machine against traditional heuristics on the quadratic knapsack problem, successfully obtaining high-quality solutions on instances of size up to 2,000 variables.Finally, coefficient reduction techniques for suppressing errors in quantum annealers under realistic minor-embedding conditions are systematically validated.Our findings clarify the practical effectiveness of these methods in improving sample quality on real devices, a crucial area that had been largely unexamined.Collectively, these contributions provide essential software methodologies that bridge the gap between the theoretical promise of Ising machines and their effective real-world application, establishing a foundation for future advancements of Ising machines such as software-hardware co-design to achieve greater improvements in accuracy and scalability.

•Mar 15, 2026•0 citations

Linearizing Binary Optimization Problems Using Variable Posets for Ising Machines

Kentaro Ohno, Nozomu Togawa

Ising machines are next-generation computers expected to efficiently sample near-optimal solutions of combinatorial optimization problems. Combinatorial optimization problems are modeled as quadratic unconstrained binary optimization (QUBO) problems to apply an Ising machine. However, current state-of-the-art Ising machines still often fail to output nearoptimal solutions due to the complicated energy landscape of QUBO problems. Furthermore, the physical implementation of Ising machines severely restricts the size of QUBO problems to be input as a result of limited hardware graph structures. In this study, we take a new approach to these challenges by injecting auxiliary penalties preserving the optimum, which reduces quadratic terms in QUBO objective functions. The process simultaneously simplifies the energy landscape of QUBO problems, allowing the search for near-optimal solutions, and makes QUBO problems sparser, facilitating encoding into Ising machines with restriction on the hardware graph structure. We propose linearization of QUBO problems using variable posets as an outcome of the approach. By applying the proposed method to synthetic QUBO instances and to multi-dimensional knapsack problems, we empirically validate the effects on enhancing minorembedding of QUBO problems and the performance of Ising machines.

arXiv:2307.05125•IEEE Transactions on Emerging Topics in Computing•May 30, 2024•7 citations

Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem

Kentaro Ohno, Tatsuhiko Shirai, Nozomu Togawa

Combinatorial optimization has wide applications from industry to natural science. Ising machines bring an emerging computing paradigm for efficiently solving a combinatorial optimization problem by searching a ground state of a given Ising model. Current cutting-edge Ising machines achieve fast sampling of near-optimal solutions of the max-cut problem. However, for problems with additional constraint conditions, their advantages have been hardly shown due to difficulties in handling the constraints. In this work, we focus on benchmarks of Ising machines on the quadratic knapsack problem (QKP). To bring out their practical performance, we propose fast two-stage post-processing for Ising machines, which makes handling the constraint easier. Simulation based on simulated annealing shows that the proposed method substantially improves the solving performance of Ising machines and the improvement is robust to a choice of encoding of the constraint condition. Through evaluation using an Ising machine called Amplify Annealing Engine, the proposed method is shown to dramatically improve its solving performance on the QKP. These results are a crucial step toward showing advantages of Ising machines on practical problems involving various constraint conditions.

arXiv:2403.19175•IEEE Access•Jan 1, 2024•14 citations
Emerging Ising machines are promising for solving computationally hard optimization problems, yet their limits on structured, circuit-derived satisfiability (SAT) problems remain poorly understood. Using semiprime factorization as a representative benchmark, we show that tight constraints, when mapped into optimization form, fundamentally distort the energy landscape, and that these distortions are amplified when problems are decomposed to fit limited Ising machine capacity. To address this, we propose a hybrid flow that offloads Ising-harmful structure to lightweight preprocessing while reserving the genuinely hard search for the Ising machine. We further show that generic, circuit-structure-unaware decomposition is insufficient for circuit-derived instances, and that structure-aware partitioning is essential. These findings identify constraint handling as a central obstacle, highlighting hybrid hardware-software approaches as the path forward for scaling Ising machines to real-world SAT workloads. Evaluated on fabricated 45-spin all-to-all Ising chips, our flow extends solvable problem sizes from 8-bit (94 variables) to 11-bit (190 variables) without any hardware changes.
We propose a resource-constrained heuristic for instances of Max-SAT that iteratively decomposes a larger problem into smaller subcomponents that can be solved by optimized solvers and hardware. The unconstrained outer loop maintains the state space of a given problem and selects a subset of the SAT variables for optimization independent of previous calls. The resource-constrained inner loop maximizes the number of satisfiable clauses in the "sub-SAT" problem. Our outer loop is agnostic to the mechanisms of the inner loop, allowing for the use of traditional solvers for the optimization step. However, we can also transform the selected "sub-SAT" problem into a quadratic unconstrained binary optimization (QUBO) one and use specialized hardware for optimization. In contrast to existing solutions that convert a SAT instance into a QUBO one before decomposition, we choose a subset of the SAT variables before QUBO optimization. We analyze a set of variable selection methods, including a novel graph-based method that exploits the structure of a given SAT instance. The number of QUBO variables needed to encode a (sub-)SAT problem varies, so we additionally learn a model that predicts the size of sub-SAT problems that will fit a fixed-size QUBO solver. We empirically demonstrate our results on a set of randomly generated Max-SAT instances as well as real world examples from the Max-SAT evaluation benchmarks and outperform existing QUBO decomposer solutions.
Ising machines (IM) are physics-inspired alternatives to von Neumann architectures for solving hard optimization tasks. By mapping binary variables to coupled Ising spins, IMs can naturally solve unconstrained combinatorial optimization problems such as finding maximum cuts in graphs. However, despite their importance in practical applications, constrained problems remain challenging to solve for IMs that require large quadratic energy penalties to ensure the correspondence between energy ground states and constrained optimal solutions. To relax this requirement, we propose a self-adaptive IM that iteratively shapes its energy landscape using a Lagrange relaxation of constraints and avoids prior tuning of penalties. Using a probabilistic-bit (p-bit) IM emulated in software, we benchmark our algorithm with multidimensional knapsack problems (MKP) and quadratic knapsack problems (QKP), the latter being an Ising problem with linear constraints. For QKP with 300 variables, the proposed algorithm finds better solutions than state-of-the-art IMs such as Fujitsu's Digital Annealer and requires 7,500x fewer samples. Our results show that adapting the energy landscape during the search can speed up IMs for constrained optimization.
Ising machines show great potential as hardware solvers for combinatorial optimization problems such as Boolean Satisfiability (SAT) - one of the hardest classic problems of practical importance. Unlocking this potential, however, is only possible by bridging the gap between SAT problem characteristics and Ising machine specifics. In this paper, we introduce a novel optimizing compiler featuring a bag of powerful heuristic tricks, SATIC, toward this goal. We evaluate SATIC on a representative manufactured Ising chip. Our measurements show that SATIC enables Ising machines to solve up to73×\text{73} \times73×larger SAT problems than the hardware capacity would otherwise allow, demonstrating unmatched performance and scalability.
An emerging class of specialized hardware called Ising machines offers a novel approach to tackling computationally intractable combinatorial optimization problems.Specifically, Ising machines are designed to solve problems formulated as the quadratic unconstrained binary optimization (QUBO) problem.However, their widespread practical adoption is currently hindered by several critical obstacles, including the challenge of achieving high solution accuracy, the absence of fair and robust comparative frameworks against traditional optimization methods, and limitations in handling large-scale problems.This dissertation addresses these fundamental challenges through a software-centric approach centered on preprocessing and postprocessing techniques applied to the input and output of Ising machines.This work makes three key contributions.First, a novel preprocessing methodology is proposed to improve accuracy and scalability by linearizing QUBO problems.This technique reduces quadratic terms in the input problem through the extraction of variable ordering relationships, which simplifies the problem structure, enables compact embedding, and offers broader applicability than existing variable reduction methods.The method is successfully validated on QUBO and multi-dimensional knapsack problem instances.Second, a twostage postprocessing methodology is developed to yield feasible, high-quality solutions for constrained problems by adapting basic heuristic principles.This enabled the first fair benchmark of a state-of-the-art Ising machine against traditional heuristics on the quadratic knapsack problem, successfully obtaining high-quality solutions on instances of size up to 2,000 variables.Finally, coefficient reduction techniques for suppressing errors in quantum annealers under realistic minor-embedding conditions are systematically validated.Our findings clarify the practical effectiveness of these methods in improving sample quality on real devices, a crucial area that had been largely unexamined.Collectively, these contributions provide essential software methodologies that bridge the gap between the theoretical promise of Ising machines and their effective real-world application, establishing a foundation for future advancements of Ising machines such as software-hardware co-design to achieve greater improvements in accuracy and scalability.
Ising machines are next-generation computers expected to efficiently sample near-optimal solutions of combinatorial optimization problems. Combinatorial optimization problems are modeled as quadratic unconstrained binary optimization (QUBO) problems to apply an Ising machine. However, current state-of-the-art Ising machines still often fail to output nearoptimal solutions due to the complicated energy landscape of QUBO problems. Furthermore, the physical implementation of Ising machines severely restricts the size of QUBO problems to be input as a result of limited hardware graph structures. In this study, we take a new approach to these challenges by injecting auxiliary penalties preserving the optimum, which reduces quadratic terms in QUBO objective functions. The process simultaneously simplifies the energy landscape of QUBO problems, allowing the search for near-optimal solutions, and makes QUBO problems sparser, facilitating encoding into Ising machines with restriction on the hardware graph structure. We propose linearization of QUBO problems using variable posets as an outcome of the approach. By applying the proposed method to synthetic QUBO instances and to multi-dimensional knapsack problems, we empirically validate the effects on enhancing minorembedding of QUBO problems and the performance of Ising machines.
Combinatorial optimization has wide applications from industry to natural science. Ising machines bring an emerging computing paradigm for efficiently solving a combinatorial optimization problem by searching a ground state of a given Ising model. Current cutting-edge Ising machines achieve fast sampling of near-optimal solutions of the max-cut problem. However, for problems with additional constraint conditions, their advantages have been hardly shown due to difficulties in handling the constraints. In this work, we focus on benchmarks of Ising machines on the quadratic knapsack problem (QKP). To bring out their practical performance, we propose fast two-stage post-processing for Ising machines, which makes handling the constraint easier. Simulation based on simulated annealing shows that the proposed method substantially improves the solving performance of Ising machines and the improvement is robust to a choice of encoding of the constraint condition. Through evaluation using an Ising machine called Amplify Annealing Engine, the proposed method is shown to dramatically improve its solving performance on the QKP. These results are a crucial step toward showing advantages of Ising machines on practical problems involving various constraint conditions.