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:2405.17112 · Communications Physics

Using continuation methods to analyse the difficulty of problems solved by Ising machines

Jacob Lamers, Guy Verschaffelt, Guy Van der Sande

Published Nov 21, 2024• 10 citations
arXivHTMLPDF

Abstract

Ising machines are dedicated hardware solvers of NP-hard optimization problems. However, they do not always find the most optimal solution. The probability of finding this optimal solution depends on the problem at hand. Using continuation methods, we show that this is closely linked to how the ground state emerges from other states when a system parameter is changed, i.e. its bifurcation sequence. From this analysis, we can determine the effectiveness of solution schemes. Moreover, we find that the proper choice of implementation of the Ising machine can drastically change this bifurcation sequence and therefore vastly increase the probability of finding the optimal solution. Lastly, we also show that continuation methods themselves can be used directly to solve optimization problems. An Ising machine is a piece of hardware that tries to solve quadratic unconstrained binary optimization problems. The authors explain why some problems are significantly easier to tackle than others using Ising machines and demonstrate that different physical implementations can render some challenging problems a lot easier to solve.

DOI
10.1038/s42005-024-01867-4

Related papers

How to Boost Ising Machines' Ability to Find Optimum Solutions: a Bifurcation Analysis

Jacob Lamers, Guy Verschaffelt, Guy Van der Sande

Photonic Ising machines are a recent and promising non-von Neuman architecture to efficiently solve large NP-hard optimization problems. This is done by letting spins evolve to the ground state of the Ising system. However, the Ising machine does not always relax to this ground state and can get trapped in local minima, resulting in suboptimal solutions. Here, we show that Ising-encoded optimization problems implemented on analog Ising machines can be divided in three difficulty classes and we propose an annealing scheme to efficiently solve two of them. Furthermore, we show that changing the physical implementation of the Ising machine can cause a problem to change difficulty class, rendering it potentially a lot more easy to solve.

OptoElectronics and Communications Conference and International Conference on Photonics in Switching and Computing (OECC/PSC)•Sep 26, 2023•0 citations

Efficient optimization accelerator framework for multi-state spin Ising problems

Chirag Garg, Sayeef Salahuddin

Abstract Ising Machines are emerging hardware architectures that efficiently solve NP-hard combinatorial optimization problems. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form, but this transformation often complicates the solution landscape, degrading performance, especially for multi-state problems. To address this challenge, we model spin interactions as generalized boolean logic function to significantly reduce the exploration space. We demonstrate the effectiveness of our approach on graph coloring problem using probabilistic Ising solvers, achieving similar accuracy compared to state-of-the-art heuristics and machine learning algorithms. It also shows significant improvement over state-of-the-art QUBO-based Ising solvers, including probabilistic Ising and simulated bifurcation machines. We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach that shows $$\sim$$ ~ 10000 $$\times$$ × performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5 $$-$$ − 4 $$\times$$ × over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.

arXiv:2505.20250•Nature Communications•Oct 30, 2025•5 citations

Physics-Inspired Optimization in the QUBO Framework: Key Concepts and Approaches

Lien-Po Yu, Chin-Fu Nien

Quantum computing promises to have a tremendous advantage over its classical counterpart for solving computationally hard problems, yet remains in a relatively early stage for practical applications owing to the limited capabilities of today’s quantum computers. The approach to the special purposes of quantum computers by exploiting the special-purpose physics-inspired or quantum-inspired computers is emerging as a novel alternative to its quantum counterpart in tackling hard problems in high-performance computing. Inspired by physics, the Ising machine — a type of special-purpose computer that implements or emulates physics or quantum effects of the Ising model to speed up finding solutions to optimization problems — has recently become an active research area in the field of combinatorial optimization. This paper is to address the key enabling software and hardware technology underlying physics-inspired optimization using Ising machines in the unified quadratic unconstrained binary optimization (QUBO) framework for modeling and solving computationally hard combinatorial optimization problems, and with an aim to shed some light on the challenges and opportunities associated with the ever-growing landscape of this novel high-performance computing.

SPIN•Aug 30, 2023•1 citation

Continuous black-box optimization with an Ising machine and random subspace coding

Syun Izawa, Koki Kitai, Shu Tanaka +2 more

A black-box optimization algorithm such as Bayesian optimization finds the extremum of an unknown function by alternating the inference of the underlying function and optimization of an acquisition function. In a high-dimensional space, such algorithms perform poorly due to the difficulty of acquisition function optimization. Herein, we apply Ising machines to overcome the difficulty in the continuous black-box optimization. As an Ising machine specializes in optimization of binary problems, a continuous vector has to be encoded to binary, and the solution by Ising machines has to be translated back. Our method has the following three parts: (1) random subspace coding based on axis-parallel hyperrectangles from continuous vector to binary vector, (2) a quadratic unconstrained binary optimization (QUBO) defined by the acquisition function based on the nonnegative-weighted linear regression model, which is solved by Ising machines, and (3) a penalization scheme to ensure that the solution can be translated back. It is shown with benchmark tests that its performance using the D-Wave Advantage quantum annealer and simulated annealing is competitive with a state-of-the-art method based on the Gaussian process in high-dimensional problems. Our method may open up the possibility of Ising machines and other QUBO solvers, including a quantum approximate optimization algorithm using gated-quantum computers, and may expand its range of application to continuous-valued problems.

arXiv:2104.14778•Physical Review Research•Apr 21, 2022•37 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

An Evolutionary Ising Optimization Framework for Unconstrained Binary Quadratic Programming

Wujie Fu, Anupam Trivedi, Guanyu Chen +3 more

An Ising machine (IM), as a type of analog computer tailored for tackling intractable combinatorial optimization problems, has attracted remarkable attention in recent years. In contrast to the blossoming field of bespoke IM hardware, developing metaheuristics from IMs remains largely uninvestigated. Here, we propose a physics-inspired evolutionary computation paradigm, termed the Ising optimization framework (IOF); it comprises a unique Ising algorithm and a hybrid annealing scheme, which together are well-suited for solving quadratic unconstrained binary optimization (QUBO) problems embedded in Ising system energy. The Ising algorithm leverages a set of iterated self-mapping functions to evolve an Ising-spin swarm, enabling efficient energy minimization in artificial Ising systems while mitigating detrimental chaos. Complementing the algorithm, a hybrid annealing scheme integrating singular value dropout, bifurcation control, and a nudging strategy, is devised to augment the overall optimization capacity. The effectiveness of the IOF is validated on various Ising and Max-cut problems with decision variables ranging from 625 to 5000 in number. In comparison to four major types of methods for solving QUBOs, including IM simulations, nature-inspired algorithms, a state-of-the-art heuristic, and the commercial solver Gurobi, the IOF consistently demonstrates notable optimization quality and computational efficiency. This paper provides a theoretical foundation and practical guidelines for bridging Ising-inspired approaches with evolutionary computation, offering an evolutionary perspective on Ising optimizations and suggesting a fertile avenue for future research and application.

IEEE Transactions on Evolutionary Computation•May 7, 2025•3 citations
Ising machines are dedicated hardware solvers of NP-hard optimization problems. However, they do not always find the most optimal solution. The probability of finding this optimal solution depends on the problem at hand. Using continuation methods, we show that this is closely linked to how the ground state emerges from other states when a system parameter is changed, i.e. its bifurcation sequence. From this analysis, we can determine the effectiveness of solution schemes. Moreover, we find that the proper choice of implementation of the Ising machine can drastically change this bifurcation sequence and therefore vastly increase the probability of finding the optimal solution. Lastly, we also show that continuation methods themselves can be used directly to solve optimization problems. An Ising machine is a piece of hardware that tries to solve quadratic unconstrained binary optimization problems. The authors explain why some problems are significantly easier to tackle than others using Ising machines and demonstrate that different physical implementations can render some challenging problems a lot easier to solve.
Photonic Ising machines are a recent and promising non-von Neuman architecture to efficiently solve large NP-hard optimization problems. This is done by letting spins evolve to the ground state of the Ising system. However, the Ising machine does not always relax to this ground state and can get trapped in local minima, resulting in suboptimal solutions. Here, we show that Ising-encoded optimization problems implemented on analog Ising machines can be divided in three difficulty classes and we propose an annealing scheme to efficiently solve two of them. Furthermore, we show that changing the physical implementation of the Ising machine can cause a problem to change difficulty class, rendering it potentially a lot more easy to solve.
Abstract Ising Machines are emerging hardware architectures that efficiently solve NP-hard combinatorial optimization problems. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form, but this transformation often complicates the solution landscape, degrading performance, especially for multi-state problems. To address this challenge, we model spin interactions as generalized boolean logic function to significantly reduce the exploration space. We demonstrate the effectiveness of our approach on graph coloring problem using probabilistic Ising solvers, achieving similar accuracy compared to state-of-the-art heuristics and machine learning algorithms. It also shows significant improvement over state-of-the-art QUBO-based Ising solvers, including probabilistic Ising and simulated bifurcation machines. We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach that shows ∼\sim∼ ~ 10000 ×\times× × performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5 −-− − 4 ×\times× × over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.
Quantum computing promises to have a tremendous advantage over its classical counterpart for solving computationally hard problems, yet remains in a relatively early stage for practical applications owing to the limited capabilities of today’s quantum computers. The approach to the special purposes of quantum computers by exploiting the special-purpose physics-inspired or quantum-inspired computers is emerging as a novel alternative to its quantum counterpart in tackling hard problems in high-performance computing. Inspired by physics, the Ising machine — a type of special-purpose computer that implements or emulates physics or quantum effects of the Ising model to speed up finding solutions to optimization problems — has recently become an active research area in the field of combinatorial optimization. This paper is to address the key enabling software and hardware technology underlying physics-inspired optimization using Ising machines in the unified quadratic unconstrained binary optimization (QUBO) framework for modeling and solving computationally hard combinatorial optimization problems, and with an aim to shed some light on the challenges and opportunities associated with the ever-growing landscape of this novel high-performance computing.
A black-box optimization algorithm such as Bayesian optimization finds the extremum of an unknown function by alternating the inference of the underlying function and optimization of an acquisition function. In a high-dimensional space, such algorithms perform poorly due to the difficulty of acquisition function optimization. Herein, we apply Ising machines to overcome the difficulty in the continuous black-box optimization. As an Ising machine specializes in optimization of binary problems, a continuous vector has to be encoded to binary, and the solution by Ising machines has to be translated back. Our method has the following three parts: (1) random subspace coding based on axis-parallel hyperrectangles from continuous vector to binary vector, (2) a quadratic unconstrained binary optimization (QUBO) defined by the acquisition function based on the nonnegative-weighted linear regression model, which is solved by Ising machines, and (3) a penalization scheme to ensure that the solution can be translated back. It is shown with benchmark tests that its performance using the D-Wave Advantage quantum annealer and simulated annealing is competitive with a state-of-the-art method based on the Gaussian process in high-dimensional problems. Our method may open up the possibility of Ising machines and other QUBO solvers, including a quantum approximate optimization algorithm using gated-quantum computers, and may expand its range of application to continuous-valued problems.
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.
An Ising machine (IM), as a type of analog computer tailored for tackling intractable combinatorial optimization problems, has attracted remarkable attention in recent years. In contrast to the blossoming field of bespoke IM hardware, developing metaheuristics from IMs remains largely uninvestigated. Here, we propose a physics-inspired evolutionary computation paradigm, termed the Ising optimization framework (IOF); it comprises a unique Ising algorithm and a hybrid annealing scheme, which together are well-suited for solving quadratic unconstrained binary optimization (QUBO) problems embedded in Ising system energy. The Ising algorithm leverages a set of iterated self-mapping functions to evolve an Ising-spin swarm, enabling efficient energy minimization in artificial Ising systems while mitigating detrimental chaos. Complementing the algorithm, a hybrid annealing scheme integrating singular value dropout, bifurcation control, and a nudging strategy, is devised to augment the overall optimization capacity. The effectiveness of the IOF is validated on various Ising and Max-cut problems with decision variables ranging from 625 to 5000 in number. In comparison to four major types of methods for solving QUBOs, including IM simulations, nature-inspired algorithms, a state-of-the-art heuristic, and the commercial solver Gurobi, the IOF consistently demonstrates notable optimization quality and computational efficiency. This paper provides a theoretical foundation and practical guidelines for bridging Ising-inspired approaches with evolutionary computation, offering an evolutionary perspective on Ising optimizations and suggesting a fertile avenue for future research and application.