Jij Tech Blog

Jij inc.の開発日記です

データベース探索問題の量子断熱解 (Adiabatic Grover)

断熱量子計算 量子アニーリング 量子コンピュータ

この記事の概要

量子アルゴリズムの有名なものとしてグローバー(Grover)のアルゴリズムがあります。多数の項目の中から特定の項目を見つけるデータベース探索問題です。これを断熱量子計算(Adiabatic Quantum Computing, AQC)で解くとどのようになるのか、その解法や計算速度をご紹介いたします。

復習: グローバーのアルゴリズム

探索問題とその古典オラクル

探索問題とは一般にN個の要素からM個の解を見つける問題のことです。例として名簿データベースから佐藤さんだけを取り出したいなどが考えられます。N個の要素がn桁のビット列 x = x_1 x_2 \cdots x_nでラベル付けされているとして、この探索問題に対する「古典オラクル」を次のように定義しましょう。

\displaystyle{ f(x) = \left\{ \begin{array}{cl} 1 && (xは解) \\ 0 && (xは解でない) \end{array} \right. }

つまりfは要素のラベルxを与えるとその要素が解であるかを2択で教えてくれる関数です。名簿の例では 名簿_0 = 高橋, 名簿_1 = 佐藤のとき、 f(0) = 0, f(1) = 1となります。探索問題を解く古典アルゴリズムの計算量は xが解であるかどうかを古典オラクルに尋ねる(オラクルを呼びだす)回数で評価します。こうすることで、問題の子細に依存しない統一的な評価が可能になります。

オラクルについてのより詳細を知りたい方はこちらの記事もあわせてご覧ください。

量子オラクルと位相反転


一方、探索問題を解く量子アルゴリズムの計算量は、次の(量子)オラクル \mathcal{O}_fを呼ぶ回数で評価します。

\displaystyle{ \left|x \right\rangle \otimes \left|q \right\rangle \xrightarrow{\mathcal{O}_f} \left|x \right\rangle \otimes \left|q \oplus f(x) \right\rangle }

ここで入力状態 \left|x \right\rangleは入力ビット列xを計算基底で表した状態、 \left|q \right\rangleは補助ビット、 \oplusはmod 2の加算(XOR演算)です。xが探索問題の解であるかどうかは、補助ビットqが反転したかどうかをチェックすることでわかるようになっています。すなわち

\displaystyle{ \left|x \right\rangle \left|0 \right\rangle \xrightarrow{\mathcal{O}_f} \left|x \right\rangle \left|f(x) \right\rangle }

他にも、補助ビットを \left|- \right\rangle = (\left|0 \right\rangle - \left|1 \right\rangle)/\sqrt{2}とセットしておけば

\displaystyle{ \left|x \right\rangle \otimes \left|- \right\rangle \xrightarrow{\mathcal{O}_f} (-)^{f(x)} \left|x \right\rangle \otimes \left|- \right\rangle }

となり、xが探索問題の解のときにのみ状態の位相が反転するようにも設定することが可能です。

オラクル \mathcal{O}_fのもっとも大きな特徴の一つは、入力状態が重ね合わせであってもそのまま動作することです。例えば、入力状態として全ての状態の重ね合わせ N^{-1/2} \sum_x \left|x \right\rangleをとり、補助ビットを \left|- \right\rangleとすれば

\displaystyle{ \frac{1}{\sqrt{N}} \sum_x \left|x \right\rangle \otimes \left|- \right\rangle \xrightarrow{\mathcal{O}_f} \frac{1}{\sqrt{N}} \sum_x (-1)^{f(x)} \left|x \right\rangle \otimes \left|- \right\rangle }

となります。このようにxが解のときのみ位相が反転する性質をうまく用いて解を見つけるのが、グローバーのアルゴリズムの概要です。古典ではオラクルの呼び出し回数は項目数Nのオーダーとなっていましたが、量子回路模型のグローバーのアルゴリズムでは \mathcal{O}(\sqrt{N})で解けることが知られています[1]。

データベース探索をAQCで解く

項目に番号を付与し、これらに直交規格化ベクトル \left| 0\right\rangle, \left| 1\right\rangle, \dots, \left| N-1\right\rangleを対応させます。このうち特定の状態 \left| m \right\rangleを断熱量子計算で求めることが今回の問題です。

全ハミルトニアン

終状態のハミルトニアン

断熱計算終了時には、状態 \left| m\right\rangleのみを基底状態に持つようなハミルトニアンになっていなければ、探索が終了したとは言えないでしょう。よって

\displaystyle{ H_m \left| m \right\rangle = 0 \\ H_m \left| j \right\rangle = \left| j \right\rangle }

のように、状態 \left| m\right\rangleは固有値0、そしてそれ以外の状態 \left| j \right\rangleでは固有値1となるようなハミルトニアンを設定します。上の議論から、終状態のハミルトニアンの簡単な形として

\displaystyle{ H_m = I - \left| m\right\rangle \left\langle m\right| }

を選びます。

初期状態のハミルトニアン

AQCにおいて最初の状態は自明に用意できる状態を基底状態にもつハミルトニアンとします。よって全ての可能な状態を同じ重みで重ね合わせた状態を初期状態として

\displaystyle{ \left| \psi_0 \right\rangle = \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1} \left| i \right\rangle }

のように書きます。終状態のハミルトニアンと同様の議論から、これを基底状態に持つようなハミルトニアンとして

\displaystyle{ H_0 = I - \left| \psi_0 \right\rangle \left\langle \psi_0 \right| }

を選択します。

全ハミルトニアン

よってこの問題における全ハミルトニアンを

\displaystyle{ H(t) = (1-f(s)) H_0 + f(s) H_m }

のようにして、断熱的に時間発展させることを考えます。ここで s = t/T \ (0\leq t \leq T)で、Tはアニーリング時間です。そして f(s)は f(0)=0, f(1)=1のような境界条件を持つ、単調増加関数とします[2]。

スペクトル構造

ハミルトニアンは \left| m\right\rangleと、それに直交する \left| m_\perp \right\rangle = \frac{1}{\sqrt{N-1}} \sum_{i\neq m} \left| i\right\rangleのみを使って書けます。よって初期条件をこの空間内にとると、系はこの2つの状態ベクトルで張られるような2次元空間の中で時間発展を行います。この2つの状態を基底とするハミルトニアンは以下のように表現されます。

\displaystyle{ H = \left( \begin{array}{cc} \left\langle m \right| H \left| m \right\rangle & \left\langle m \right| H \left| m_\perp \right\rangle \\ \left\langle m_\perp \right| H \left| m \right\rangle & \left\langle m_\perp \right| H \left| m_\perp \right\rangle \end{array} \right) }

これを計算すると

\displaystyle{ H = \frac{1}{2} \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) + \frac{\Delta}{2} \left( \begin{array}{cc} \cos \theta & \sin \theta \\ \sin \theta & - \cos \theta \end{array} \right) \tag{1} }

のように変形することができます。ここで

\displaystyle{ \cos \theta = \frac{1}{\Delta } (1-2(1-f)(1-\frac{1}{N})) \\ \sin \theta = \frac{2}{\Delta } (1-f) \frac{1}{\sqrt{N}} \sqrt{1-\frac{1}{N}} }

さらに \cos^2 \theta + \sin^2 \theta = 1より

\displaystyle{ \Delta = \sqrt{(1-2f)^2 + \frac{4}{N} f (1-f)} }

と求まります。
(1)式の固有値は

\displaystyle{ \epsilon_0 = \frac{1}{2} (1-\Delta), \ \epsilon_1 = \frac{1}{2} (1+\Delta) }

よって \Deltaは基底状態と第一励起状態のエネルギー差を表し、スペクトル構造はE = 1/2を挟んで対称な形であることがわかります[2][3]。さらに \Deltaはその関数の形から f=1/2で最小の値をとります。よって、スペクトル構造を図示すると、その概形は以下のようになります[4]。

Spectrum of adiabatic Grover.
Adiabatic Groverのスペクトル構造

スケジューリング

式変形

次はこの問題において最適な f(s)の形、すなわちアニーリングスケジュールについて考えてみましょう。断熱定理より

\displaystyle{ \frac{df}{ds} \leq C T \Delta^2 }

の条件を満たしていれば、エネルギーギャップを飛び越えることなく、基底状態のまま系が変化していきます。詳細な計算を行うと C=1/ \left\langle \epsilon_1 \right| \frac{dH}{df} \left| \epsilon_0 \right\rangle >0 であることがわかります。証明は省略しますが、このCはどんなにNが大きくなっても有界に留まり、Nによらない定数で抑えられます。
f(s)の満たすべきギリギリの条件は上式の等号をとることで導くことができます。 \Deltaの表記より

\displaystyle{ \frac{df}{ds} = CT (1-4\frac{N-1}{N} f(1-f)) }

これを \tan^{-1}の積分公式を用いて積分すると

\displaystyle{ s = \frac{1}{CT} \frac{N}{\sqrt{N-1}} (\tan^{-1} (\sqrt{N-1}(2f-1)) + \tan^{-1} \sqrt{N-1}) \tag{2} }

となります[2][3][4]。

可視化とその物理的意味

(2)式を横軸s, 縦軸f(s)にしてプロットすると以下のようになります。

Plot of Evolution function f(s)
アニーリングスケジュール

単純な線形スケジュールでないことがわかります。これはエネルギーギャップが大きい部分(図の開始と終了付近)では状態を高速に変化させ、エネルギーギャップが小さい部分(図の真ん中付近)では状態を劇的に変化させないようにすることで、基底状態から励起状態へ状態を遷移させることなく、求めたいデータベース検索結果 \left| m \right\rangleの状態を目指すことを意味しています[2][3][4]。

古典に比べてどれくらい高速化されているのか

このとき、検索にかかるおよそのアニーリング時間は(2)式で s = 1, f = 1の境界条件より

\displaystyle{ T \xrightarrow{N \gg 1} \frac{\pi}{2C }\sqrt{N} \propto \sqrt{N} }

となります。この結果は量子回路におけるグローバーのアルゴリズムと同じ計算時間[1]になっており、確かに古典の場合 \mathcal{O} (N)に比べて2乗の高速化(かかる時間は平方根)になっていることがわかります[2][3][4]。

解析のポイント

前回の接合木問題とグローバーでのAQCの解析のポイントは、オラクルの性質によりヒルベルト空間の部分空間のみを考えればよいということです。他にも、AQCで何かしら上述と同様の主張を行う際は、ハミルトニアンの対称性を用いて部分空間のみを考慮して計算量・エネルギーギャップを解析することがあります。

結言

今回はAQCでグローバーのアルゴリズムを解く、その解法と計算量などの見積もりをご紹介いたしました。グローバーのアルゴリズム自体が汎用性が高いため、これが量子アニーリングでもできるというだけでも応用分野がかなり広がりそうです。

参考文献

文責

中村翔、株式会社 Jij
Sho K. NAKAMURA, Jij Inc.
憂いの篩 -Pensieve-

※ 疑問点や間違いなどございましたら、お気軽にブログ上でご質問ください。