T-QARD Harbor

クラスタリングとは、教師無し学習の一つで、類似した特徴を持ったデータが同じグループに属するようにグループ分けすることを言います。主な手法にk-meansや階層型クラスタリングがありますが、これらは局所探索法であるため厳密解に到達する保証がありません。一方で、SAや遺伝的アルゴリズムのような大域的な探索手法では実行時間が長くなってしまいます。
そこで、本論文では高速に実行可能な量子アニーリングを利用します。まず、量子アニーリングマシンで計算可能な形でクラスタリングを定式化します。そして、それらの問題を解いた結果をk-meansと比較し、提案手法の利点と欠点について議論します。

航空機に対する発着ゲートの割り当ては航空管制において重要な業務の一つとなっています。この際、最も効率良いようなゲート割り当てを求めたいわけだが、これは組合せ最適化問題として扱うことができます。しかしながら、このような問題では最適解を高速に求めることが困難であることが知られています。したがって、本論文では量子アニーリングマシンのような新しいハードウェアの有用性を評価します。しかし、現実世界の問題では数多くの量子ビットを必要とするため、現状の量子アニーリングマシンでそのまま計算を行うことはできません。そこで、問題の構造を維持したまま、データを前処理することで、量子ビットを削減することを試みました。

本論文では量子アニーリングを用いてガンデータの分類を行い、既存アルゴリズムとの比較評価を行います。量子アニーリングは、量子効果を用いてイジング模型の基底状態を探索します。このイジング模型の基底状態を古典的な計算によって探索することが可能なシミュレーテッドアニーリングの性能も評価します。その結果、イジング模型を用いた機械学習アルゴリズムは、学習データが少ない場合に優れた分類性能を持つことがわかりました。

本論文では自動車産業の課題として、Volkswagenの自動車製造に欠かせない工程である車両の塗装順の計算をマルチカーペイントショップ問題として定義し、そのソルバとして量子アニーリングマシンの有効性を評価する。

本論文では、ボルツマンマシンの学習内のサンプリングにD-Waveマシンを用いることで、その画像生成の品質向上を目的としています。
分類器としてニューラルネットワークを予め学習しておき、特定の数字の画像を生成したときに、その画像の分類結果を測ることで直接的な評価を行います。

今回は、量子アニーリングソリューションコンテストに参加した際の発表内容を紹介します。筆者はチームT-QARD-QAPOとして参加し、ポートフォリオ最適化に関するアプリを構想し、発表しました。ポートフォリオ最適化とは、リスクとリターンを考慮して、最適な資産の組み合わせ（ポートフォリオ）を見つけることです。ポートフォリオ最適化には様々な理論がありますが、今回は現代ポートフォリオ理論に基づいたポートフォリオ最適化を行いました。

先日開催された量子アニーリングソリューションコンテストにTQARD-410として参加し、量子アニーリングでフォトモザイクアートを作成するPhosaiqを提案しました。Phosaiqは画像の並びを最適化したフォトモザイクアートを作成し、またユーザーが調整することでフォトモザイクアートの質とユーザの体験価値を高めるプロダクトです。このコンテストにおいて、Phosaiqは優勝(D-Wave Systems社賞を受賞)することができました。

グラフ彩色とは隣接した頂点対を異なる色になるように彩色することです。3色以上のグラフ彩色はNP困難であり、高速に計算することが困難な問題の一つです。したがって、厳密性を犠牲にした近似的な解を求めるのが妥当であると考えられています。近似解を求める方法の一つにグラフから独立点集合(どの頂点も隣接していない頂点の集合)を求め、一つの独立点集合ごとに1色ずつ割り当てる貪欲法があります。本論文では、このアルゴリズムでグラフ彩色を行うときに独立点集合を量子アニーリングを用いて求めます。この提案手法を古典コンピュータで独立点集合を求めたときの結果を比較します。

ボルツマン機械学習では対数尤度関数を最大化するために、ギブス・ボルツマン分布からのサンプリングによる平均値を計算する必要があります。その方法の一つとして、マルコフ連鎖モンテカルロ法 (MCMC) が使われています。しかし、MCMCは初期状態から平衡状態への緩和に長時間の計算を要する場合があります。また、緩和した後も平均値を精度良く求めるための十分なサンプリング数の確保に時間がかかるといった課題もあります[1]。そこで本論文では、D-Waveマシンから得られる出力の分布がギブス・ボルツマン分布に近いことを利用して、平均値の計算にD-Waveマシンを用います。本手法により、手書き数字画像の生成・復元が可能であることに加え、ランダムなイジング模型も学習可能であることを示します。

本論文では、グラフ分割問題を取り扱う。グラフ分割問題とはグラフのノードを複数のグループに分割することであり、以下の二つの条件を満たすことを考える。