情報処理学会第 83 回全国大会

2H-03

量子アニーリングマシンにおける組み合わせ最適化問題の適用可能性の調査
大山 基樹†

森下 誠‡

片桐 孝洋‡,§

大島 聡史‡,§

永井 亨§

名古屋大学 情報学部 コンピュータ科学科†
名古屋大学 大学院情報学研究科‡
名古屋大学 報基盤センター§

1. はじめに
量子コンピュータは従来のコンピュータによるアプローチでは実行できない組合せ最適化問題の解を求める事ができる.しかし，現状ではハードウェアやグラフの接続性の制約によって実用的な問題をマッピングする事が出来ない例がある事が知られている．そこで本研究では，
Quadratic Unconstrained Binary Optimization(QUBO) の入力インスタンスを適切に分割し，部分問題にするアプローチによって，大規模問題を効果的に解けるかの調査を行う．またこのアプローチによって巡回セールスマン（travelingsalesman problem, TSP）問題を用いて分割前と後で比較した際，解の精度にどの程度の違いが見られるかを示し，今後の展望としてどういった処理が有効であるかを示す．

2. QuadraticUnconstrainedOptimization (QUBO)

BinaryQUBO 問題とは二次制約なしバイナリ最適化問題であり，制約条件を満たす中で目的関数を最小/最大にする解を求める問題である．この問
題は NP 困難問題であり，計算時間が指数的に長くなってしまうという，いわゆる組み合わせ爆発の問題を抱えている．したがって変数の数が多い場合，近似解法や問題に応じた専用解法を用いる事となる．いま注目を集めている量子アニーリングマシンを始めとしたイジングモデル型情報処理では，解きたい組合せ最適化問題を制約なし 0-1 整数計画問題かつ，２次までの決定変数の項のみの形へ帰着させ，専用マシンで解くという手続きを取る．現状の量子アニーリン
グ方式は組合せ最適化問題に特化しており，対象の問題をイジングモデルで定式化し，マシン上にマッピングする事が出来れば問題を解く事が出来る．イジングモデルとは，正方格子状にInvestigation of applicability of combinatorial optimization
problems in quantum annealing machines† Motoki Oyama, Information system, Computer science, Schoolof Informatics, Nagoya University‡Makoto Morisita, Graduate School of Informatics, Nagoya
University§
Takahiro Katagiri , Satoshi Ohshima, Toru Nagai, Information
Technology Center, Nagoya University

1-35

配置したスピン（+1 or -1）からなる格子モデルである．このモデルにおいては，各スピン同士は磁気的に不均一に相互作用をしており，系の全エネルギーは，式(1)のコスト関数 E で与えられる．
𝑁𝑁E = ∑ ∑ 𝐽𝑖𝑗 𝜎𝑖 𝜎𝑗 − ∑ ℎ𝑖 𝜎𝑖𝑖=1 𝑗≠𝑖

(1)

𝑖=1

ここで N は全スピン数， 𝜎𝑖 = ±1はサイト𝑖のス
ピン変数，𝐽𝑖𝑗 は異なるスピン間の相互作用強度，ℎ𝑖 はサイト𝑖の局所磁場である．つまり，対象の問題に対して対応したイジングモデル(ℎ𝑖 , 𝐽𝑖𝑗 )を構成する．次に，その最低エネルギー状態（スピン配列）を求める事で，組合せ最適化問題の最適解を求める事が出来る．

3. 量子アニーリングの現状の問題点
現状の量子アニーリングマシンの構造としては，ハードウェアやグラフの接続性の制約という問題点がある．現在の量子アニーリングマシンは最大ビット数の制限があり実用的な問題をマッピングする事が出来ない．また，マシンの中では，量子ビット同士が物理的に結合して相互作用を起こしているが，物理空間などの制約がある事から，全ての量子ビットがお互いに結合していないので，解きたい問題によっては物理的な結合の数以上の結合が必要になる場合が存在する．

4. QUBO を部分問題に分割する方法
ここでは対象の問題を部分問題に分割する事
で，より大きな QUBO 問題を解決する方法[1]について述べる．現在このアプローチは qbsolv 等のアルゴリズムで実行している．部分問題に分割する事によって，全体の問題解決の速度に改善が見られる訳ではなく，解の精度が向上するとされている．qbsolv アルゴリズムは古典／量子アルゴリズムによるハイブリッド解法である．
これは量子アニーリングの解の精度に制限があるが，状態空間の様々な領域を探索する事が出来るという利点と，タブーサーチの近傍内の正確な最小値を素早く見つける事が出来るという利点を用いている．つまり量子アニーリングで近傍への移動を行い，タブーサーチで近傍内のCopyright 2021 Information Processing Society of Japan.
All Rights Reserved.

情報処理学会第 83 回全国大会

探索を行う方針である．

5. 予備評価
ここでは，CMOS アニーリングマシンで小規模の TSP 問題を解き，入力インスタンスの分割によってどの程度，解の精度が落ちるか実験した．TSP 問題とは，都市の集合と各２都市間の移動コスト（ここでは距離）が与えられたとき，全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小なものを求める組合せ最適化問題である．
ここでの TSP 問題としては都市数 N=8 の問題を対象とし，その問題を N=4 と N=5 の部分問題に分割し，ある１頂点を両方の頂点部分集合に共通のノードとして，元の解と部分問題を統合した際の解の精度を比較する．分割方法としては，(A)より近い隣接頂点を同じ部分に含む方法；(B)近い隣接頂点を別の部分に含める方法；を用いる．これは一般的に近傍で問題を分割した方が TSP 問題においてはより良い解が得られるからである．
統合方法としては，TSP 問題の回転対称性とスーパーノードの特性より，二つの部分問題の総距離の合計にて行う．また，コスト関数に対してどの程度制約条件を重視するかの指標を示す
パラメータ k に関しては， k=1.0 を用いる.

6. 性能評価の結果
表１に各パターンの総距離の比較を示す．結果から，(A)(B)で，最良・最悪・平均の総距離数が分割前の問題より劣る事がわかる．したがって，問題を分割する事による解の精度の向上は見られないと考えられる．また部分問題に分割する手法を用いる場合は，入力インスタンスを適切に分割しなければ最適解の精度が著しく低下する事がわかる．したがって入力インスタン
スの分割を事前処理としてグラフ分割（GraphPartitioning, GP）問題を定式化して量子アニーリングを用いて解く事で適切な分割の可能性が見込まれる[2]．
表 1 実行結果
最良結果 最悪結果 平均結果
分割なし
86208
153.4(A)分割
128212
162.6(B)分割
190262225.4
一方で，入力インスタンスの分割に成功した場合の利点として，相互作用の値の減少と共にマッピングに必要なグラフのサイズが小さくなる
ため，QUBO 行列のサイズを削減する事が可能である．一般的に制約の強さは，小さい方が良い解が出る傾向にあり，加えて制約の強さの下限

1-36値は，最適解の経路に含まれる都市間の最長距離である事[3]から，k の値をより小さく設定する事が可能である．
表 2 に k の値に関する比較，表 3 に問題サイズによる最適解との差の平均の度合いを示す．
解の精度は k=1.0 の場合が最も良く，問題サイズが大きくなるほど最適解から遠のいている．
したがって部分問題に分割した方がより小さい kを用いる事が可能であり，問題サイズを縮小出来るため，より良い解が得られる可能性があるといえる．
表２ k の値による平均結果
k=1.0
k=2.0
k＝5.0
119.2
156.0
174.8
表３ 問題サイズによる最適解とのずれ
N＝4
N＝5N＝820.77%
170.25%256.88%

7. まとめTSP 問題においては問題を分割する事により解の精度に低下が見られた．しかしながら，分割により k の値と問題サイズを小さくする事が出来るため，大規模な問題サイズの問題に関しては分割後の方が良い解を得る可能性が考えられる．よって入力インスタンスを問題に応じて適切に分割する事が出来ればサイズと接続性の壁を乗り越える事ができ，実用的なビジネス問題への適用も考えられる．今後の展望としては，
GP 問題のアルゴリズムを用いて適切な分割を行う方法を開発し，QUBO 行列のサイズを削減する事がある．またその分割を再帰的に用いる事で，サイズがより大きな問題に量子アニーリン
グを適用させることがあげられる．
参考文献[1]M. Booth, S. P. Reinhardt, and A. Roy,
Partitioning Optimization Problems for HybridClassical/Quantum Execution,14-106A-A,DWave Technical Report Series, 2017, pp.1-14.
[2] H. Ushijima-Mwesigwa, C. F. A. Negre,
Susan M. Mniszewski, “Graph Partitioning
using Quantum Annealing on the D-Wave
System”, arXiv:1705.03082 [quant-ph]. ,2017,
pp. 1-20.
[3] K. Takehara, D. Oku, Y. Matsuda, S.
Tanaka and N. Togawa, "A Multiple
Coefficients Trial Method to Solve
Combinatorial Optimization Problems for
Simulated-annealing- based Ising Machines,"
2019 IEEE 9th International Conference onConsumer Electronics (ICCE-Berlin), Berlin,Germany, 2019, pp. 64-69

Copyright 2021 Information Processing Society of Japan.
All Rights Reserved.