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:2412.00284

Enumeration algorithms for combinatorial problems using Ising machines: When should we stop exploring energy landscapes?

Yuta Mizuno, Ali, Mohammad, Tamiki Komatsuzaki

Published Nov 29, 2024• 2 citations
arXivHTMLPDF

Abstract

Combinatorial problems such as combinatorial optimization and constraint satisfaction problems arise in decision-making across various fields of science and technology. In real-world applications, when multiple optimal or constraint-satisfying solutions exist, enumerating all these solutions is often desirable, as it provides flexibility in decision-making. However, combinatorial problems and their enumeration versions pose significant computational challenges due to combinatorial explosion. To address these challenges, we propose enumeration algorithms for combinatorial optimization and constraint satisfaction problems using Ising machines. Ising machines are specialized devices designed to efficiently solve combinatorial problems by exploring the energy landscape of an Ising model. Ising machines typically sample lower-energy solutions with higher probability. Our enumeration algorithms repeatedly perform such sampling to collect all desirable solutions. The crux of the proposed algorithms lies in their stopping criteria for sampling-based energy landscape exploration, which are derived from probability theory. In particular, the proposed algorithms have theoretical guarantees that the failure probability of enumeration is bounded above by a user-specified value, provided that lower-cost solutions are sampled more frequently and equal-cost solutions are sampled with equal probability. Many physics-based Ising machines are expected to (approximately) satisfy these conditions. As a demonstration, we applied our algorithm using simulated annealing to maximum clique enumeration on random graphs. We found that our algorithm enumerates all maximum cliques in large, dense graphs faster than a conventional branch-and-bound algorithm specifically designed for maximum clique enumeration. These findings underscore the effectiveness and potential of our proposed approach.

DOI
10.48550/arxiv.2412.00284

Related papers

AutoQUBO v2: Towards Efficient and Effective QUBO Formulations for Ising Machines

Justin Pauckert, Mayowa Ayodele, Marcos Diez García +2 more

The QUBO framework provides a way to model, in principle, any combinatorial optimization problem and enables the use of Ising machines to solve it. Ising machines are devices designed to quickly find good solutions to QUBO problems. In previous work, Auto-QUBO was designed to automatically generate QUBO formulations from a high-level problem description. We address two shortcomings of this method. It only works on a per-instance basis, making repeated formulations for similar problems inefficient, and relies on the user to specify penalty weights. This work introduces symbolic sampling, which provides QUBO formulations for entire problem classes. We demonstrate the speedup that can be achieved with this approach using instances of the maximum clique problem. Additionally, we use proven methods to compute valid penalty weights automatically to simplify the translation process. By providing a user-friendly way to generate QUBO formulations in an efficient manner, both in terms of time and problem difficulty, we enable more people to use Ising machines for combinatorial optimization.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•16 citations

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

Sampling combinatorial energy landscapes by classical and quantum computation

Eric B. Jones

Combinatorial and, by extension, non-convex optimization problems are among the most difficult to solve computationally due to the inadequacy of local search methods alone to find global optima. The notion of an energy landscape provides a unified language to describe the origin of combinatorial complexity across a wide variety of fields including physics, materials science, and artificial intelligence. This thesis utilizes probabilistic techniques for efficiently sampling energy landscapes that rely on classical high-performance computers and near-term quantum computers. Such sampling techniques not only provide effective heuristics for solving combinatorial optimization problems, but also enable an explanation of physical phenomena that rely on features of the energy landscape other than the global optimum. Six use cases are considered that are of relevance to the design of future clean energy systems: i) a predictive theory of materials polymorphism based on the partitioning of the continuous energy landscape into structurally equivalent regions, ii) a theory of the structure of functional glasses based on thermally averaging structurally inequivalent regions, iii) solution of the minimum dominating set variant of the optimal phasor measurement unit placement problem on the power grid by quantum-annealing over a discrete, combinatorial solution landscape, iv) a reformulation and solution of the Markov decision process formalism underlying optimal control via quantum annealing, v) a prescription for the variational preparation of fractional quantum Hall states on a digital quantum computer that accommodates the size of the Hilbert space on quantum hardware while shifting the burden of variational minimization to classical, global optimization heuristics, and vi) the simulation of quantum cellular automata on a digital quantum computer and establishment thereby as primitives that could help design noise-resilient classically-parameterized unitary circuits such as those used in quantum machine learning. Through these domain examples, the outlook established herein is that efficient methods for exploring combinatorial energy landscapes, combined with resilience-minded near-term quantum algorithm construction and intelligent division of labor between quantum and classical resources, provide a promising path towards solving some of the most challenging problems in renewable energy science.

•Dec 31, 2019•0 citations

Energy landscapes of combinatorial optimization in Ising machines

Dmitrii Dobrynin, Adrien Renaudineau, Mohammad Hizzani +3 more

Physics-based Ising machines (IM) have been developed as dedicated processors for solving hard combinatorial optimization problems with higher speed and better energy efficiency. Generally, such systems employ local search heuristics to traverse energy landscapes in searching for optimal solutions. Here, we quantify and address some of the major challenges met by IMs by extending energy-landscape geometry visualization tools known as disconnectivity graphs. Using efficient sampling methods, we visually capture landscapes of problems having diverse structure and hardness manifesting as energetic and entropic barriers for IMs. We investigate energy barriers, local minima, and configuration space clustering effects caused by locality reduction methods when embedding combinatorial problems to the Ising hardware. To this end, we sample disconnectivity graphs of PUBO energy landscapes and their different QUBO mappings accounting for both local minima and saddle regions. We demonstrate that QUBO energy-landscape properties lead to the subpar performance for quadratic IMs and suggest directions for their improvement.

arXiv:2403.01320•Physical review. E•Oct 18, 2024•29 citations

A Review of Simulation Algorithms of Classical Ising Machines for Combinatorial optimization

Tingting Zhang, Qichao Tao, Bailiang Liu +1 more

Combinatorial optimization problems are difficult to solve due to the space explosion in an exhaustive search. Using Ising model-based solvers can efficiently find near-optimal solutions by minimizing the energy of a nonlinear Hamiltonian system. In contrast to Ising machines based on quantum mechanics, classical Ising machines using conventional technologies, such as the complementary metal-oxide-semiconductor, offer efficient implementations with competitive performance. In this paper, we briefly review recently developed simulation algorithms of classical Ising machines. These algorithms are classified by considering various inherent mechanisms in the simulation of physical phenomena. Then, strategies to improve the simulation efficiency are discussed by generalizing their characteristics and behaviours. These simulation algorithms are key for improving the efficiency of classical Ising machines in solving combinatorial optimization problems.

IEEE International Symposium on Circuits and Systems proceedings•May 28, 2022•17 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
Combinatorial problems such as combinatorial optimization and constraint satisfaction problems arise in decision-making across various fields of science and technology. In real-world applications, when multiple optimal or constraint-satisfying solutions exist, enumerating all these solutions is often desirable, as it provides flexibility in decision-making. However, combinatorial problems and their enumeration versions pose significant computational challenges due to combinatorial explosion. To address these challenges, we propose enumeration algorithms for combinatorial optimization and constraint satisfaction problems using Ising machines. Ising machines are specialized devices designed to efficiently solve combinatorial problems by exploring the energy landscape of an Ising model. Ising machines typically sample lower-energy solutions with higher probability. Our enumeration algorithms repeatedly perform such sampling to collect all desirable solutions. The crux of the proposed algorithms lies in their stopping criteria for sampling-based energy landscape exploration, which are derived from probability theory. In particular, the proposed algorithms have theoretical guarantees that the failure probability of enumeration is bounded above by a user-specified value, provided that lower-cost solutions are sampled more frequently and equal-cost solutions are sampled with equal probability. Many physics-based Ising machines are expected to (approximately) satisfy these conditions. As a demonstration, we applied our algorithm using simulated annealing to maximum clique enumeration on random graphs. We found that our algorithm enumerates all maximum cliques in large, dense graphs faster than a conventional branch-and-bound algorithm specifically designed for maximum clique enumeration. These findings underscore the effectiveness and potential of our proposed approach.
The QUBO framework provides a way to model, in principle, any combinatorial optimization problem and enables the use of Ising machines to solve it. Ising machines are devices designed to quickly find good solutions to QUBO problems. In previous work, Auto-QUBO was designed to automatically generate QUBO formulations from a high-level problem description. We address two shortcomings of this method. It only works on a per-instance basis, making repeated formulations for similar problems inefficient, and relies on the user to specify penalty weights. This work introduces symbolic sampling, which provides QUBO formulations for entire problem classes. We demonstrate the speedup that can be achieved with this approach using instances of the maximum clique problem. Additionally, we use proven methods to compute valid penalty weights automatically to simplify the translation process. By providing a user-friendly way to generate QUBO formulations in an efficient manner, both in terms of time and problem difficulty, we enable more people to use Ising machines for combinatorial optimization.
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.
Combinatorial and, by extension, non-convex optimization problems are among the most difficult to solve computationally due to the inadequacy of local search methods alone to find global optima. The notion of an energy landscape provides a unified language to describe the origin of combinatorial complexity across a wide variety of fields including physics, materials science, and artificial intelligence. This thesis utilizes probabilistic techniques for efficiently sampling energy landscapes that rely on classical high-performance computers and near-term quantum computers. Such sampling techniques not only provide effective heuristics for solving combinatorial optimization problems, but also enable an explanation of physical phenomena that rely on features of the energy landscape other than the global optimum. Six use cases are considered that are of relevance to the design of future clean energy systems: i) a predictive theory of materials polymorphism based on the partitioning of the continuous energy landscape into structurally equivalent regions, ii) a theory of the structure of functional glasses based on thermally averaging structurally inequivalent regions, iii) solution of the minimum dominating set variant of the optimal phasor measurement unit placement problem on the power grid by quantum-annealing over a discrete, combinatorial solution landscape, iv) a reformulation and solution of the Markov decision process formalism underlying optimal control via quantum annealing, v) a prescription for the variational preparation of fractional quantum Hall states on a digital quantum computer that accommodates the size of the Hilbert space on quantum hardware while shifting the burden of variational minimization to classical, global optimization heuristics, and vi) the simulation of quantum cellular automata on a digital quantum computer and establishment thereby as primitives that could help design noise-resilient classically-parameterized unitary circuits such as those used in quantum machine learning. Through these domain examples, the outlook established herein is that efficient methods for exploring combinatorial energy landscapes, combined with resilience-minded near-term quantum algorithm construction and intelligent division of labor between quantum and classical resources, provide a promising path towards solving some of the most challenging problems in renewable energy science.
Physics-based Ising machines (IM) have been developed as dedicated processors for solving hard combinatorial optimization problems with higher speed and better energy efficiency. Generally, such systems employ local search heuristics to traverse energy landscapes in searching for optimal solutions. Here, we quantify and address some of the major challenges met by IMs by extending energy-landscape geometry visualization tools known as disconnectivity graphs. Using efficient sampling methods, we visually capture landscapes of problems having diverse structure and hardness manifesting as energetic and entropic barriers for IMs. We investigate energy barriers, local minima, and configuration space clustering effects caused by locality reduction methods when embedding combinatorial problems to the Ising hardware. To this end, we sample disconnectivity graphs of PUBO energy landscapes and their different QUBO mappings accounting for both local minima and saddle regions. We demonstrate that QUBO energy-landscape properties lead to the subpar performance for quadratic IMs and suggest directions for their improvement.
Combinatorial optimization problems are difficult to solve due to the space explosion in an exhaustive search. Using Ising model-based solvers can efficiently find near-optimal solutions by minimizing the energy of a nonlinear Hamiltonian system. In contrast to Ising machines based on quantum mechanics, classical Ising machines using conventional technologies, such as the complementary metal-oxide-semiconductor, offer efficient implementations with competitive performance. In this paper, we briefly review recently developed simulation algorithms of classical Ising machines. These algorithms are classified by considering various inherent mechanisms in the simulation of physical phenomena. Then, strategies to improve the simulation efficiency are discussed by generalizing their characteristics and behaviours. These simulation algorithms are key for improving the efficiency of classical Ising machines in solving combinatorial optimization problems.
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.