補遺: グローバー探索問題

データベース探索問題は、量子計算の速さを測るための清潔な試験台です。$N$ 個の候補の中から一つの正解を探すだけなら、古典的には平均して $O(N)$ 回の照会が必要です。Grover探索はこれを $O(\sqrt{N})$ にします。驚くべきことに、量子断熱計算でも、スケジュールをギャップに合わせて調整すると同じ $O(\sqrt{N})$ が出ます。

ここでは、講義ノートの計算に沿って、探索問題を二次元部分空間へ畳み込み、ギャップを計算し、局所断熱スケジュールを積分します。

1. 問題設定

候補状態を

$$|0⟩,|1⟩,\dots ,|N-1⟩$$

とします。正解を $|m⟩$ とします。探索問題の目標ハミルトニアンは

$${\hat{H}}_m=\hat{I}-|m⟩⟨m|$$

です。正解状態に作用させると

$${\hat{H}}_m|m⟩=0$$

であり、それ以外の直交状態にはエネルギー1を与えます。つまり、正解だけが基底状態です。

初期状態は一様重ね合わせ

$$|s⟩=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩$$

とし、その基底状態を持つハミルトニアンを

$${\hat{H}}_s=\hat{I}-|s⟩⟨s|$$

とします。断熱探索では

$$\hat{H}(q)=(1-q){\hat{H}}_s+q{\hat{H}}_m,0\le q\le 1$$

をゆっくり変えます。

コラム 2024大学院講義 第9回 1:13:00-1:18:00

探索問題で量子加速を測る

講義では、図書館の本を一冊探すような問題としてデータベース探索が導入されました。古典的に一つずつ見るなら $O(N)$、Grover型の量子探索なら $O(\sqrt N)$。この二乗加速は、量子計算が何を得意にし得るのかを測る、よくできたものさしです。

ただし「二乗加速は小さい」と軽く言うと、話を誤ります。$N$ が巨大になったとき、$N$ と $\sqrt N$ の差は圧倒的です。量子計算の強みを語るには、誇張も過小評価もいらず、スケーリングをそのまま見るのが一番強いです。

2. 二次元部分空間への縮約

正解以外をまとめた状態

$$|r⟩=\frac{1}{\sqrt{N-1}}\sum _{x\ne m}|x⟩$$

を導入します。一様状態は

$$|s⟩=\frac{1}{\sqrt{N}}|m⟩+\sqrt{\frac{N-1}{N}}|r⟩$$

です。ハミルトニアン $\hat{H}(q)$ は、$|m⟩,|r⟩$ で張られる二次元空間の中で閉じています。したがって、巨大な $N$ 次元行列を直接扱わずに、二次元行列として計算できます。

基底 $(|m⟩,|r⟩)$ で書くと、

$$\hat{H}(q)=\left(\begin{array}{cc}(1-q)(1-\frac{1}{N})& -(1-q)\frac{\sqrt{N-1}}{N}\\ -(1-q)\frac{\sqrt{N-1}}{N}& q+(1-q)\frac{1}{N}\end{array}\right)$$

です。単位行列に比例する部分はエネルギー差に影響しないので、重要なのは二つの固有値の差です。

コラム 2024大学院講義 第9回 1:30:00-1:42:00

答えとそれ以外に世界を畳む

$N$ 次元の行列をそのまま対角化するのは、手計算の仕事ではありません。けれども探索問題では、正解 $|m\rangle$ と「正解以外の一様重ね合わせ」$|r\rangle$ だけが本質的です。講義では、この見方を線形代数の自由さとして説明していました。

行列表現は一つではありません。何を見たいかに合わせて基底を選びます。探索問題では、正解と非正解に世界を畳むことで、量子加速の計算が人間の手に戻ってきます。

3. エネルギーギャップ

二次元行列の固有値差を計算すると、

$$\mathrm{\Delta }(q)=\sqrt{1-4(1-\frac{1}{N})q(1-q)}$$

です。最小値は $q=1/2$ で

$${\mathrm{\Delta }}_{min}=\frac{1}{\sqrt{N}}$$

となります。ここが探索問題の難所です。候補数 $N$ が大きくなるほど、途中のギャップは小さくなります。

線形スケジュール $q=t/T$ で全体を同じ速さで動かすと、断熱条件は最小ギャップに支配され、

$$T=O\left(\frac{1}{{\mathrm{\Delta }}_{min}^2}\right)=O(N)$$

となります。これでは古典探索と同じスケーリングです。

4. 局所断熱スケジュール

そこで、ギャップが大きい場所では速く進み、ギャップが小さい場所では遅く進むようにします。局所断熱条件を

$$\frac{dq}{dt}=ϵ\mathrm{\Delta }(q{)}^2$$

と置きます。$ϵ\ll 1$ は断熱性の余裕を表す小さな定数です。全時間は

$$T={\int }_0^1\frac{dq}{ϵ\mathrm{\Delta }(q{)}^2}$$

です。$\mathrm{\Delta }(q{)}^2=1-4(1-1/N)q(1-q)$ を代入して積分すると、

$$T=\frac{N}{2ϵ\sqrt{N-1}}[\arctan \sqrt{N-1}-\arctan (-\sqrt{N-1})]$$

を得ます。大きな $N$ では

$$T\simeq \frac{\pi }{2ϵ}\sqrt{N}$$

です。これが断熱版Grover探索の二乗加速です。

コラム 2024大学院講義 第10回 0:56:00-0:59:00

局所スケジュールで $\sqrt N$ へ

講義では、線形に進めるだけでは $O(N)$ になってしまうところを、ギャップに応じて速度を変えることで $O(\sqrt N)$ が出る、と強調されました。ここには断熱計算の希望が詰まっています。ハミルトニアンの経路が同じでも、進み方を変えるだけで計算時間のスケーリングが変わります。

同時に、難しさもここにあります。一般の問題でギャップを評価できなければ、どこで遅くすべきか分かりません。Grover探索は、ギャップが解析できる幸運な例であり、量子アニーリングの計算量解析の理想的な練習台です。

5. ゲート型Grover探索との関係

ゲート型Grover探索では、オラクルと反転操作を交互に作用させ、正解状態の振幅を増幅します。断熱版では、初期ハミルトニアンから目標ハミルトニアンへ連続的に変形し、基底状態を追いかけます。操作の見た目は違いますが、得られるスケーリングは同じです。

$$O(N)⟶O(\sqrt{N})$$

この一致は、量子アニーリングが「ゲート型とは別の機械だから遅い」と単純には言えないことを教えてくれます。少なくとも、問題の構造とスケジュールを正しく合わせられる場合には、断熱時間発展も量子加速を再現できます。

6. QAの収束定理への橋

Grover探索では、ギャップを明示的に計算できました。だから、局所断熱スケジュールも明示的に積分できました。一般のIsing最適化問題では、同じことは簡単ではありません。ギャップを厳密に求めること自体が、元の問題を解くのと同じくらい難しくなり得ます。

そこで、補遺: QAの収束定理では、厳密な最小ギャップを求める代わりに、Perron--Frobenius型の評価で下限を与えます。得られるスケジュールは非常に遅いですが、「有限サイズなら十分ゆっくり横磁場を落とせば基底状態へ行く」という保証を与えます。Grover探索は、ギャップが見える特別な場合。収束定理は、ギャップが見えない一般の場合の保険です。

PDF画像では、大学院講義2024板書 p.28からp.33にかけて、探索ハミルトニアン、二次元縮約、局所断熱スケジュールの計算を確認できます。参考文献: [1]。

参考文献

1. Jérémie Roland, Nicolas J. Cerf, “Quantum search by local adiabatic evolution,” Physical Review A 65, 042308 (2002). 出典