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 International Conference on Integrated Circuits, Technologies and Applications (ICTA)

A Genuine-Equilibrium Monte Carlo Sampling-Based Effective Algorithm for Fully-Connected Ising Models

Xiangrui Wang, Dong Jiang, Yang Zhang, Hongyuan Kang, Enyi Yao

Published Oct 27, 2023• 3 citations
Publisher

Abstract

Ising machines have emerged as a potential technique for hardware acceleration in solving combinatorial optimization problems. However, an effective and hardware-implementation-friendly algorithm is still required to further enhance the fully-connected Ising machine's performance. Parallel momentum-tempering (PMT) algorithm is proposed in this paper, incorporating the full parallel updating capability of momentum annealing (MA) with the global exploration in the solution space provided by parallel tempering (PT). PMT exhibits an excellent performance, and a PMT with 8 replicas surpasses MA on the WK2000 max-cut benchmark, achieving a considerable 80%(1k/6k) reduction in required iteration steps while obtaining a mean cut value of 33,160. Besides, PMT is well-matched for hardware implementation versus MA, benefiting from invariant parameters in each replica.

DOI
10.1109/icta60488.2023.10364257

Related papers

GPU-based Ising Machine for Solving Combinatorial Optimization Problems with Enhanced Parallel Tempering Techniques

Kuei-Po Huang, Chin-Fu Nien, Yun-Ting Zhang +2 more

Ising machines (IMs) are hardware solvers designed to tackle computationally complex combinatorial optimization problems (COPs), harnessing physical processes such as quantum annealing to simulate the Ising model, enabling these specially designed solvers to tackle a wide range of computationally complex NP-hard problems in real-world applications, such as portfolio optimization and logistics planning. While prior works propose to fabricate dedicated integrated circuits for building IMs, we leverage off-the-shelf Graphics Processing Unit (GPU) chips for implementing Ising algorithms for quick development. In this work, we explore parallel tempering (PT), an Ising algorithm, which shows promise owing to its capability for parallel processing of multiple independent searches for the optimal solution, each with a different amount of randomness that allows escaping local minima. We propose several optimization strategies, including addressing the dependency problem in PT to enhance algorithm parallelism and integrating genetic algorithm (GA)-like operations to increase the diversity of the search process for effective solution discovery. Empirical evaluations demonstrate that our proposed Parallel Quantum-inspired Search (PQS) solver achieves a $2.66 \times$ speedup over the state-of-the-art GPU-based solution without sacrificing solution quality.

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS)•Nov 7, 2024•3 citations

Solving traveling salesman problems via a parallel fully connected ising machine

Qichao Tao, Jie Han

Annealing-based Ising machines have shown promising results in solving combinatorial optimization problems. As a typical class of these problems, however, traveling salesman problems (TSPs) are very challenging to solve due to the constraints imposed on the solution. This article proposes a parallel annealing algorithm for a fully connected Ising machine that significantly improves the accuracy and performance in solving constrained combinatorial optimization problems such as the TSP. Unlike previous parallel annealing algorithms, this improved parallel annealing (IPA) algorithm efficiently solves TSPs using an exponential temperature function with a dynamic offset. Compared with digital annealing (DA) and momentum annealing (MA), the IPA reduces the run time by 44.4 times and 19.9 times for a 14-city TSP, respectively. Large scale TSPs can be more efficiently solved by taking a k-medoids clustering approach that decreases the average travel distance of a 22-city TSP by 51.8% compared with DA and by 42.0% compared with MA. This approach groups neighboring cities into clusters to form a reduced TSP, which is then solved in a hierarchical manner by using the IPA algorithm.

ACM/IEEE Design Automation Conference (DAC)•Jul 10, 2022•21 citations

Binary optimization by momentum annealing

Takuya Okuyama, Tomohiro Sonobe, Ken‐ichi Kawarabayashi +1 more

One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.

Physical review. E•Jul 10, 2019•92 citations

Make life simple: unleash the full power of the parallel tempering algorithm

Elmar Bittner, Andreas Nußbaumer, Wolfhard Janke E

We introduce a new update scheme to systematically improve the efficiency of parallel tempering Monte Carlo simulations by taking into account the temperature dependence of autocorrelation times.In contrast to previous attempts the temperatures are not dynamically adjusted but chosen in such a way that the acceptance rate for proposed exchanges of all adjacent replica is about 50%.We show that by adapting the number of sweeps between the parallel tempering moves to the canonical autocorrelation time, the average round-trip time of a replica between the lowest and the highest temperatures is significantly decreased and, therefore, the efficiency of the parallel tempering algorithm is considerably improved.We illustrate the new algorithm with results for the two-dimensional Ising model and propose a toy model to find the optimal parameter set for the parallel tempering routine within no time.

International Symposium on Lattice Field Theory (LATTICE)•Jun 23, 2010•0 citations

Accelerating the Max-Cut Problems via Distributed Ising Machine Solvers

Xing-Yu Wu, Yi-Xin Zhang, Chen-rui Fan +1 more

The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.

IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations

Efficient Implementation of Parallel Annealing Method with Heisenberg Model

Kazuma Kanai, T. Kawahara

Annealing processors that can quickly solve combinatorial optimization problems (COPs) are attracting attention. They solve COPs by converting them into spin-spin interactions and external fields of the Ising model. Annealing processors that use fully-coupled spin coupling can solve a wide range of COPs. However, it is difficult to execute parallel annealing in fully-coupled spin coupling because one spin is updated by referring to all the other spins. In this paper, we proposed multi-state pseudo annealing (MSPA), which is an annealing method for changing the spin value from a conventional binary to a multi state that takes into account intermediate states. In a software validation, we solved the Maxcut problem and the traveling salesman problem and confirmed that the proposed method improves the solution quality in parallel annealing compared with simulated annealing and pseudo annealing. In addition, we implemented MSPA on a field-programmable gate array as a 1024 -spin 16 -parallel system using a scalable structure. With the proposed system, we solved the Max-cut problem and confirmed that it achieves a 9.40 times faster solving speed and yields a 1% larger Max-cut value compared with the conventional parallelized annealing processors.

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS)•Nov 7, 2024•2 citations
Ising machines have emerged as a potential technique for hardware acceleration in solving combinatorial optimization problems. However, an effective and hardware-implementation-friendly algorithm is still required to further enhance the fully-connected Ising machine's performance. Parallel momentum-tempering (PMT) algorithm is proposed in this paper, incorporating the full parallel updating capability of momentum annealing (MA) with the global exploration in the solution space provided by parallel tempering (PT). PMT exhibits an excellent performance, and a PMT with 8 replicas surpasses MA on the WK2000 max-cut benchmark, achieving a considerable 80%(1k/6k) reduction in required iteration steps while obtaining a mean cut value of 33,160. Besides, PMT is well-matched for hardware implementation versus MA, benefiting from invariant parameters in each replica.
Ising machines (IMs) are hardware solvers designed to tackle computationally complex combinatorial optimization problems (COPs), harnessing physical processes such as quantum annealing to simulate the Ising model, enabling these specially designed solvers to tackle a wide range of computationally complex NP-hard problems in real-world applications, such as portfolio optimization and logistics planning. While prior works propose to fabricate dedicated integrated circuits for building IMs, we leverage off-the-shelf Graphics Processing Unit (GPU) chips for implementing Ising algorithms for quick development. In this work, we explore parallel tempering (PT), an Ising algorithm, which shows promise owing to its capability for parallel processing of multiple independent searches for the optimal solution, each with a different amount of randomness that allows escaping local minima. We propose several optimization strategies, including addressing the dependency problem in PT to enhance algorithm parallelism and integrating genetic algorithm (GA)-like operations to increase the diversity of the search process for effective solution discovery. Empirical evaluations demonstrate that our proposed Parallel Quantum-inspired Search (PQS) solver achieves a 2.66×2.66 \times2.66× speedup over the state-of-the-art GPU-based solution without sacrificing solution quality.
Annealing-based Ising machines have shown promising results in solving combinatorial optimization problems. As a typical class of these problems, however, traveling salesman problems (TSPs) are very challenging to solve due to the constraints imposed on the solution. This article proposes a parallel annealing algorithm for a fully connected Ising machine that significantly improves the accuracy and performance in solving constrained combinatorial optimization problems such as the TSP. Unlike previous parallel annealing algorithms, this improved parallel annealing (IPA) algorithm efficiently solves TSPs using an exponential temperature function with a dynamic offset. Compared with digital annealing (DA) and momentum annealing (MA), the IPA reduces the run time by 44.4 times and 19.9 times for a 14-city TSP, respectively. Large scale TSPs can be more efficiently solved by taking a k-medoids clustering approach that decreases the average travel distance of a 22-city TSP by 51.8% compared with DA and by 42.0% compared with MA. This approach groups neighboring cities into clusters to form a reduced TSP, which is then solved in a hierarchical manner by using the IPA algorithm.
One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.
We introduce a new update scheme to systematically improve the efficiency of parallel tempering Monte Carlo simulations by taking into account the temperature dependence of autocorrelation times.In contrast to previous attempts the temperatures are not dynamically adjusted but chosen in such a way that the acceptance rate for proposed exchanges of all adjacent replica is about 50%.We show that by adapting the number of sweeps between the parallel tempering moves to the canonical autocorrelation time, the average round-trip time of a replica between the lowest and the highest temperatures is significantly decreased and, therefore, the efficiency of the parallel tempering algorithm is considerably improved.We illustrate the new algorithm with results for the two-dimensional Ising model and propose a toy model to find the optimal parameter set for the parallel tempering routine within no time.
The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.
Annealing processors that can quickly solve combinatorial optimization problems (COPs) are attracting attention. They solve COPs by converting them into spin-spin interactions and external fields of the Ising model. Annealing processors that use fully-coupled spin coupling can solve a wide range of COPs. However, it is difficult to execute parallel annealing in fully-coupled spin coupling because one spin is updated by referring to all the other spins. In this paper, we proposed multi-state pseudo annealing (MSPA), which is an annealing method for changing the spin value from a conventional binary to a multi state that takes into account intermediate states. In a software validation, we solved the Maxcut problem and the traveling salesman problem and confirmed that the proposed method improves the solution quality in parallel annealing compared with simulated annealing and pseudo annealing. In addition, we implemented MSPA on a field-programmable gate array as a 1024 -spin 16 -parallel system using a scalable structure. With the proposed system, we solved the Max-cut problem and confirmed that it achieves a 9.40 times faster solving speed and yields a 1% larger Max-cut value compared with the conventional parallelized annealing processors.