埋め込み性能の評価

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

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

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

図 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|^{に減少する．}

䐟ϯϬϬdžϯϬϬኚᩘ䛾ṇ᪉᱁Ꮚ

䐠ϭϬϬϬኚᩘ䛾᏶඲䜾䝷䝣

ϭϬϬ䡚ϭ୓ƋƵďŝƚ䛾䜻䝯䝷䜾䝷䝣

<_ϰ͕ϰ䠖ϰ䡚ϯϱಶ

<ϰ͕ϰ䠖ϰ䡚ϯϱಶ ϯϬϬ

ϯϬϬ

㒊ศၥ㢟䛾 ᇙ䜑㎸䜏

㒊ศၥ㢟䛾 ᇙ䜑㎸䜏

図4.9: 最短経路の探索回数と部分問題サイズのqubit数依存性の評価方法

問題を埋め込む．また，各qubit数のキメラグラフに対して100回部分問題の埋め込みを 実施し，平均と分散を評価した上で平均±標準偏差をエラーバー付きでプロットする．最 短経路の探索回数N_path^{の評価結果が図}4.10に示してある．問題グラフが正方格子と完全 グラフの場合のN_pathのqubit依存性を線形近似により求めると

N_path^(grid)∼O(N_q^1.27), (4.7)

N_path^(complete) ∼O(N_q^0.84), (4.8) が得られる．ここで，N_qはqubit数を表す．一般的に実時間アルゴリズムはN_q³以下が望 ましいと言われることを考えると，提案アルゴリズムにおける経路探索回数のqubit数依 存性は十分小さいと言える．図4.11にはN_subのqubit数依存性を示す．問題グラフが正 方格子と完全グラフの場合のNsubのqubit数依存性を線形近似により求めると

N_sub^(grid)∼O(N_q^0.90), (4.9)

N_sub^(complete) ∼O(N_q^0.50), (4.10) が得られる．完全グラフに対しては，理論的に埋め込み可能な最大の部分問題サイズを埋 め込めている．正方格子では，理論的に埋め込み可能な部分問題サイズはO(N_q^1.0)である のに対して，評価結果ではO(N_q^0.9)と近い依存性を示している．ここで重要なのは，完全 グラフの埋め込み方法[92]を用いた場合は，問題グラフが正方格子であってもO(N_q^0.5)の 部分問題しか埋め込めないのに対して，提案アルゴリズムを用いることでO(N_q^0.9)^の大き な部分問題を埋め込めるということである．以上の評価結果から，最短経路の探索回数と 部分問題サイズのqubit数依存性は問題ないと言える．

次に，任意の2変数間に対してランダムに相互作用を発生させたグラフ（Erd˝os-R´enyi

graph）を問題グラフとしたときに，2048qubitのキメラグラフに埋め込まれる部分問題の

サイズを確認する．ここでは，問題グラフ上で相互作用を発生させる確率P_bondを変化さ

10² 10³ 10⁴ 10⁵ 10⁶ 10⁷

10² 10³ 10⁴ 10⁵

Npath

The number of qubits: N_q Grid graph

Complete graph Linear fits

図4.10: ^{最短経路の探索回数}N_path^のqubit^数依存性

10¹ 10² 10³ 10⁴ 10⁵

10² 10³ 10⁴ 10⁵

Nsub

The number of qubits: N_q Grid graph

Complete graph Linear fits

図4.11: ^{部分問題サイズ}Nsubのqubit^数依存性

50 100 150 200 250 300 350

0.01 0.1 1

Nsub

Edge probability: P_bond

図4.12: 部分問題サイズN_subのqubit数依存性

せて，キメラグラフに埋め込まれる部分問題サイズNsubを評価する．各Pbondに対して 1個の問題グラフを生成し，部分問題を100回埋め込んだときの平均と分散を評価した上 で，平均±標準偏差をエラーバー付きでプロットする．問題グラフの相互作用密度P_bond の減少に伴って部分問題サイズN_subは大きくなっており，問題グラフの相互作用をラン ダムに発生させた場合でも，問題グラフに合わせて大きな部分問題を埋め込めていること が分かる．

最後に，100×100変数の正方格子の問題グラフに提案アルゴリズムを適用したとき に，2,048qubitのキメラグラフ上に埋め込まれた部分問題の例を図4.13^と4.14^に示す．

100×100の各グリッドが2値変数を表しており，部分問題としてキメラグラフ上に埋め 込まれた変数を黒く塗りつぶしてある．本章の第4.2節で説明したように，部分問題のグ ラフは木構造になっていないことが好ましいが，提案アルゴリズムによって埋め込まれた 部分問題は閉ループを多く含む構造になっていることが分かる．

以上の評価結果によって，提案アルゴリズムが期待通りの動作をしていることを確認で きたと言える．