FPGAリソースを考慮した量子アニーリングのトロッタ間並列処理手法

種々の組合せ最適化問題の解法に用いられる量子アニーリングの高速化は重要な課題である．ここでは，量子モンテカルロ法に基づく疑似量子アニーリング（SQA，Simulated Quantum Annealing）の FPGA を用いた並列化エミュレーションにおいて，FPGA のリソースを考慮した並列化手法を示す．FPGA のリソースで実現可能な並列数に応じて，スピン変数のトグル処理をトロッタ単位で並列数分の処理単位に分割する．各処理単位のスピンのトグル処理は独立に行われる．メルセンヌツイスタ法による乱数計算と，隣接するトロッタの情報を組み込むことによってスピン間の相互依存関係を克服し，直列処理の場合と同等の精度でハードウェアのリソースに合わせた並列処理を可能とした．

Quantum annealing is a new algorithm to solve combinatorial optimization problems where the original problem is converted to the energy minimization of Ising model or the equivalent QUBO (Quadratic Unconstrained Binary Optimization). Speeding up quantum annealing is important to obtain the solutions of combinatorial optimization problems in short time. In this manuscript, an acceleration method of simulated quantum annealing (SQA) based on the quantum Monte Carlo method is presented for FPGA platforms. The method takes into account the resources of the FPGA. Toggles of spin variables are parallelized trotter by trotter depending on the usable FPGA resource. By using the Mersenne twistor method to compute random numbers and by incorporating information about neighboring trotters, proposed parallel processing can obtain the same accuracy as in the case of serial processing. The proposed method gains more than 20 times speed-up compared with a serial execution of hardware on 32 trotter case.