線形スケジューリングでの成功確率

前節で求めた励起状態の展開係数[^式(6.163)]から分かるように，励起状態の展開係数 は基底状態とのエネルギーギャップに依存した速さで指数関数的に減衰する．このことか

ら，QA-ITでは基底状態から励起状態への遷移が発生したとしても，エネルギーギャップ

が大きい領域での減衰を利用することで高い成功確率が得られると期待される．実際に，

いくつかのモデルでQA-RT^よりQA-ITの方が高速となることが先行研究 [16, 18, 19]^で 示されている．ここでは，短時間極限での線形スケジューリングにおける成功確率の上限 を計算し，励起状態の指数減衰を考慮した場合の計算時間を算出する．

線形スケジューリングにおけるグローバー問題のハミルトニアンは

HˆQA(s) =sHˆ0+ (1−s) ˆHq, (6.182) Hˆ0 = ˆI_N− |0⟩ ⟨0|, (6.183) Hˆq= ˆI_N− |Ψ0⟩ ⟨Ψ0|, (6.184)

|Ψ₀⟩ ≡ 1

√N

N∑−1 i=0

|i⟩, (6.185)

ds

du = 1, (6.186)

で与えられる．第6.5節で述べたようにグローバー問題のQA^は2準位系に帰着するので，

基底状態と励起状態の展開係数のみを考えればよく，maxj|Aj0(u)|=|A10(u)|^{となる．式} (6.157)^に式(6.165)を代入すると，展開係数の微分方程式は

dc^′₁(u)

du = +c^′₀(u)∆ε₁₀(u)A₁₀(u)e^{+τ∆ϕ10(u)}, (6.187) dc^′₀(u)

du =−c^′₁(u)∆ε₁₀(u)A^∗₁₀(u)e^{−τ∆ϕ10(u)}, (6.188) となる．この微分方程式に式(6.34)，(6.36)，(6.95)を代入すると

dc^′₁(u) du = +

√N −1 N

c^′₀(u)

∆ε10(u)²e^{+τ∆ϕ10(u)}, (6.189) dc^′₀(u)

du =−

√N −1 N

c^′₁(u)

∆ε10(u)²e^{−τ∆ϕ10(u)}, (6.190) と変形できる．式(6.189)を積分すると，励起状態の展開係数について

c^′₁(u) =c^′₁(0) +

√N −1 N

∫ _u

0

du^′ c^′₀(u^′)

∆ε10(u^′)²e^{τ∆ϕ10(u′)}, (6.191) が得られる．初期条件を

c₀(0) =c^′₀(0) = 1, (6.192) c1(0) =c^′₁(0) = 0, (6.193) と設定すると，式(6.190)の右辺は負となるので，

c^′₀(u)≤1, (6.194)

となる．式(6.191)に式(6.193)と(6.194)を代入して，両辺にe^{−τ ϕ1(u)}を掛けると

c1(u)≤e^{−τ ϕ0(u)}D1(u), (6.195)

D₁(u)≡

√N−1

N e^{−τ∆ϕ10(u)}

∫ _u

0

du^′

∆ε₁₀(u^′)²e^{τ∆ϕ10(u′)}, (6.196)

となる．c1(u)の上限を評価するためには，D1(u)の右辺の積分を計算すればよい．断熱定 理では長時間極限における展開係数を求めることを目指していたので，式(6.196)^の部分 積分を実行する際にe^{τ∆ϕ10(u′)}を積分し，1/τ の次数を増加させていた．一方で，ここで は短時間アニーリングでの展開係数を求めたいので，部分積分を実行する際にe^{τ∆ϕ10(u′)} を微分して，τ の次数を増加させていくという方針をとる．ただし，以降の計算が簡単に なるため，断熱定理の導出と同様の部分積分を1回だけ実行し，

D1(u) = 1 τ

√N−1

N e^{−τ∆ϕ10(u)}

{[ 1

∆ε10(u^′)³e^{τ∆ϕ10(u′)} ]_u^′₌₁

u^′=0

+12 (

1− 1 N

) ∫ u 0

du^′

∆ε₁₀(u^′)⁵ (

u^′−1 2

)

e^{τ∆ϕ10(u′)} }

, (6.197) と変形する．式(6.158)^に式(6.153)^と(6.88)^{を代入すると，}N ≫1^では

∆ϕ₁₀(u)≃ 1 2

( u−1

2 )

∆ε₁₀(u) +1

4, (6.198)

と近似できる（付録.B参照）．式(6.198)を式(6.197)に代入すると，QA終了時点（u= 1） におけるD1(u= 1)^は

D1(u= 1)≃ 1 τ

√N −1

N (1−e^−τ2) +12N τ

(√ N −1

N )3

e^−τ4I1(1,0), (6.199) I₁(u_a, u_b)≡

∫ _ub

ua

du

∆ε₁₀(u)⁵ (

u−1 2

)

e^τ2(^u−¹₂)^∆ε10(u), (6.200) となる．さらに，式(6.200)の右辺に含まれる指数関数の肩に対して，N ≫1^として

τ 2

( u−1

2 )

∆ε₁₀(u)≃τ (

u−1 2

) u−1 2

, (6.201)

と近似する．この近似ではエネルギーギャップの最小値を0としているため，断熱的な時 間発展について調べたい場合に採用すると間違いを起こすと考えられる．一方で，グロー バー問題に対する短時間のQA-ITでは励起状態の展開係数の指数減衰が支配的な要素と なるため，大きな問題にはならない．或いは，短時間のQAではエネルギーギャップの最 小値が1/√

N と0のどちらであったとしても，基底状態を維持するよりも励起状態に遷移 する方が支配的であると考えてもよい．式(6.201)は|u−1/2|^{を含むので，}

I1(0,1) =I1

( 0,1

2 )

+I1

(1 2,1

)

, (6.202)

と分解して，第一項と第二項の上限を別々に評価する．第一項に関しては，積分変数を x= 4(N −1)

( u−1

2 )₂

+ 1, (6.203)

と変換すると

I1

( 0,1

2 )

≃ −1 8

N⁵²

N −1e^14Nτ−1J1(1, N), (6.204) J₁(1, N)≡

∫ _N

1

dx

x⁵²e^−x4Nτ−1, (6.205)

となる．J₁(1, N)の被積分関数に含まれる1/x⁵² は繰り返し積分し易い関数であり，部分 積分を実行する際にe^−x4Nτ−1 を微分してτの次数を増やしていくことができる．この部分 積分を3回実行すると

J1(1, N) = 2

3e^−14Nτ−1 [

1−1 2

( τ N−1

)

− 1 4

( τ N −1

)2]

− 2 3

(1 N

)³

2

e^{−14NN τ−1} [

1−1 2

( N τ N−1

)

− 1 4

( N τ N −1

)2]

+ 1 24

( τ N −1

)3∫ _N

1

√xe^−x4Nτ−1dx, (6.206) が得られる．式(6.206)の第三項の積分を厳密に計算することはできないが，1 ≤x≤N で成立する以下の不等式:

1 1 +√

Nx+

√N 1 +√

N ≤√

x, (6.207)

を用いるとJ₁(1, N)の下限を J1(1, N)≥ 2

3e^−14Nτ−1 [

1−1 2

√N−1

√N+ 1 ( τ

N −1 )]

−2 3

( 1 N

)³

2

e^{−14NN τ−1} [

1 +1 2

√N−1

√N+ 1 ( N τ

N −1 )]

, (6.208) と評価することができ，結果を式(6.204)^{に代入すると}

I1

( 0,1

2 )

≤ − 1 12

N⁵² N −1

[ 1−1

2

√N−1

√N+ 1 ( τ

N −1 )]

+ 1 12

N N −1e^−τ4

[ 1 +1

2

√N −1

√N + 1 ( N τ

N−1 )]

(6.209) が得られる．式(6.202)の第二項に関しても，式(6.203)によって積分変数を変換すると

I₁ (1

2,1 )

≃ 1 8

N⁵²

N −1e^−14Nτ−1K₁(1, N), (6.210) K₁(1, N)≡

∫ _N

1

dx x⁵²

e^+x4N−1τ , (6.211)

と変形できる．先程と同様の部分積分を3回実行すると K1(1, N) =−2

3 (1

N )³

2

e^{14N−1N τ} [

1 +1 2

( N τ N −1

)

−1 4

( N τ N−1

)₂]

+2 3e^14Nτ−1

[ 1 +1

2 ( τ

N−1 )

− 1 4

( τ N −1

)₂]

− 1 24

( τ N −1

)3∫ _N

1

√xe^x4Nτ−1dx, (6.212)

となり，式(6.207)^{を用いると}K1(1, N)^の上限を

K1(1, N)≤ −2 3

( 1 N

)³

2

e^{14NN τ−1} [

1−1 2

√N −1

√N + 1 ( N τ

N−1 )]

+2 3e^14Nτ−1

[ 1 +1

2

√N−1

√N+ 1 τ N −1

]

, (6.213) と評価することができる．この結果を式(6.210)に代入すると，

I₁ (1

2,1 )

≤ − 1 12

N N −1e^τ4

[ 1−1

2

√N−1

√N+ 1 ( N τ

N −1 )]

+ 1 12

N⁵² N −1

[ 1 +1

2

√N−1

√N+ 1 ( τ

N −1 )]

, (6.214) が得られる．式(6.199)に式(6.202)，(6.209)，(6.214)を代入すると

D1(u= 1)≤ 1 2√

N−1

√N−1

√N+ 1 (

1 + 2√

N e^−τ4 +e^−τ2 )

≃e^−τ4, (6.215)

となる．この結果は，励起状態の展開係数はN に依存しない速さで指数関数的に減衰す ることを示しており，この結果の妥当性については後の数値計算で確認する．

次に，基底状態の展開係数の下限を評価する．QA-ITではノルムが保存しないので，成 功確率を計算するためには基底状態と励起状態の展開係数の比を求める必要がある．まず，

以下の不等式:

d dt

√P_GS(t) = d dt

⟨0|ψ(t)⟩

⟨ψ(t)|ψ(t)⟩ ≥0, (6.216) を証明する．この不等式は，最適解|0⟩^{を得る確率が}QA-ITの過程で減少しないことを表 している．式(6.147)^{を用いると}

d dt

√P_GS(t) = ⟨0|ψ(t)⟩ ⟨ψ(t)|H(t)ˆ |ψ(t)⟩ − ⟨ψ(t)|ψ(t)⟩ ⟨0|H(t)ˆ |ψ(t)⟩

⟨ψ(t)|ψ(t)⟩³² , (6.217) と変形できる．式(6.90)^と(6.91)^{を用いると，最適解}|0⟩^は

|0⟩=P(t)|0(t)⟩ −Q(t)|1(t)⟩, (6.218)

0≤P(t), Q(t)≤1, (6.219)

と展開でき，状態ベクトルは

|ψ(t)⟩=L(t) [

α(t)|0(t)⟩+√

1−α(t)²|1(t)⟩]

, (6.220)

0≤α(t)≤1, (6.221)

と書くことができる．ここで，L(t)は時間に依存する状態ベクトルのノルムを表している．

式(6.218)^と(6.220)^を式(6.217)^{に代入すると} d

dt

√PGS(t) =α(t)√

1−α(t)²[√

1−α(t)²P(t) +α(t)Q(t) ]

∆ε10(t)≥0, (6.222) となり，式(6.216)が示される．この結果から，

PGS(τ)≥ 1

N, (6.223)

となることが分かる．ここで，P_GS(τ)はQA-ITの終了時点で最適解を得る確率を表して

おり，1/N はQA-ITの初期条件において最適解を得る確率を表している．基底状態の展

開係数を

C0(u)≡e^{−τ ϕ0(u)}D0(u), (6.224) とおいて，式(6.224)^と(6.195)^{を用いると，}PGS(τ)^{は展開係数を用いて}

PGS(τ) = c0(1)²

c₀(1)²+c₁(1)², (6.225)

= D0(1)²

D₀(1)²+D₁(1)², (6.226) と書くことができる．励起状態の展開係数に関しては，式(6.215)よりτ →0, N → ∞^で

D₁(u= 1)≤1, (6.227)

を満たしており，式(6.223)，(6.226)，(6.227)を用いると D₀(u= 1)≥ 1

√N, (6.228)

が得られる．

最後に，特定の成功確率:

PGS(τ) = 1

1 +δ^′2, (6.229)

を達成するために必要なアニーリグ時間τGS(δ^′)^{を計算する．式}(6.215)^と(6.228)^より，

D₁(1) D₀(1) ≲√

N e^−τ4, (6.230)

が得られ，これを式(6.226)^{に代入すると}

PGS(τ) = 1

1 +N e^−τ2, (6.231)

となる．この結果から，式(6.229)を達成するためのアニーリング時間は τ_GS(δ^′) = 2 log

(N δ^′2

)

∼O(logN), (6.232)

と見積もることができる．

断熱的な時間発展を前提にしたアニーリング時間τ_thはO(N)で増加するが，励起状態 の展開係数の指数減衰も考慮するとO(logN)で抑えられることが分かる．

10 15 20 25 30 35 40

10² 10³ 10⁴ 10⁵ 10⁶ 10⁷ 10⁸ τGS(0.01)

The number of items: N Simulation

Linear fits

図6.19: 線形スケジューリングで99%の成功確率を得るために必要なアニーリング時間

ドキュメント内 大規模な組合せ最適化問題に対する量子アニーリングマシンの活用方法に関する研究 (ページ 95-101)