部分問題の埋込アルゴリズムの提案

よる最短経路の探索で占められているので，要求される最短経路の探索回数に焦点をあて る．ダイクストラ法の計算時間は，ハードウェアグラフの頂点数|Vq|^{とエッジの数}|Eq|^を 用いて

T_Dijkstra∼O(|E_q|+|V_q|log|V_q|), (4.1) で与えられる．キメラグラフでは

|E_q| ∼O(|V_q|¹), (4.2)

である．前半処理では問題グラフに含まれる相互作用の数|Ep|だけ最短経路を探索する 必要があるので，最短経路の探索回数N_Dijkstra^{(1) は，}

N_Dijkstra⁽¹⁾ ∼O(|E_p|), (4.3)

となる．後半処理における最短経路の探索回数N_Dijkstra⁽²⁾ は

N_Dijkstra⁽²⁾ ∼O(|Vp||Vq||Ep|), (4.4) であることが先行研究 [90]の中で示されている．ここで，|Vp|は問題グラフに含まれる変 数の数を表す．計算時間は明らかに後半処理が支配的となっている．このことから，前半 における重複割当てを上手く避ける方法を見つけ出せれば，後半の処理が不要となり，計 算時間を大幅に低減できると期待される．

この問題設定から分かるように，従来の埋め込みアルゴリズムはD-Wave^{マシンを用いて} 直接問題を解くことを前提として考えられてきた．一方で，部分問題の埋め込みアルゴリ ズムでは，一部の変数で構成される部分問題を埋め込めば良い．この違いを考慮すると，

部分問題の埋め込みに限って言えば，Caiのアルゴリズムから重複割当てを取り除くこと は容易である．つまり，重複割当てが不要な埋め込み易い変数で部分問題を構成し，重複 割当てを利用しないと埋め込めない変数の埋め込みは諦めれば良い．

しかしながら，単純に重複割当てを拒否するだけでは埋め込み可能な変数がすぐになく

なり，qubitを使い切る前に埋め込みが終了するという問題が発生する．簡単な例として，

図4.5(a)に示す問題グラフにおいて，変数1から順番にキメラグラフに埋め込むことを

考える．変数1が図4.5(b)に示すように左上のqubitに割当てられたとすると，変数2〜 6は最短経路に基づいて図4.5(c)に示すように埋め込まれる．この時点で変数1が割当て

られたqubitの隣接は全て使い切っているので，未使用qubitが多く残っているにも関わ

らず変数7^〜9が埋め込まれずに終了してしまう．この問題は変数1^のchain ^{を伸ばす余} 地が残されていないことに起因しており，解決策として提案アルゴリズムではqubit^の予 約という概念を導入する．最短経路探索の結果として重複割当てをせずに変数x_add^を埋 め込めると分かった場合，x_addは最短経路の起点qubitに関連付けてchainを伸ばすため

に必要なqubitを予約する．起点qubitがキメラグラフ内の完全2部グラフの左側と右側

のどちらに位置するかに依存して予約されるqubitは異なる．起点が左側に位置する場合 は図4.6(a)に示すようにキメラグラフ上で縦方向にchain^{を伸ばすための}qubit^が予約さ れ，右側に位置する場合は図4.6(b)に示すようにキメラグラフ上で横方向にchain^を伸ば すためのqubit^{が予約される．}x_add^{が予約した}qubit^に対してx_add^{以外の変数を割当てる} ことは禁止され，x_addの全ての隣接変数の埋め込みが完了した時点でx_addによる予約が 解消される．予約制度の導入によって図4.5(a)の問題グラフの全ての変数が埋め込めるよ うになることを図4.7を用いて示す．図4.7(a)に示すように，変数1がキメラグラフの左

上のqubitに割当てられると，その下の完全2^{部グラフにある}qubit^が変数1^{によって予}

約される．変数2^〜5が追加で埋め込まれた状態が図4.7(b)^{であり，変数}2^〜5^はchain^を 横方向に伸ばすためのqubit^{を予約する．図}4.7(c)^{に示すように，変数}6^〜9^{が埋め込まれ} る時点で変数1の予約qubitに対して変数1が実際に割当てられ，新たに変数1が割当て

られたqubitに隣接するように変数6〜9が割当てられる．以上のように，予約制度の導

入によって多くの変数と相互作用する変数が存在する場合でも，chainを伸ばしながら埋 め込んでいくことが可能となる．起点に関連させて予約するqubit^{の選び方は，問題グラ} フの中で最も相互作用の数が多い完全グラフの埋め込み方法を参考にすればよい．図4.3 を見ると分かるように，完全グラフの埋め込みでは変数間の相互作用を表現するために完 全2部グラフ内の濃い相互作用を利用し，相互作用する変数の種類を増やすために異なる 完全2部グラフを跨ぐようにchainを伸ばしている．予約制度ではこれを参考にして，起 点qubitから異なる完全2部グラフに向けてchain を伸ばせるように予約qubitを決めて いる．予約制度はキメラグラフの構造を利用したものであり，第4.2^{節で挙げた「アルゴ} リズムの中身が相互作用の詳細に依存しない」という要件を満たしていないように思える が，ハードウェアグラフが変更されたときでも完全グラフの埋め込みを参考にするという 方針の下で柔軟にアルゴリズムを修正することができる．

最後に，重複割当ての拒否による最短経路探索の計算時間低減について説明する．Cai

ϭ Ϯ

ϯ ϰ ϱ ϲ ϴ ϳ

ϵ ϭ

ϯ ϰ ϱ ϲ

ϭ Ϯ

;ĂͿၥ㢟䜾䝷䝣 ;ďͿኚᩘϭ䜢ᇙ䜑㎸䜏ᚋ ;ĐͿኚᩘϲ䜎䛷䜢ᇙ䜑㎸䜏ᚋ

図4.5: 重複割当ての拒否により問題が発生する例

;ĂͿ⦪᪉ྥ䛾ண⣙ ;ďͿᶓ᪉ྥ䛾ண⣙

ண⣙ƋƵďŝƚ

ண⣙ƋƵďŝƚ

ண⣙ƋƵďŝƚ

㉳ⅬƋƵďŝƚ

ண⣙ƋƵďŝƚ ண⣙ƋƵďŝƚ

㉳ⅬƋƵďŝƚ ண⣙ƋƵďŝƚ

図4.6: 基点qubitに関連して予約されるqubit

ϭ

;ĂͿኚᩘϭ䛾๭ᙜ䛸ண⣙ ;ďͿኚᩘϮ䛛䜙ϱ䛾๭ᙜ䛸ண⣙ ;ĐͿኚᩘϲ䛛䜙ϵ䛾๭ᙜ䛸ண⣙

ϭ

ϭ

ϭ

ϯ ϰ ϱ Ϯ

ϯ ϰ ϱ

Ϯ ϭ

ϭ

ϯ ϰ ϱ Ϯ

ϯ ϰ ϱ Ϯ

ϳ ϴ ϵ ϲ

ϳ ϴ ϵ ϲ

図4.7: 予約制度の導入による埋め込みの改善

฼⏝῭䜏ƋƵďŝƚ䜢ྵ䜐᏶඲Ϯ㒊䜾䝷䝣

฼⏝῭䜏ƋƵďŝƚ䜢ྵ䜎䛺䛔䛜 '_ƉĂƚŚ䛻ྵ䜎䜜䜛᏶඲Ϯ㒊䜾䝷䝣

฼⏝῭䜏ƋƵďŝƚ䜢ྵ䜎䛪䠈 '_ƉĂƚŚ䛻ྵ䜎䜜䛺䛔᏶඲Ϯ㒊䜾䝷䝣

図 4.8: G_pathに含まれる完全2部グラフの例

のアルゴリズムでは重複割当てを許容しているため，変数が割当てられたqubit^も含めて ハードウェアグラフ全体で最短経路を探索する必要がある．一方で，提案したアルゴリズ ムでは重複割当てを拒否するため，最短経路を探索するグラフG_pathは未使用qubitのみ で構成すれば十分である．図4.8に示すように，G_pathは利用済みのqubitを含む完全2部 グラフ(^青色)と，それらに隣接する完全2^部グラフ(^赤色)のみで構成すれば良い．利用 済みのqubit^がGpathから除かれることを考慮すると，Gpathの頂点数|Vpath|^{とエッジの} 数|E_path|は赤色のセルに含まれるものが支配的であり，

|Vpath| ∼O(|Vq|^1/2), (4.5)

|E_path| ∼O(|V_path|), (4.6) となる．ダイクストラ法の計算時間が式(4.1)で与えられ，キメラグラフのエッジ数が式

(4.2)で与えられることを考慮すると，最短経路の計算時間だけを見てもCai^{のアルゴリ}

ズムに対して約1/√

|V_q|^{に減少する．}