断熱量子計算によるHHLアルゴリズム

この記事の概要

Subasi et al., 2018, "Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing"を読んだので、その理解を深めるためのアウトプットとして作成したものです。

この記事の概要
問題設定
断熱量子計算
結言
参考文献
文責

問題設定

$N \times N$ のエルミート行列 $A$ とベクトル ${\bf b} = (b_1, \dots, b_N)^T$ があったとき、以下の連立一次方程式

$\displaystyle{ A {\bf x} = {\bf b} }$

を満たす ${\bf x} = (x_1, \dots, x_N)^T$ を求めよ、という問題です。答えとなる

$\displaystyle{ | {\bf x} \rangle := \frac{\sum_{j=1}^N x_j | j \rangle }{\sqrt{\sum_{j=1}^N |x_j|^2}} = \frac{A^{-1} | {\bf b} \rangle}{\|A^{-1} | {\bf b} \rangle \|} }$

という量子状態が求まれば、この問題が解けたことになります。ここで

$\displaystyle{ | {\bf b} \rangle = \frac{\sum_{j=1}^N b_j | j \rangle }{\sqrt{\sum_{j=1}^N |b_j|^2}} }$

です。さらに $A$ には逆行列が存在し、 $\| A \| \leq 1$ とします。
実際には $\epsilon$ の精度でこの問題を解きたいので、求まった状態 $\rho_x$ が

$\displaystyle{ \frac{1}{2} {\rm Tr} | \rho_x - | {\bf x} \rangle \langle {\bf x} | | \leq \epsilon }$

を満たすアルゴリズムを作ることが、この論文のゴールです。

断熱量子計算

ハミルトニアン

ハミルトニアンを

$\displaystyle{ H(s):= A(s) P^\perp_{\bar{b}} A(s) }$

のように定めます。ここで

$\displaystyle{ A(s) : = (1-s) Z \otimes \mathbb{1} + sX \otimes A \\ | \bar{b} \rangle := | + \rangle \otimes | b\rangle \\ P^\perp_{\bar{b}} := \mathbb{1} - | \bar{b} \rangle \langle \bar{b} | }$

です。さらに $X, Z$ は1量子ビットにおけるパウリ演算子、 $| + \rangle$ は $X$ の固有状態、 $s \in [0, 1$ ]はアニーリング時間を表すパラメータです。このハミルトニアンは $2N$ 次元のヒルベルト空間を持ちます。これは $N$ 次元の行列 $A$ に加えて、1つの補助量子ビットを用いるためです。補助量子ビットを用いることで、 $A(s)$ は全ての $s$ に対して逆行列が存在することが保証されます。

基底状態とエネルギーギャップ

基底状態

$\displaystyle{ | x(s) \rangle := \frac{A(s)^{-1} | \bar{b} \rangle}{\| A(s)^{-1} | \bar{b} \rangle \|} }$

は基底状態で、 $H(s) | x(s) \rangle = 0$ を満たします。これが唯一存在する基底状態です。 $s$ を $0 \rightarrow 1$ に増加させると

$\displaystyle{ | {\bf x}(0) \rangle = | - \rangle \otimes | {\bf b} \rangle \rightarrow | {\bf x}(1) \rangle = | + \rangle \otimes | {\bf x} \rangle }$

のように変化します。

エネルギーギャップ

上述のハミルトニアンにおける基底状態と第1励起状態のエネルギーギャップは

$\displaystyle{ \Delta (s) \geq \Delta^\ast (s) := (1-s)^2 + (s/\kappa)^2 }$

を満たします。ここで $\kappa$ は行列 $A$ の条件数です。

条件数とは、その問題のコンピュータでの数値解析しやすさの尺度でその問題がどれだけ数値解析に適しているかを表す指標です。小さな値ほど解析しやすい良条件で、大きな値ほど解析しにくい悪条件となります。

Randomization Method (RM)

通常の量子アニーリングでは $s$ を連続に変化させます。しかしここでは離散的に変化させることで、基底状態の近似射影測定を効果的に計算することができます。このとき、離散的にした $s$ を一定に保つ時間間隔をランダムに決定するため、これをRandomization Method (RM)と呼びます。
RMの計算時間は $\mathcal{O} (L^2 / (\epsilon \Delta))$ であることが知られています。ここで $L$ はパスの長さ

$\displaystyle{ L := \int_0^1 ds \| | \partial_s x(s) \rangle \| }$

そして $\Delta$ はハミルトニアンの最小エネルギーギャップです。

アニーリングスケジュール

HHLの断熱量子計算アルゴリズムにおいては

$\displaystyle{ s(v) := \frac{e^{v\frac{\sqrt{1+\kappa^2}}{\sqrt{2} \kappa}} + 2\kappa^2 - \kappa^2 e^{-v \frac{\sqrt{1+\kappa^2}}{\sqrt{2} \kappa}}}{2(1+\kappa^2)} \ (v_a \leq v \leq v_b) }$

というアニーリングスケジュールを組むことで、基底状態を求めることができます。ここで

$\displaystyle{ v_a := \frac{\sqrt{2} \kappa}{\sqrt{1+\kappa^2}} \log (\kappa \sqrt{1+ \kappa^2} -\kappa^2) \\ v_b := \frac{\sqrt{2} \kappa}{\sqrt{1+\kappa^2}} \log (\sqrt{1+ \kappa^2} +1) }$

です。このアニーリングスケジュールを $v_a < v^1 < v^2 < \cdots < v^q =v_b$ のように $q$ 個に分割します。ここで $v^j = v_a + j\delta \ (j=1, \dots, q), \delta = (v_b - v_a)/q$ 、そして $s^0 = s(v_a) = 0, s^q = s(v_b) = 1$ です。このRMステップ数は $q = \Theta (\log^2 (\kappa) / \epsilon)$ で与えられます。このように $q$ を選ぶことで

$\displaystyle{ 1 - |\langle x(s^j) | x(s^{j+1}) \rangle|^2 = \mathcal{O}(\epsilon/q) }$

となります。

アルゴリズムと計算時間

$j= 1, \dots, q$ において、ランダムな時間の長さ $t^j$ の元で状態を時間発展させます。 $t^j \in [0, 2\pi / \Delta^\ast (s^j)$ ]の一様乱数です。ここで時間発展させるとは、以下のように演算子を次々に掛け合わせていくことに対応します。

$\displaystyle{ e^{-it^q H(s^q)} \cdots e^{-it^1 H(s^1)} | {\bf b} \rangle }$

この方法で解を求めるのにかかる総計算時間は、 $T: = \sum_{j=1}^q \langle t^j \rangle$ を計算して

$\displaystyle{ T = \mathcal{O} (\kappa^2 \log (\kappa) / \epsilon) }$

と算出されます。

アルゴリズムの改良 (エネルギーギャップの増幅)

シンプルな考え方として、このアルゴリズムを高速化する方法の1つに $H(s)$ のエネルギーギャップを大きくすることが考えられます。そのためには、行列の固有値 $\lambda > 0 \ (\lambda \ll 1)$ を大きくするような、例えば固有値を $\lambda \rightarrow \pm \sqrt{\lambda}$ となるような変換を施せば良いです。
そこで新しいハミルトニアンとして、以下のようなものを考えます。

$\displaystyle{ H'(s) := \sigma^+ \otimes A(s) P^\perp_{\bar{b}} + \sigma^- \otimes P^\perp_{\bar{b}} A(s) }$

ここで $\sigma^\pm = (X \pm i Y)/2$ は1つの補助量子ビットにかかる上昇・下降演算子です。このハミルトニアンは $4N$ 次元のヒルベルト空間を持ちます。さらに

$\displaystyle{ (H'(s))^2 = \left( \begin{array}{cc} H(s) & {\bf 0} \\ {\bf 0} & P^\perp_{\bar{b}}(A(s))^2 P^\perp_{\bar{b}} \end{array} \right) }$

となります。上の行列は各ブロックが $2N\times 2N$ の行列となります。 $B(s) = A(s) P^\perp_{\bar{b}}$ を用いると、対角ブロックはそれぞれ $B(s)^\dagger B(s), B(s) B(s)^\dagger$ と書けます。このことから、このハミルトニアンは元々のハミルトニアン $H(s)$ と同じエネルギースペクトルを持ちます。

この変換によって、エネルギーギャップは $\Delta^\ast (s) \rightarrow \sqrt{\Delta^\ast(s)}$ となります。よって、時間間隔も $t^j \in [0, 2\pi / \sqrt{\Delta^\ast (s^j)}$ ]の一様乱数として選ぶことができます。このとき同様に $T: = \sum_{j=1}^q \langle t^j \rangle$ を計算して