Highly-Parallel FPGA Accelerator for Simulated Quantum Annealing
Highly-Parallel FPGA Accelerator for Simulated Quantum Annealing
复制标题
用于模拟量子退火的高度并行 FPGA 加速器
DOI：
10.1109/tetc.2019.2957177
复制
发表时间：
2019
影响因子：
5.9
通讯作者：
Hariyama Masanori
中科院分区：
文献类型：
--
作者：
Waidyasooriya Hasitha;Hariyama Masanori
量子退火是一种利用量子涨落寻找组合优化问题全局最优解的方法。像d波这样的量子退火炉对于解决少于2048个变量的小问题是有效的。在数字计算机上模拟量子退火使我们能够解决现实世界中的大型问题。然而，处理时间随着变量的数量呈指数增长。本文提出了一种利用空间和时间并行性的高并行模拟量子退火加速器。该加速器在FPGA上采用“开放计算语言（OpenCL）”实现。对于8,192个自旋模型，与单核CPU实现相比，我们在一个FPGA中使用32个trotter实现了145倍的速度，在两个FPGA中使用64个trotter实现了290倍的速度。
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.