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

IEEE Transactions on Computers

Multi-spin-flip engineering in an Ising machine

Tatsuhiko Shirai, Nozomu Togawa

Published Jan 1, 2022• 9 citations
Publisher

Abstract

A merge process is proposed to engineer a multi-spin flip in an Ising machine. The merge process deforms the Hamiltonian (energy function) of the Ising model. We prove a theorem for the merge process and show that a single-spin flip in the deformed Hamiltonian is equivalent to a multi-spin flip in the original Hamiltonian. A merge process induces a transition within the subspace of feasible solutions. We propose a hybrid simulated annealing (SA) algorithm with the merge process. The hybrid algorithm outperforms the conventional SA algorithm, genetic algorithm, and tabu search in the binary quadratic knapsack problems (QKP) and the quadratic assignment problems (QAP). Finally, the hybrid merge process is used in a real Ising machine. The performance is improved in QKP and QAP instances. The merge process is generally applicable to existing Ising machine hardware because the deformed Hamiltonian keeps the format of the Ising model.

DOI
10.1109/tc.2022.3178325

Related papers

A GPU-Based Ising Machine With a Multi-Spin-Flip Capability for Constrained Combinatorial Optimization

Satoru Jimbo, Tatsuhiko Shirai, Nozomu Togawa +2 more

Ising machines are domain-specific computers that solve combinatorial optimization problems (COPs). They utilize an Ising model to represent a COP and search for the optimal spin configuration of the Ising model to solve the COP. Most Ising machines are based on simulated annealing (SA) and update the spin configuration according to single-spin-flip Markov Chain Monte Carlo methods. However, supporting a multi-spin flip is important to enhance the search performance of SA-based Ising machines when constrained COPs are solved. In this paper, we extend the merge method, which was introduced to provide a multi-spin-flip capability for SA-based Ising machines, and formulate it as a series of matrix multiplications that can be executed on a graphics processing unit (GPU) efficiently. We then construct a GPU-based Ising machine that implements the GPU-oriented merge method together with an extended SA algorithm. We finally demonstrate its superiority over the state-of-the-art GPU-based Ising machine for quadratic knapsack problems.

IEEE Access•Jan 1, 2024•8 citations

Analysis and Acceleration of the Quadratic Knapsack Problem on an Ising Machine

Matthieu Parizy, Nozomu Togawa

The binary quadratic knapsack problem (QKP) aims at optimizing a quadratic cost function within a single knapsack. Its applications and difficulty make it appealing for various industrial fields. In this paper we present an efficient strategy to solve the problem by modeling it as an Ising spin model using an Ising machine to search for its ground state which translates to the optimal solution of the problem. Secondly, in order to facilitate the search, we propose a novel technique to visualize the landscape of the search and demonstrate how difficult it is to solve QKP on an Ising machine. Finally, we propose two software solution improvement algorithms to efficiently solve QKP on an Ising machine.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jul 7, 2021•16 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•9 citations

Effectiveness of Hybrid Optimization Method for Quantum Annealing Machines

Shuta Kikuchi, Nozomu Togawa, Shu Tanaka

To enhance the performance of quantum annealing machines, several methods have been proposed to reduce the number of spins by fixing spin values through preprocessing. We proposed a hybrid optimization method that combines a simulated annealing (SA)-based non-quantum-type Ising machine with a quantum annealing machine. However, its applicability remains unclear. Therefore, we evaluated the performance of the hybrid method on large-size Ising models and analyzed its characteristics. The results indicate that the hybrid method improves upon solutions obtained by the preprocessing SA, even if the Ising models cannot be embedded in the quantum annealing machine. We analyzed the method from three perspectives: preprocessing, spin-fixed sub-Ising model generation method, and the accuracy of the quantum annealing machine. From the viewpoint of the minimum energy gap, we found that solving the sub-Ising model with a quantum annealing machine results in a higher solution accuracy than solving the original Ising model. Additionally, we demonstrated that the number of fixed spins and the accuracy of the quantum annealing machine affect the dependency of the solution accuracy on the sub-Ising model size.

arXiv:2507.15544•Jul 21, 2025•0 citations

Performance analysis of classical adiabatic annealing on Ising machines

Jacob Lamers, Guy Verschaffelt, Guy Van der Sande

Ising machines are a promising approach to solve combinatorial optimization problems. They map these problems onto the Ising model and search for low-energy configurations. However, navigating the rugged energy landscapes of these systems remains difficult. To improve this navigation, classical adiabatic annealing has been proposed in the literature as a heuristic optimization method for classical Ising machines. Using this technique, the Hamiltonian of the Ising machine is gradually transformed from an easily solvable Hamiltonian to the target Hamiltonian. However, its purported effectiveness is primarily motivated by an analogy to quantum adiabatic annealing, and systematic benchmarking has remained limited. In this work, we analyze the classical adiabatic annealing technique using continuation methods. Motivated by insights from this analysis, we propose an optimized annealing strategy we refer to as hybrid classical adiabatic annealing. We benchmark our proposed strategy using MaxCut instances with up to 800 spins and problems with external fields, for which it achieves a marginal improvement for a limited set of problems. We conclude that, although theoretically motivated and occasionally beneficial, the hybrid strategy does not offer a sufficient practical advantage over simpler, existing techniques.

quant-pharXiv:2606.07331•Jun 8, 2026•0 citations

Hybrid Optimization Method Using Simulated-Annealing-Based Ising Machine and Quantum Annealer

Shuta Kikuchi, Nozomu Togawa, Shu Tanaka

Ising machines have the potential to realize fast and highly accurate solvers for combinatorial optimization problems. They are classified based on their internal algorithms. Examples include simulated-annealing-based Ising machines (non-quantum-type Ising machines) and quantum-annealing-based Ising machines (quantum annealers). Herein we propose a hybrid optimization method, which utilizes the advantages of both types. In this hybrid optimization method, the preprocessing step is performed by solving the non-quantum-annealing Ising machine multiple times. Then sub-Ising models with a reduced size by spin fixing are solved using a quantum annealer. The performance of the hybrid optimization method is evaluated via simulations using Simulated Annealing (SA) as a non-quantum-type Ising machine and D-Wave Advantage as a quantum annealer. Additionally, we investigate the parameter dependence of the proposed hybrid optimization method. The hybrid optimization method outperforms the preprocessing SA and the quantum annealing machine alone in fully connected random Ising models.

arXiv:2306.06589•Journal of the Physical Society of Japan•Nov 10, 2023•8 citations
A merge process is proposed to engineer a multi-spin flip in an Ising machine. The merge process deforms the Hamiltonian (energy function) of the Ising model. We prove a theorem for the merge process and show that a single-spin flip in the deformed Hamiltonian is equivalent to a multi-spin flip in the original Hamiltonian. A merge process induces a transition within the subspace of feasible solutions. We propose a hybrid simulated annealing (SA) algorithm with the merge process. The hybrid algorithm outperforms the conventional SA algorithm, genetic algorithm, and tabu search in the binary quadratic knapsack problems (QKP) and the quadratic assignment problems (QAP). Finally, the hybrid merge process is used in a real Ising machine. The performance is improved in QKP and QAP instances. The merge process is generally applicable to existing Ising machine hardware because the deformed Hamiltonian keeps the format of the Ising model.
Ising machines are domain-specific computers that solve combinatorial optimization problems (COPs). They utilize an Ising model to represent a COP and search for the optimal spin configuration of the Ising model to solve the COP. Most Ising machines are based on simulated annealing (SA) and update the spin configuration according to single-spin-flip Markov Chain Monte Carlo methods. However, supporting a multi-spin flip is important to enhance the search performance of SA-based Ising machines when constrained COPs are solved. In this paper, we extend the merge method, which was introduced to provide a multi-spin-flip capability for SA-based Ising machines, and formulate it as a series of matrix multiplications that can be executed on a graphics processing unit (GPU) efficiently. We then construct a GPU-based Ising machine that implements the GPU-oriented merge method together with an extended SA algorithm. We finally demonstrate its superiority over the state-of-the-art GPU-based Ising machine for quadratic knapsack problems.
The binary quadratic knapsack problem (QKP) aims at optimizing a quadratic cost function within a single knapsack. Its applications and difficulty make it appealing for various industrial fields. In this paper we present an efficient strategy to solve the problem by modeling it as an Ising spin model using an Ising machine to search for its ground state which translates to the optimal solution of the problem. Secondly, in order to facilitate the search, we propose a novel technique to visualize the landscape of the search and demonstrate how difficult it is to solve QKP on an Ising machine. Finally, we propose two software solution improvement algorithms to efficiently solve QKP on an Ising machine.
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.
To enhance the performance of quantum annealing machines, several methods have been proposed to reduce the number of spins by fixing spin values through preprocessing. We proposed a hybrid optimization method that combines a simulated annealing (SA)-based non-quantum-type Ising machine with a quantum annealing machine. However, its applicability remains unclear. Therefore, we evaluated the performance of the hybrid method on large-size Ising models and analyzed its characteristics. The results indicate that the hybrid method improves upon solutions obtained by the preprocessing SA, even if the Ising models cannot be embedded in the quantum annealing machine. We analyzed the method from three perspectives: preprocessing, spin-fixed sub-Ising model generation method, and the accuracy of the quantum annealing machine. From the viewpoint of the minimum energy gap, we found that solving the sub-Ising model with a quantum annealing machine results in a higher solution accuracy than solving the original Ising model. Additionally, we demonstrated that the number of fixed spins and the accuracy of the quantum annealing machine affect the dependency of the solution accuracy on the sub-Ising model size.
Ising machines are a promising approach to solve combinatorial optimization problems. They map these problems onto the Ising model and search for low-energy configurations. However, navigating the rugged energy landscapes of these systems remains difficult. To improve this navigation, classical adiabatic annealing has been proposed in the literature as a heuristic optimization method for classical Ising machines. Using this technique, the Hamiltonian of the Ising machine is gradually transformed from an easily solvable Hamiltonian to the target Hamiltonian. However, its purported effectiveness is primarily motivated by an analogy to quantum adiabatic annealing, and systematic benchmarking has remained limited. In this work, we analyze the classical adiabatic annealing technique using continuation methods. Motivated by insights from this analysis, we propose an optimized annealing strategy we refer to as hybrid classical adiabatic annealing. We benchmark our proposed strategy using MaxCut instances with up to 800 spins and problems with external fields, for which it achieves a marginal improvement for a limited set of problems. We conclude that, although theoretically motivated and occasionally beneficial, the hybrid strategy does not offer a sufficient practical advantage over simpler, existing techniques.
Ising machines have the potential to realize fast and highly accurate solvers for combinatorial optimization problems. They are classified based on their internal algorithms. Examples include simulated-annealing-based Ising machines (non-quantum-type Ising machines) and quantum-annealing-based Ising machines (quantum annealers). Herein we propose a hybrid optimization method, which utilizes the advantages of both types. In this hybrid optimization method, the preprocessing step is performed by solving the non-quantum-annealing Ising machine multiple times. Then sub-Ising models with a reduced size by spin fixing are solved using a quantum annealer. The performance of the hybrid optimization method is evaluated via simulations using Simulated Annealing (SA) as a non-quantum-type Ising machine and D-Wave Advantage as a quantum annealer. Additionally, we investigate the parameter dependence of the proposed hybrid optimization method. The hybrid optimization method outperforms the preprocessing SA and the quantum annealing machine alone in fully connected random Ising models.