組合せ的前処理と量子アニーリングの融合による行列計算の加速手法

近年，量子アニーリングが注目を集めている．量子アニーリングは，量子揺らぎを利用した物理過程によって最適化問題の解を求める手法であり，様々な組合せ最適化問題を高速に解けると期待されている．量子アニーリングマシンは，ゲート型の量子計算機に比べて大規模化が容易であり，例えばD-Wave社2000Qシステムでは，0-1変数で最大2000変数を持つ組合せ最適化問題（0-1変数無制約2次計画問題）の求解が可能である．本研究では，量子アニーリングマシンと古典計算機を組み合わせたハイブリッド環境により，行列の対角化（固有値計算）や連立１次方程式の求解などの応用上重要な行列計算を加速することを目的としている．そのための手法として，本研究では組合せ的前処理と量子アニーリングを融合する．多くの行列計算アルゴリズムは，行列要素の絶対値の分布や非ゼロ要素の分布により，収束性や計算量が大きく変化する．そこで，行と列の置換などの組合せ的前処理により，これらの分布を対象アルゴリズムの特性に合わせて最適化すれば，収束性の向上や計算量の減少が見込める．今年度の研究では，実対称行列向けの固有値解法であるブロックヤコビ法を対象として，効率的な組合せ的前処理の設計と評価を行った．具体的には，ブロックヤコビ法における非対角ブロックの消去前に，行と列の置換により，絶対値の大きい要素を対角ブロックに集中させ，消去が効率的に行えるようにした．本前処理を組合せ最適化問題として定式化し，量子アニーリングマシンD-WAVE Advantage上で実装して12×12程度の小規模行列に適用したところ，絶対値の大きい要素の対角ブロックへの集中が正しく行えることを確認した．

近年，量子アニーリングが注目を集めている．量子アニーリングは，量子揺らぎを利用した物理過程によって最適化問題の解を求める手法であり，様々な組合せ最適化問題を高速に解けると期待されている．量子アニーリングマシンは，ゲート型の量子計算機に比べて大規模化が容易であり，例えばD-Wave社2000Qシステムでは，0-1変数で最大2000変数を持つ組合せ最適化問題（0-1変数無制約2次計画問題）の求解が可能である．本研究では，量子アニーリングマシンと古典計算機を組み合わせたハイブリッド環境により，行列の対角化（固有値計算）や連立１次方程式の求解などの応用上重要な行列計算を加速することを目的としている．そのための手法として，本研究では組合せ的前処理と量子アニーリングを融合する．多くの行列計算アルゴリズムは，行列要素の絶対値の分布や非ゼロ要素の分布により，収束性や計算量が大きく変化する．そこで，行と列の置換などの組合せ的前処理により，これらの分布を対象アルゴリズムの特性に合わせて最適化すれば，収束性の向上や計算量の減少が見込める．今年度の研究では，実対称行列向けの固有値解法であるブロックヤコビ法を対象として，効率的な組合せ的前処理の設計と評価を行った．具体的には，ブロックヤコビ法における非対角ブロックの消去前に，行と列の置換により，絶対値の大きい要素を対角ブロックに集中させ，消去が効率的に行えるようにした．本前処理を組合せ最適化問題として定式化し，量子アニーリングマシンD-WAVE Advantage上で実装して12×12程度の小規模行列に適用したところ，絶対値の大きい要素の対角ブロックへの集中が正しく行えることを確認した．