IEEE Transactions on Emerging Topics in Computing

Highly-Parallel FPGA Accelerator for Simulated Quantum Annealing

Hasitha Muthumala Waidyasooriya, Masanori Hariyama

Published Dec 2, 2019• 40 citations

Abstract

Quantum annealing (QA) is a method to find the global optimum of a combinatorial optimization problem by using quantum fluctuations. Quantum annealers such as D-wave are efficient to solve small problems with less than 2048 variables. Simulated quantum annealing on digital computers allows us to solve large real-world problems. However, the processing time increases exponentially with the number of variables. This article proposes a highly-parallel accelerator for simulated quantum annealing exploiting spatial and temporal parallelism. The accelerator is implemented using “open computing language (OpenCL)” on FPGA. For 8,192 spin models, we achieve 145 times speed using 32 Trotters in one FPGA and 290 times speed-up using 64 Trotters in two FPGAs, compared to single-core CPU implementation.

DOI: 10.1109/tetc.2019.2957177

Related papers

Accelerator Architecture for Simulated Quantum Annealing Based on Resource-Utilization-Aware Scheduling and its Implementation Using OpenCL

Hasitha Muthumala Waidyasooriya, Yusuke Araki, Masanori Hariyama

Quantum annealing (QA) is used to find the global optimum for combinatorial optimization problems. QA can be simulated on a computer using quantum Monte Carlo (QMC) simulation while spending a huge processing time. We propose a custom architecture to accelerate simulated QA. The proposed architecture is implemented using “open computing language (OpenCL)” on an Intel Aria10 FPGA. It is possible to design the most appropriate architecture for different optimization problems by changing the design parameters of the OpenCL code. We achieved over 1.94 times speed-up compared to CPU-based implementation.

International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)Nov 1, 20189 citations

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, 20221 citation

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 NetworkingNov 1, 201910 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 AccessJan 1, 202022 citations

A Parallel Hardware Architecture For Quantum Annealing Algorithm Acceleration

Evelina Forno, Andrea Acquaviva, Yuki Kobayashi +2 more

Quantum Annealing (QA) is an emerging technique, derived from Simulated Annealing, providing metaheuristics for multivariable optimisation problems. Studies have shown that it can be applied to solve NP-hard problems with faster convergence and better quality of result than other traditional heuristics, with potential applications in a variety of fields, from transport logistics to circuit synthesis and optimisation. In this paper, we present a hardware architecture implementing a QA-based solver for the Multidimensional Knapsack Problem, designed to improve the performance of the algorithm by exploiting parallelised computation. We synthesised the architecture using as a target an Altera FPGA board and simulated the execution for solving a set of benchmarks available in the literature. Simulation results show that the proposed implementation is about 100 times faster than a single-thread general-purpose CPU without impact on the accuracy of the solution.

IFIP/IEEE International Conference on Very Large Scale IntegrationOct 1, 20189 citations

Multi-FPGA Acceleration of Simulated Quantum Annealing for Route Optimization in Commercial AGV Operating Systems

Thinh NGUYEN QUANG, Kosuke Matsuyama, Keisuke Shimizu +11 more

Improving the efficiency, safety, and speed of large-scale Automated Guided Vehicle (AGV) systems is crucial for enhancing the productivity of logistics warehouses. Recent advancements in quantum annealing devices have demonstrated the potential to optimize AGV routing effectively. However, applying quantum annealing to complex and large-scale AGV routing problems remains challenging due to insufficient consideration of operational constraints and the limited number of qubits available in current quantum annealers. To address these challenges, this study proposes a new formulation for large-scale AGV routing by introducing a priority constant to reduce delays caused by constraint violations. Additionally, we develop a system architecture that employs multiple FPGAs to accelerate Simulated Quantum Annealing (SQA), thereby overcoming the computational inefficiencies of classical SQA implementations. The proposed architecture is designed to solve large-scale optimization problems involving tens of thousands of variables. Each FPGA board can process problems with up to 50,176 variables, and a five-FPGA parallel configuration achieves significantly faster processing speeds. The performance of the proposed system is validated using a commercial AGV Operating System (AOS), including experiments with real AGVs in a small-scale environment and simulations involving up to 1,000 AGVs. Experimental results demonstrate that the proposed SQA accelerator achieves faster processing speeds and higher-quality solutions compared to existing SQA solvers, confirming its effectiveness for large-scale AGV route optimization.

IEEE AccessJan 1, 20260 citations