第 6 章 量子揺らぎのスケジューリングによる高速化 66
6.6 数分割問題のスケジューリング
ϴ͘ϴ͕ϵ͘ϳ͕ϱ͘Ϭ͕ϲ͘ϴ ϵ͘ϰ͕ ϵ͘Ϯ͕ ϰ͘ϴ͕ ϲ͘ϵ
䛘䜙䜜䛯ᩘ
䜾䝹䞊䝥ϭ 䜾䝹䞊䝥Ϯ ϴ͘ϴ͕ϵ͘ϳ͕ϱ͘Ϭ͕ϲ͘ϴ ϵ͘ϰ͕ ϵ͘Ϯ͕ ϰ͘ϴ͕ ϲ͘ϵ
⥲сϯϬ͘ϯ ⥲сϯϬ͘ϯ
図6.12: 今回の評価で取り扱う数分割問題
• 線形スケジューリング[式(6.37)と(6.49)参照]
τc(1) = 2.23×104, (6.107)
τ∞= 8.04×102, (6.108)
τth= 2.23×104, (6.109)
• 断熱定理に基づくスケジューリング[式(6.41)と(6.57)参照]
τc(1) = 6.88×102, (6.110)
τ∞= 2.32τc(1), (6.111)
τth= 1.60×103, (6.112)
• 第一励起状態に基づくスケジューリング[式(6.44)と(6.60)参照]
τc(1) = 1.83×109, (6.113)
τ∞= 0.73τc(1), (6.114)
τth= 1.83×109, (6.115)
断熱定理に基づくスケジューリングのτthが最も小さく，第一励起状態に基づくスケジュー リングのτthが最も大きくなっている．この結果は，第一励起状態に基づいたスケジュー リングで断熱的な時間発展を達成するためには，線形スケジューリングよりも長いアニー リング時間を必要とすることを示している．スケジューリングを工夫してQAを高速化す る際には，式(6.32)の分子にある行列要素も考慮してある程度の高エネルギー状態まで考 慮する必要があることが分かる．
断熱定理に基づくスケジューリングと第一励起状態に基づくスケジューリングにおける sのu依存性を図6.14に示す．2つのスケジューリングにおけるsはほとんど同じu依 存性を示となっているにも関わらず，τthは式(6.112)と(6.115)に示すように大きく異な
10-8 10-6 10-4 10-2 100 102 104 106
0 0.2 0.4 0.6 0.8 1
|Amax(s)|, |A10(s)|
s
|Amax(s)|
|A10(s)|
図6.13: ハミルトニアンを特徴づける量
0 0.2 0.4 0.6 0.8 1
0 0.2 0.4 0.6 0.8 1
s(u)
u = t / τ Based on |ATmax(s)|
Based on |AT10(s)|
図6.14: sのu依存性の比較
0 0.1 0.2 0.3 0.4
0 0.02 0.04 0.06 0.08 0.1
s(u)
u = t / t Based on |ATmax(s)|
Based on |AT10(s)|
図 6.15: QA序盤におけるs(u)の比較
0.4 0.5 0.6 0.7 0.8 0.9 1
0.95 0.96 0.97 0.98 0.99 1
s(u)
u = t / t Based on |ATmax(s)|
Based on |AT10(s)|
図6.16: QA終盤におけるs(u)の比較 る．このことから，τthはスケジューリングの変更に対して非常に敏感であり，現実的に
はD-Waveマシン等のアニーリングマシンでスケジューリングの工夫による高速化を達成
するのは非常に難易度が高いことが分かる．また，断熱定理に基づくスケジューリングを 導出できて，且つD-Waveマシン等で正確にスケジューリングを設定できたとしても，第 6.3節で議論したように指数関数的な高速化を達成できる状況は極めて限定的である．QA の序盤と終盤におけるs(u)を比較したのが図6.15と6.16である．第一励起状態に基づく スケジューリングではQAの序盤と終盤における励起状態への遷移のし易さが過小評価さ れるので（図6.13参照），断熱定理に基づくスケジューリングに対してs(u)が高速に変 化している．
6.6.3 数値計算による確認
次に，シュレーディンガー方程式を数値的に解いて，失敗確率と残留エネルギーのτ依 存性を確認する．シュレーディンガー方程式は4次のルンゲ-クッタ法を用いて解いた．
線形スケジューリング，第一励起状態に基づいたスケジューリング，断熱定理に基づい たスケジューリングを用いた場合の失敗確率のτ依存性を図6.17に示す．赤の実線は断熱 定理に基づくスケジューリングにおける長時間極限の失敗確率の上限Pall∞(τ)[式(6.57)]を 表しており，点線は各スケジューリングのτthを表している．図から明らかなように，断 熱定理に基づくスケジューリングを利用すると失敗確率を下げることができるが，第一励
10-4 10-3 10-2 10-1 100
100 101 102 103 104 105
1 - PGS(τ)
Annealing time: τ Linear scheduling
Based on |ATmax(s)|
Based on |AT10(s)|
図6.17: N = 104における失敗確率のτ依存性の比較
起状態に基づくスケジューリングでは線形スケジューリングと同等以下の成功確率しか得 られない．第一励起状態に基づくスケジューリングによってQA性能が改善しないこと自 体は予想通りであるが，失敗確率が1から下がり始める時間に関してはτth[式(6.115)]よ り小さくなっている．一方で，線形スケジューリングと断熱定理に基づくスケジューリン グではτ =τth付近から失敗確率が1から下がり始めており，この結果は断熱的な時間発 展が実現されることで成功確率が上がり始めていることを示唆している．長時間極限にお ける失敗確率に関しても，断熱定理に基づくスケジューリングでは式(6.57)に近い値と なっている．第一励起状態に基づくスケジューリングでτthよりも短いアニーリング時間 から失敗確率が下がり始める原因ははっきりと分からないが，励起状態から基底状態への 遷移が寄与しているのではないかと予想される [104, 121]．また，線形スケジューリング の101 ≲τ ≲103で失敗確率が若干下がっていることも，励起状態から基底状態への遷移 が関わっているのではないかと推測される．
図6.18は残留エネルギーのτ依存性を示している．予想に反して，断熱定理に基づく スケジューリングより線形スケジューリングの残留エネルギーの方が低くなってる．成功 確率は断熱定理に基づくスケジューリングが最も高くなっていることを考慮すると，断熱 定理に基づくスケジューリングでは基底状態かエネルギーの非常に高い励起状態が出力さ れることが分かる．この原因としては，断熱定理に基づくスケジューリングではQAの終 盤でsを高速に動かすため，s≃0.4で第一励起状態への遷移が発生するとQA終盤で励 起状態から励起状態への遷移が発生してしまうことが挙げられる．この結果は，高い成功 確率を得るためのスケジューリングと低い残留エネルギーを得るためのスケジューリング は一般的に異なっていることを示している．基底状態を効率的に得るための指針は断熱定 理によって与えられるが，低い残留エネルギーを得るための効率的なスケジューリングを 設定する方法に関してはよく分かっていない．
10-3 10-2 10-1 100 101 102 103
100 101 102 103 104 105
Residual energy
Annealing time: τ Linear scheduling
Based on |ATmax(s)|
Based on |AT10(s)|
図6.18: N = 104における失敗確率のτ依存性の比較