近年、組合せ最適化問題の高効率解法として期待されている量子アニーリングをはじめとしたイジングマシンが注目を集めている。イジングマシンで組合せ最適化問題を解く際には、組合せ最適化問題の目的関数ならび制約条件をイジングモデルのエネルギー関数で表現し、基底状態(エネルギー最小状態)を探索する。イジングマシンによって動作原理が異なり、その動作原理に基づくイジングモデルの設計やハイパーパラメータの調整を行うことによって、イジングマシンの性能を最大限引き出す計算処理が可能となる。
本研究課題では、大きく分けて以下の3つのトピックに関して研究を行った。(1)量子アニーリングの性能を引き出す量子ゆらぎの導入方法の検討、(2)イジングマシンにおけるハイパーパラメータ調整法の検討、(3)イジングマシンの応用探索
(1)では、ランダムな大きさの相互作用を持つ1次元イジングスピンモデルに対する量子アニーリングの性能を統計力学の知見に基づき検討した。相互作用のランダムネスに対応したランダムな横磁場を印加することで、量子アニーリングの性能が高まることが示された。この成果については現在論文投稿中である(プレプリント版は、arXiv:2007.07439に掲載)。(2)では、いくつかのイジングマシンにおいて必須の「埋め込みアルゴリズム」におけるハイパーパラメータの調整方法について統計力学シミュレーション(モンテカルロシミュレーション)に基づき解析を行った。この成果についてはIEEE Accessに掲載された。また、いくつかのイジングマシンにおいて必要なビット幅削減についてもまとめIEEE Transactions on Computersに掲載された。(3)では、部分グラフ検出ならびにスロット配置問題と呼ばれる具体的な組合せ最適化問題に対してイジングマシンを用いる方法を考案し、実際のイジングマシンで計算処理を行った結果をまとめた。ともに、IEICE Transactions on Information and Systemsに掲載された。
In recent years, Ising machines such as quantum annealing, which is expected to be a highly efficient solution method for combinatorial optimization problems, have attracted much attention. When solving a combinatorial optimization problem with an Ising machine, the combinatorial optimization problem's objective function and constraints are expressed by the energy function of the Ising model, and the ground state (minimum energy state) is searched. Each Ising machine has a different operating principle, and by designing an Ising model based on the operating principle and adjusting the hyperparameters, it is possible to perform computational processing that maximizes the Ising machine's performance.
In this research project, we have studied the following three major topics. In this research project, we studied the following three topics: (1) how to introduce quantum fluctuations to maximize the performance of quantum annealing, (2) how to tune hyperparameters in Ising machines, and (3) how to explore applications of Ising machines.
In (1), the performance of quantum annealing for a one-dimensional Ising spin model with randomly sized interactions was investigated based on the knowledge of statistical mechanics. It is shown that quantum annealing performance is enhanced by applying a random transverse magnetic field corresponding to the randomness of the interaction. This result is now under submission for publication (preprint version is available at arXiv:2007.07439). In (2), we analyzed how to tune the hyperparameters in the "embedding algorithm," which is essential for some Ising machines, based on statistical mechanics simulation (Monte Carlo simulation). This result was published in IEEE Access. We also summarized the bit-width reduction required for some Ising machines and published it in IEEE Transactions on Computers. In (3), we devised a method using an Ising machine for a specific combinatorial optimization problem called the subgraph detection and slot placement problem and summarized the computational processing results on an actual Ising machine. Both papers were published in IEICE Transactions on Information and Systems.
|