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 Rebooting Computing (ICRC)

An Ising Computer Based on Simulated Quantum Annealing by Path Integral Monte Carlo Method

Takuya Okuyama, Masato Hayashi, Masanao Yamaoka

Published Nov 1, 2017• 47 citations
Publisher

Abstract

In the near future, one of the main processes is solving large combinatorial optimization problems. However, the performance growth of von Neumann architecture will slow due to the end of semiconductor scaling. To resolve this problem, we propose an Ising computer that maps the optimization problems to the ground state search of Ising models. We previously proposed a computer that finds the ground state of Ising models by simulated annealing (SA) approximately. Though the solution quality of the previous prototype is comparable to that of SA, enhancing the solution quality will be required to solve real-world applications. In this paper, we present our FPGA-based Ising computer that executes simulated quantum annealing by using a path integral quantum Monte Carlo method for Ising models on a 48-by-48 king graph with 8-bit couplings. We also propose a shared random number supply, which contributes to decrease the number of random number generators to two. Experimental results indicate that the proposed Ising computer is more than 15 times faster to obtain 99.9%-solution with a probability of 99% than SA running on a state-of-the-art CPU.

DOI
10.1109/icrc.2017.8123652

Related papers

FPGA-Based Prototype of a Quantum Annealing Simulator for Sparse Ising Model

Hasitha Muthumala Waidyasooriya, Yuta Ohma, Masanori Hariyama

Quantum annealing (QA) is a probabilistic approx-imation method to find the global optimum of a combinatorial optimization problem. QA is done on quantum annealers such as D-wave using quantum properties. Since the number of qubits in quantum annealers is limited, it is difficult to use those to solve large-scale real-world problems. Therefore, quantum annealing simulation on digital computers is necessary. In this paper, we discuss an FPGA based quantum annealing simulator for sparse Ising model. Unlike a fully-connected Ising model, the number of connections among spins in sparse model is limited. Highly sparse Ising models require significantly low amount of computations while allowing more parallel operations. One the other hand, sparsity and the connections among spins are not the same for different Ising models, and it is difficult to propose one specific accelerator architecture for all. We propose a method to automatically generate an application specific accelerator archi-tecture for a given sparse Ising model. The proposed accelerator fully exploits the parallelism to increase the processing speed. We design an FPGA prototype of the proposed accelerator and confirmed the correct behavior. In future, we expect to extend the proposed method to execute large quantum annealing simulations using multiple FPGAs.

IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)•Dec 1, 2022•1 citation

Simulated Ising Annealing Algorithm with Gaussian Augmented Hamiltonian Monte Carlo

Langyu Li, Hao Wang, Zhixin Xie +3 more

A numerical technique called Simulated Ising Annealing (SIA) uses digital computers to obtain approximations of the ground states of Ising models. The quadratic unconstrained binary optimization (QUBO) problem in combinatorial optimization, which is challenging to solve through exhaustive search, has significant linkages to the Ising model. Therefore, SIA's main objective is to identify a better solution in finite iterations. In order to enhance the performance of the simulated annealing procedure, we adopt a Gaussian augmented Hamiltonian Monte Carlo (GAHMC) method in this study. We contrasted our algorithm with Gibbs sampling and local quantum annealing method. Finally, we discuss its application on QUBO problem.

Chinese Control Conference (CCC)•Jul 24, 2023•2 citations

Data-Transfer-Bottleneck-Less Architecture for FPGA-Based Quantum Annealing Simulation

Chia-Yin Liu, Hasitha Muthumala Waidyasooriya, Masanori Hariyama

Quantum Annealing (QA) is a classical probabilistic algorithm that provides a heuristic to find the globally optimal solution for a combinatorial optimization problem by using quantum tunneling processes. Quantum annealing simulation can be implemented on Field Programmable Gate Arrays (FPGAs) using Quantum Monte Carlo (QMC) simulation in the transverse Ising model. Since input data of the QMC simulation increases exponentially with the problem size, we have to use the DRAM of an FPGA board to store these data. However, storing data in DRAM causes two problems. One is the limited data access bandwidth, and the other is the limitation of DRAM capacity. We propose a data-transfer-bottleneck-less FPGA-based accelerator for quantum annealing simulation and apply it to implement number partitioning problem, which is one of the combinatorial optimization problems. The critical idea of our architecture is not storing but computing the large data in FPGA kernels and eliminating the burden on data transfer. We implement the proposed architecture on Stratix 10 FPGA and achieve up to 39.6 times speed-up compared to CPU-based quantum annealing simulation. We also achieve up to 2.8 times speed-up and implement 262,144 spins, which is 64 times increase compared to the most recent FPGA implementation.

International Symposium on Computing and Networking•Nov 1, 2019•10 citations

Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems

Naoya Onizawa, Ryoma Sasaki, Duckgyu Shin +2 more

Combinatorial optimization problems are frequently classified as NP-hard, which means that the time needed to find the optimal solution generally increases exponentially with the problem size. However, the existing research gap highlights the necessity to develop combinatorial optimization methods capable of scaling to large problems while maintaining low solution latency. In this paper, we introduce stochastic simulated quantum annealing (SSQA) for fast solution of combinatorial optimization problems. SSQA is designed based on stochastic computing, which can simulate quantum annealing (QA) by using multiple replicas of spins (probabilistic bits) in classical computing. The use of stochastic computing leads to an efficient parallel spin-state update algorithm, enabling quick search for a solution around the global minimum energy. Therefore, SSQA realizes quantum-like annealing for large-scale problems and can handle fully connected models in combinatorial optimization, unlike QA. The proposed method is evaluated in MATLAB on graph isomorphism problems, which are typical combinatorial optimization problems. It can handle a 100-times larger problem size compared to QA and a 25-times larger problem size compared to a traditional SA method, respectively, for similar convergence probabilities. The time to solution of SSQA is 11.5 times and 423 times smaller than that of the conventional stochastic simulated annealing method and traditional SA, respectively, when solving a 2,025-node combinatorial optimization problem.

arXiv:2302.12454•IEEE Access•Jan 1, 2024•8 citations

A GPU-Based Quantum Annealing Simulator for Fully-Connected Ising Models Utilizing Spatial and Temporal Parallelism

Hasitha Muthumala Waidyasooriya, Masanori Hariyama

Simulated quantum annealing (SQA) is a probabilistic approximation method to find a solution for a combinatorial optimization problem using digital computers. The processing time of SQA increases exponentially with the number of variables. Therefore, acceleration of SQA is regarded as a very important topic. However, parallel implementation is difficult due to the serial nature of the quantum Monte Carlo algorithm used in SQA. In this paper, we propose a method to implement SQA in parallel on a GPU while preserving the data dependency. According to the experimental results, we have achieved over 97 times speed-up while maintaining the same accuracy-level compared to a single-core CPU implementation.

IEEE Access•Jan 1, 2020•22 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
In the near future, one of the main processes is solving large combinatorial optimization problems. However, the performance growth of von Neumann architecture will slow due to the end of semiconductor scaling. To resolve this problem, we propose an Ising computer that maps the optimization problems to the ground state search of Ising models. We previously proposed a computer that finds the ground state of Ising models by simulated annealing (SA) approximately. Though the solution quality of the previous prototype is comparable to that of SA, enhancing the solution quality will be required to solve real-world applications. In this paper, we present our FPGA-based Ising computer that executes simulated quantum annealing by using a path integral quantum Monte Carlo method for Ising models on a 48-by-48 king graph with 8-bit couplings. We also propose a shared random number supply, which contributes to decrease the number of random number generators to two. Experimental results indicate that the proposed Ising computer is more than 15 times faster to obtain 99.9%-solution with a probability of 99% than SA running on a state-of-the-art CPU.
Quantum annealing (QA) is a probabilistic approx-imation method to find the global optimum of a combinatorial optimization problem. QA is done on quantum annealers such as D-wave using quantum properties. Since the number of qubits in quantum annealers is limited, it is difficult to use those to solve large-scale real-world problems. Therefore, quantum annealing simulation on digital computers is necessary. In this paper, we discuss an FPGA based quantum annealing simulator for sparse Ising model. Unlike a fully-connected Ising model, the number of connections among spins in sparse model is limited. Highly sparse Ising models require significantly low amount of computations while allowing more parallel operations. One the other hand, sparsity and the connections among spins are not the same for different Ising models, and it is difficult to propose one specific accelerator architecture for all. We propose a method to automatically generate an application specific accelerator archi-tecture for a given sparse Ising model. The proposed accelerator fully exploits the parallelism to increase the processing speed. We design an FPGA prototype of the proposed accelerator and confirmed the correct behavior. In future, we expect to extend the proposed method to execute large quantum annealing simulations using multiple FPGAs.
A numerical technique called Simulated Ising Annealing (SIA) uses digital computers to obtain approximations of the ground states of Ising models. The quadratic unconstrained binary optimization (QUBO) problem in combinatorial optimization, which is challenging to solve through exhaustive search, has significant linkages to the Ising model. Therefore, SIA's main objective is to identify a better solution in finite iterations. In order to enhance the performance of the simulated annealing procedure, we adopt a Gaussian augmented Hamiltonian Monte Carlo (GAHMC) method in this study. We contrasted our algorithm with Gibbs sampling and local quantum annealing method. Finally, we discuss its application on QUBO problem.
Quantum Annealing (QA) is a classical probabilistic algorithm that provides a heuristic to find the globally optimal solution for a combinatorial optimization problem by using quantum tunneling processes. Quantum annealing simulation can be implemented on Field Programmable Gate Arrays (FPGAs) using Quantum Monte Carlo (QMC) simulation in the transverse Ising model. Since input data of the QMC simulation increases exponentially with the problem size, we have to use the DRAM of an FPGA board to store these data. However, storing data in DRAM causes two problems. One is the limited data access bandwidth, and the other is the limitation of DRAM capacity. We propose a data-transfer-bottleneck-less FPGA-based accelerator for quantum annealing simulation and apply it to implement number partitioning problem, which is one of the combinatorial optimization problems. The critical idea of our architecture is not storing but computing the large data in FPGA kernels and eliminating the burden on data transfer. We implement the proposed architecture on Stratix 10 FPGA and achieve up to 39.6 times speed-up compared to CPU-based quantum annealing simulation. We also achieve up to 2.8 times speed-up and implement 262,144 spins, which is 64 times increase compared to the most recent FPGA implementation.
Combinatorial optimization problems are frequently classified as NP-hard, which means that the time needed to find the optimal solution generally increases exponentially with the problem size. However, the existing research gap highlights the necessity to develop combinatorial optimization methods capable of scaling to large problems while maintaining low solution latency. In this paper, we introduce stochastic simulated quantum annealing (SSQA) for fast solution of combinatorial optimization problems. SSQA is designed based on stochastic computing, which can simulate quantum annealing (QA) by using multiple replicas of spins (probabilistic bits) in classical computing. The use of stochastic computing leads to an efficient parallel spin-state update algorithm, enabling quick search for a solution around the global minimum energy. Therefore, SSQA realizes quantum-like annealing for large-scale problems and can handle fully connected models in combinatorial optimization, unlike QA. The proposed method is evaluated in MATLAB on graph isomorphism problems, which are typical combinatorial optimization problems. It can handle a 100-times larger problem size compared to QA and a 25-times larger problem size compared to a traditional SA method, respectively, for similar convergence probabilities. The time to solution of SSQA is 11.5 times and 423 times smaller than that of the conventional stochastic simulated annealing method and traditional SA, respectively, when solving a 2,025-node combinatorial optimization problem.
Simulated quantum annealing (SQA) is a probabilistic approximation method to find a solution for a combinatorial optimization problem using digital computers. The processing time of SQA increases exponentially with the number of variables. Therefore, acceleration of SQA is regarded as a very important topic. However, parallel implementation is difficult due to the serial nature of the quantum Monte Carlo algorithm used in SQA. In this paper, we propose a method to implement SQA in parallel on a GPU while preserving the data dependency. According to the experimental results, we have achieved over 97 times speed-up while maintaining the same accuracy-level compared to a single-core CPU implementation.
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.