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

International Conference on Field-Programmable Technology (FPT)

Stochastic Implementation of Simulated Quantum Annealing on PYNQ

Taiga Kubuta, Duckgyu Shin, Naoya Onizawa, Takahiro Hanyu

Published Dec 12, 2023• 2 citations
Publisher

Abstract

It is well-known that quantum annealing (QA) is an excellent algorithm for solving combinatorial optimization problems (COPs). However, its hardware implementation poses challenges, requiring quantum devices. Therefore, a quantum Monte Carlo (QMC) method-based annealing approach called Simulated Quantum Annealing (SQA), which aims to emulate quantum annealing using classical computers, has been proposed. In the demo-night session, we will demonstrate a SQA based on stochastic computing (SC) on a standard FPGA board, called “PYNQ”. The use of SC-based data representation, along with the realization of SC-based spin-gate circuits, makes it possible to drastically reduce hardware costs compared to QA. This enhances the suitability for extending large-scale COPs.

DOI
10.1109/icfpt59805.2023.00042

Related papers

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

Quantum Annealing via Path-Integral Monte Carlo With Data Augmentation

Jianchang Hu, Yazhen Wang

This article considers quantum annealing in the Ising framework for solving combinatorial optimization problems. The path-integral Monte Carlo simulation approach is often used to approximate quantum annealing and implement the approximation by classical computers, which refers to simulated quantum annealing (SQA). In this article, we introduce a data augmentation scheme into SQA and develop a new algorithm for its implementation. The proposed algorithm reveals new insights on the sampling behaviors in SQA. Theoretical analyses are established to justify the algorithm, and numerical studies are conducted to check its performance and to confirm the theoretical findings. Supplementary materials for this article are available online.

Journal of Computational and Graphical Statistics•Sep 1, 2020•4 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

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

How to Solve Combinatorial Optimization Problems Using Real Quantum Machines: A Recent Survey

Sovanmonynuth Heng, Dongmin Kim, Tae-Kyung Kim +1 more

A combinatorial optimization problem (COP) is the problem of finding the optimal solution in a finite set. When the size of the feasible solution set is large, the complexity of the problem increases, and it is not easy to solve in a reasonable time with the current classical computer technology. Quantum annealing (QA) is a method that replaces classical simulated annealing (SA) methods that do not solve these cases. Therefore, several attempts have been made to solve this problem using a special-purpose quantum annealer to which the QA method is applied. In this survey, we analyze recent studies that solve real-scale COPs using quantum annealers. Through this, we discuss how to reduce the size of the COP to be input to overcome the hardware limitations of the existing quantum annealer. Additionally, we demonstrated the applicability of quantum annealer to COP on a practical scale by comparing and analyzing the results of the classical simulated annealing (SA) and QA method from each study.

IEEE Access•Jan 1, 2022•31 citations

Experimental evaluation of simulated quantum annealing with MTJ-augmented p-bits

Andrea Grimaldi, Kemal Selçuk, Navid Anjum Aadit +8 more

The slowing down of Moore’s Law has created an exciting new era of electronics, leading to the emergence of various types of CMOS+X devices and architectures. Here, we present the first experimental demonstration of a probabilistic computer where a stochastic magnetic tunnel junction (sMTJ) drives a powerful CMOS-based field programmable gate array (FPGA) in a heterogeneous compute fabric. We use our machine to experimentally evaluate the simulated quantum annealing (SQA) algorithm, known to closely mimic the behavior of D-Wave’s quantum annealers which implement the transverse field Ising model (TFIM). Our machine matches the exact solution of the TFIM where p-bits in the FPGA are asynchronously driven by the stochastic dynamics of a magnetic tunnel junction. To compare the performance of SQA against classical annealing (CA) in hard combinatorial optimization at large scale, we also design a fully digital emulator of our asynchronous architecture in the FPGA. Our digital system uses 7,085 p-bits to factor up to 26-bit integers and is about 10X faster than optimized Tensor (TPU) and Graphics Processing Units (GPU) at lower power. Surprisingly, we find that the additional replica networks necessary for SQA do not lead to appreciably better performance over an optimized CA that is using the same computational resources. The systematic evaluation of the SQA algorithm we present will be relevant for other types of accelerators, such as photonic or electronic Ising machines and the integrated scaling of our CMOS + sMTJ architecture could lead to orders of magnitude further improvements over TPU and GPUs, according to experimentally-validated projections.

Technical digest - International Electron Devices Meeting/Technical digest•Dec 3, 2022•31 citations
It is well-known that quantum annealing (QA) is an excellent algorithm for solving combinatorial optimization problems (COPs). However, its hardware implementation poses challenges, requiring quantum devices. Therefore, a quantum Monte Carlo (QMC) method-based annealing approach called Simulated Quantum Annealing (SQA), which aims to emulate quantum annealing using classical computers, has been proposed. In the demo-night session, we will demonstrate a SQA based on stochastic computing (SC) on a standard FPGA board, called “PYNQ”. The use of SC-based data representation, along with the realization of SC-based spin-gate circuits, makes it possible to drastically reduce hardware costs compared to QA. This enhances the suitability for extending large-scale COPs.
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.
This article considers quantum annealing in the Ising framework for solving combinatorial optimization problems. The path-integral Monte Carlo simulation approach is often used to approximate quantum annealing and implement the approximation by classical computers, which refers to simulated quantum annealing (SQA). In this article, we introduce a data augmentation scheme into SQA and develop a new algorithm for its implementation. The proposed algorithm reveals new insights on the sampling behaviors in SQA. Theoretical analyses are established to justify the algorithm, and numerical studies are conducted to check its performance and to confirm the theoretical findings. Supplementary materials for this article are available online.
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.
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.
A combinatorial optimization problem (COP) is the problem of finding the optimal solution in a finite set. When the size of the feasible solution set is large, the complexity of the problem increases, and it is not easy to solve in a reasonable time with the current classical computer technology. Quantum annealing (QA) is a method that replaces classical simulated annealing (SA) methods that do not solve these cases. Therefore, several attempts have been made to solve this problem using a special-purpose quantum annealer to which the QA method is applied. In this survey, we analyze recent studies that solve real-scale COPs using quantum annealers. Through this, we discuss how to reduce the size of the COP to be input to overcome the hardware limitations of the existing quantum annealer. Additionally, we demonstrated the applicability of quantum annealer to COP on a practical scale by comparing and analyzing the results of the classical simulated annealing (SA) and QA method from each study.
The slowing down of Moore’s Law has created an exciting new era of electronics, leading to the emergence of various types of CMOS+X devices and architectures. Here, we present the first experimental demonstration of a probabilistic computer where a stochastic magnetic tunnel junction (sMTJ) drives a powerful CMOS-based field programmable gate array (FPGA) in a heterogeneous compute fabric. We use our machine to experimentally evaluate the simulated quantum annealing (SQA) algorithm, known to closely mimic the behavior of D-Wave’s quantum annealers which implement the transverse field Ising model (TFIM). Our machine matches the exact solution of the TFIM where p-bits in the FPGA are asynchronously driven by the stochastic dynamics of a magnetic tunnel junction. To compare the performance of SQA against classical annealing (CA) in hard combinatorial optimization at large scale, we also design a fully digital emulator of our asynchronous architecture in the FPGA. Our digital system uses 7,085 p-bits to factor up to 26-bit integers and is about 10X faster than optimized Tensor (TPU) and Graphics Processing Units (GPU) at lower power. Surprisingly, we find that the additional replica networks necessary for SQA do not lead to appreciably better performance over an optimized CA that is using the same computational resources. The systematic evaluation of the SQA algorithm we present will be relevant for other types of accelerators, such as photonic or electronic Ising machines and the integrated scaling of our CMOS + sMTJ architecture could lead to orders of magnitude further improvements over TPU and GPUs, according to experimentally-validated projections.