Grover アルゴリズムを微分幾何学的に調べた研究の紹介

はじめに

Grover アルゴリズム^[1]は今でも量子コンピュータの最も基本的で重要なアルゴリズムとして知られているものである. 論文^[2]では Grover アルゴリズムを複素射影空間の微分幾何を使って調べ, 幾何学的に最適な量子探索であることが述べられている. また Grover アルゴリズムを任意の量子状態から開始できるよう一般化する方法や entanglement を幾何学的な量で計算し, Grover アルゴリズムで entanglement がどのように変化するか調べる方法が提案されている.

本記事では論文^[2:1]で説明されていない複素射影空間の微分幾何のやや細かい内容の説明を補足し, 論文^[2:2]で得られている結果の紹介をする.

微分幾何に慣れている方は entanglement の計算や一般化された Grover アルゴリズムの節から読んでいただければと思います.

対象読者

• 量子コンピュータと微分幾何とのつながりに興味のある方.
• 量子探索の Grover アルゴリズムを知っている方.
• 幾何学の多様体, 測地線, 主束の接続^[3]を知っている方.

Grover アルゴリズム

以下 Grover アルゴリズムの説明を行うが, 詳細は教科書^[1:1]や Qiskit Textbook などを参照.

量子探索の設定

本記事では多重量子ビット ($n$ 量子ビット) で表される量子状態を扱い, 複素ヒルベルト空間 $\mathbb{C}^N$ ($N=2^n$) を考える. $\Ket{\psi_1}=(a_0,\dots.a_{N-1}), \Ket{\psi_2}=(b_0,\dots.b_{N-1}) \in \mathbb{C}^N$ に対してエルミート計量^[4] $\langle \cdot | \cdot \rangle$ を以下のように定義する.

$$\langle \psi_1 | \psi_2 \rangle := \sum_{k=0}^{N-1} \overline{a_k}\:b_k.$$

計算基底を $\Ket{0}=(1,0,\dots,0), \dots, \Ket{N-1}=(0,\dots,0, 1)$ とし, これらを探索空間とする. 量子探索での探索対象の番号は論文^[2:3]と同様に $w$ ($0 \leq w \leq N-1$) ひとつだけとする.

探索対象の番号をひとつだけとしたのは, 論文^[2:4]の結果である entaglement の計算や Grover アルゴリズムの計算時間の評価を行うためである. 本記事で説明している Grover アルゴリズムと複素射影空間の測地線や距離関数との関係の話などでは探索対象の番号が複数である場合を考えても問題ない.

探索候補以外の状態の重ね合わせを

$$\ket{r}:= \frac{1}{\sqrt{N-1}}\sum_{x \neq w}\ket{x} \tag{1}$$

とし, 計算基底の全ての重ね合わせ状態を

$$\ket{a}:= \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\ket{x} \tag{2}$$

とすると, ある実数 $\theta$ に対して

$$\begin{aligned} \langle r | a \rangle &= \sqrt{\frac{N-1}{N}} = \cos(\theta/2), \\ \langle w | a \rangle &= \frac{1}{\sqrt{N}} = \sin(\theta/2), \tag{3} \end{aligned}$$

と書けるので,

$$\ket{a} = \cos\left( \frac{\theta}{2} \right) \ket{r} + \sin\left( \frac{\theta}{2} \right)\ket{w} \tag{4}$$

と表せる.

Grover iteration

Grover アルゴリズムは計算基底の全ての重ね合わせ状態 $\ket{a}$ に対して次の Grover iteration $G$ を繰り返し適用することで量子状態を探索対象の番号だけの状態 $\ket{w}$ に近づけるものである.

$$G := I_{a} \circ I_{r}. \tag{5}$$

$I_{r}$, $I_{a}$ はそれぞれ $\ket{r}$, $\ket{a}$ についての鏡映変換 (reflection) である. $I_{r}$ を量子ゲートで実装するには, 計算基底のそれぞれの要素の番号が探索対象の番号かどうかを識別する必要があるので, 考えている探索に応じたオラクルが使われる.

量子状態 $\ket{\psi}$ による複素ヒルベルト空間 $\mathbb{C}^N$ の直交分解 $\mathbb{C}^N = \mathbb{C}\ket{\psi} \oplus \ket{\psi}^{\bot}$ を考えると, 任意のベクトル $\ket{\varphi}$ はこの分解に従って

$$\ket{\varphi} = \ket{\psi} \langle \psi | \varphi \rangle + (id_{\mathbb{C}^N}-\ket{\psi}\bra{\psi})(\ket{\varphi})$$

と表せる. $id_{\mathbb{C}^N}$ は $\mathbb{C}^N$ の恒等変換を, $\ket{\psi}\bra{\psi}$ は射影演算子^[5]を表す. $id_{\mathbb{C}^N}-\ket{\psi}\bra{\psi}$ は $\ket{\varphi}$ の $\ket{\psi}$ に直交する成分を与える変換である. $\ket{\varphi}$ の $\ket{\psi}$ についての鏡映変換は $\ket{\psi}$ に直交する成分の符号だけを反転させるものなので, $\ket{\varphi}$ から $\ket{\psi}$ に直交する成分を $2$ 回引くという変換として定義する.

$$I_{\psi} := id_{\mathbb{C}^N} - 2 \,(id_{\mathbb{C}^N} - \ket{\psi}\bra{\psi}) = 2 \ket{\psi}\bra{\psi} - id_{\mathbb{C}^N}.$$

論文^[2:5]で使われている鏡映変換は本記事のものと異なる (直交成分でなく平行成分を反転させる流儀) が, Grover iteration の定義は同じである.

鏡映変換の定義式に従うと ($\ket{a}$ で $\theta/2$ をとったのはここで $G$ に対応する回転角を $\theta$ にするため),

$$\begin{aligned} G\ket{r} &= I_{a} \circ I_{r} \ket{r} = I_{a}\ket{r} = \cos(\theta) \ket{r} + \sin(\theta)\ket{w},\\ G\ket{w} &= I_{a} \circ I_{r} \ket{w} = -I_{a}\ket{w} = - \sin(\theta) \ket{r} + \cos(\theta)\ket{w},\\ \end{aligned}$$

なので, $G$ は $\{ \ket{r}, \ket{w} \}$ を正規直交基底とする $\mathbb{C}^N$ の実 $2$ 次元部分空間内の線形変換とみなすことができて, 表現行列 $U_a(\theta)$ は

$$U_a(\theta) = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix} \tag{6}$$

である.

複素射影空間と Hopf fibration の接続

$n$ 量子ビットで表される量子状態を表す空間として複素射影空間 $\mathbb{C}P^{N-1}$ を考える. 本節では複素射影空間と Hopf fibration についての微分幾何学的な用語の説明を行う. 複素射影空間と Hopf fibration の定義については以下の記事にまとめた.

https://zenn.dev/quetta_kazunoko/articles/hopf-fibration-bloch-sphere

この記事の記号を本記事でも使い, $\mathbb{C}^N$ に対応する Hopf fibration を

$$f: S^{2N-1} \longrightarrow \mathbb{C}P^{N-1} \tag{7}$$

で表す.

複素射影空間の斉次座標と非斉次座標

複素射影空間 $\mathbb{C}P^{N-1}$ 上の点 $\Ket{\psi}$ は $\mathbb{C}^{N}$ の座標 $(z_0, \dots, z_{N-1})$ を使って表せるが, 複素射影空間は 0 でない複素スカラ―倍で互いにうつり合う $\mathbb{C}^N$ のベクトルを同一視して得られる空間であり, その同一視を考慮した座標を

$$f(\Ket{\psi}) = [z_0:\dots:z_{N-1}]$$

と書く. この座標を斉次座標という. この座標は $\mathbb{C}^{N}$ の点と $\mathbb{C}P^{N-1}$ の点の対応を見るには便利だが, 多様体の局所座標としては使えないので, $\mathbb{C}P^{N-1}$ の多様体としての計算を行うときは以下の非斉次座標を使う. $z_{N-1}$ が $[z_0:\dots:z_{N-1}]$ の $0$ でない成分であるとき,

$$\zeta_0 = \frac{z_0}{z_{N-1}}, \dots, \:\zeta_{N-2} = \frac{z_{N-2}}{{z_{N-1}}}.$$

$z_{N-1}$ 以外の成分でも $0$ でなければ同様に非斉次座標が定義できる.

複素射影空間の Fubini-Study 計量

主束

Hopf fibration (式 (7)) は $\Ket{\psi} \in S^{2N-1}$ に許された任意の複素数倍 $e^{i\theta}\Ket{\psi}$ ($\theta \in \mathbb{R}$) に対して $f(\Ket{\psi})=f(e^{i\theta}\Ket{\psi})$ となることから $1$ 次のユニタリ群 $U(1)$ を構造群とする主束 (principal bundle) である^[3:1].

Hopf fibration の垂直部分空間と水平部分空間

以下複素ヒルベルト空間 $\mathbb{C}^N$ の各点 $\Ket{\psi}$ での接空間を $T_{\Ket{\psi}}\mathbb{C}^N = \mathbb{C}^N$ とみなす. Grover アルゴリズムの節で説明したエルミート計量 $\langle \cdot | \cdot \rangle$ の実部 $\text{Re}\langle \cdot | \cdot \rangle$ はリーマン計量であり, $\mathbb{C}^{N}$ の $\mathbb{R}^{2N}$ としての標準計量を定める. 球面 $S^{2N-1}$ 上にこの標準計量を制限すると標準的な球面の計量と一致する. 点 $\Ket{\psi} \in S^{2N-1}$ での球面の接空間は

$$T_{\Ket{\psi}}S^{2N-1} = \{\, \Ket{\varphi} \in \mathbb{C}^{N} \:|\: \text{Re}\langle \varphi | \psi \rangle = 0 \} \tag{8}$$

となる. $\Ket{\psi}$ を通る主束のファイバー $f^{-1}(f(\Ket{\psi}))=\{ e^{i\theta}\Ket{\psi} \:|\: \theta \in [0, 2\pi) \}$ (量子力学での射線 (ray)^[5:1]) の接空間 $V_{\Ket{\psi}} \subset T_{\Ket{\psi}}S^{2N-1}$ は以下のように表され, $\Ket{\psi}$ での垂直部分空間という.

$$V_{\Ket{\psi}} = \{i\theta \Ket{\psi} \:|\: \theta \in \mathbb{R} \}. \tag{9}$$

リーマン計量 $\text{Re}\langle \cdot | \cdot \rangle$ について $V_{\Ket{\psi}}$ に直交する $T_{\Ket{\psi}}S^{2N-1}$ の部分空間 $H_{\Ket{\psi}}$ を $\Ket{\psi}$ での水平部分空間という.

$$H_{\Ket{\psi}} = \{\Ket{\varphi} \in T_{\Ket{\psi}}S^{2N-1} \:|\: \text{Re}\langle \varphi \,|\, i \psi \rangle = 0 \}. \tag{10}$$

エルミート計量 $\langle \cdot | \cdot \rangle$ の性質と式 (8), (10) から水平部分空間は以下のようにも表せる.

$$H_{\Ket{\psi}} = \{\Ket{\varphi} \in T_{\Ket{\psi}}S^{2N-1} \:|\: \langle \varphi | \psi \rangle = 0 \}. \tag{11}$$

$S^{2N-1}$ 上の各点 $\Ket{\psi}$ について水平部分空間 $H_{\Ket{\psi}}$ は滑らかに変化するので, この水平部分空間を与える対応が Hopf fibration の接続を与える (主束の接続^[3:2]).

水平部分空間の意味

$S^{2N-1}$ 上の各点で上記の水平部分空間が与えられたとき, 複素射影空間上の滑らかな曲線 $c: [0,1] \longrightarrow \mathbb{C}P^{N-1}$ と $f(\Ket{\psi})=c(0)$ を満たす点 $\Ket{\psi} \in S^{2N-1}$ に対して, 以下を満たす曲線 $\tilde{c}: [0,1] \longrightarrow S^{2N-1}$ がひとつだけ定まる. 任意の $t \in [0,1]$ に対して,

$$\begin{aligned} \tilde{c}(0) &= \ket{\psi}, \\ f \circ \tilde{c}(t) &= c(t), \\ \dot{\tilde{c}}(t) &\in H_{\tilde{c}(t)}. \end{aligned}$$

この $\tilde{c}$ を $\Ket{\psi}$ に対する $c$ の水平リフトという. 曲線 $c$ は量子状態 $c(0) \in \mathbb{C}P^{N-1}$ の時間発展を表し, $\Ket{\psi}$ を選ぶことは量子状態の phase をひとつ選ぶことを意味する. 水平リフト $\tilde{c}$ は (接ベクトルが曲線を近似できるくらいの) 短い時間ではリーマン計量 $\text{Re}\langle \cdot | \cdot \rangle$ について phase が変化しないよう純粋に量子状態 $c(t)$ を $\mathbb{C}P^{N-1}$ の元として変化させる.

「短い時間ではリーマン計量 $\text{Re}\langle \cdot | \cdot \rangle$ について phase が変化しないよう」という部分が式 (9), (10) によって phase が変化する垂直部分空間 $V_{\tilde{c}(t)}$ と垂直, すなわち水平部分空間の定義で表現されている.

Fubini-Study 計量

Hopf fibration $f: S^{2N-1} \longrightarrow \mathbb{C}P^{N-1}$ の $\Ket{\psi} \in S^{2N-1}$ での微分写像 $df_{\Ket{\psi}}$ を $H_{\Ket{\psi}}$ 上に制限すると $H_{\Ket{\psi}}$ と $T_{f(\Ket{\psi})}\mathbb{C}P^{N-1}$ との線形同型写像となる. これを使ってリーマン計量 $\text{Re}\langle \cdot | \cdot \rangle$ を $T_{f(\Ket{\psi})}\mathbb{C}P^{N-1}$ 上に誘導した計量を Fubini-Study 計量^[6][7]という.

球面 $S^{2N-1}$ 上の各点 $\Ket{\psi}$ で phase が変化しない方向 $H_{\Ket{\psi}}$ の計量を Hopf fibration を通して $T_{f(\Ket{\psi})}\mathbb{C}P^{N-1}$ に移植したものが Fubini-Study 計量.

以下, 球面 $S^{2N-1}$ の測地線とはリーマン計量 $\text{Re}\langle \cdot | \cdot \rangle$ についての測地線^[3:3]を, 複素射影空間 $\mathbb{C}P^{N-1}$ の測地線とは Fubini-Study 計量についての測地線のこととする.

球面 $S^{2N-1}$ の水平測地線と複素射影空間 $\mathbb{C}P^{N-1}$ の測地線

球面 $S^{2N-1}$ の測地線は必ず大円 ($\mathbb{R}^{2N}$ の原点を通る $2$ 次元部分空間と球面 $S^{2N-1}$ とが交わってできる曲線) の一部として与えられる. 球面の測地線 $\ket{\psi(s)}$ で常に水平部分空間に接しているもの

$$\ket{\dot{\psi}(s)} \in H_{\ket{\psi(s)}}$$

を水平測地線という. 水平測地線は $\mathbb{C}^N$ のエルミート計量 $\langle \cdot | \cdot \rangle$ について直交するベクトル $\ket{\psi_1}, \ket{\psi_2} \in S^{2N-1}$ を一組とって以下のように表せる.

$$\Ket{\psi(s)} = \cos\left(\frac{s}{2}\right)\ket{\psi_1} + \sin\left(\frac{s}{2}\right)\ket{\psi_2}. \tag{12}$$

ベクトルの組 $\ket{\psi_1}, \ket{\psi_2} \in S^{2N-1}$ はリーマン計量 $\text{Re}\langle \cdot | \cdot \rangle$ について直交するだけでは $\Ket{\psi(s)}$ は測地線だが水平でなくなってしまう. エルミート計量 $\langle \cdot | \cdot \rangle$ について直交しなければならない.

前節で説明したように球面 $S^{2N-1}$ と複素射影空間 $\mathbb{C}P^{N-1}$ に Hopf fibration $f$ に適合したリーマン計量を入れると, $\mathbb{C}P^{N-1}$ の測地線は $S^{2N-1}$ のなんらかの水平測地線の射影 $f(\Ket{\psi(s)})$ として表せる^[6:1].

Grover iteration と測地線との関係

Grover iteration $G$ (式(5)) は $\{ \ket{r}, \ket{w} \}$ を正規直交基底とする実 $2$ 次元部分空間内の回転 $U_a(\theta)$ とみなすことができる (式(6)) ので, 初期状態 $\ket{a}$ の $k$ 回の Grover iteration による量子状態は

$$\ket{\psi(k)} := G^{k}\ket{a} = \cos\left( k + \frac{1}{2} \right)\theta \ket{r} + \sin\left( k + \frac{1}{2} \right)\theta \ket{w} \tag{13}$$

と計算される. 式 (12) で $\ket{\psi_1}=\ket{r}$, $\ket{\psi_2}=\ket{w}$, $s=2\left( k + \frac{1}{2} \right)\theta$ とすれば, $\ket{\psi(k)}$ はちょうど球面 $S^{2N-1}$ 上の $\ket{\psi_1}=\ket{r}$, $\ket{\psi_2}=\ket{w}$ によって定まる水平測地線上をたどっていることがわかる. つまり Grover アルゴリズムの繰り返し計算による量子状態の時間発展は $\mathbb{C}P^{N-1}$ 上を Fubini-Study 計量について局所的に最短の曲線を描いている.

分離可能状態と Segre embedding

本節では論文^[2:6]に従い, Segre embedding を使った entanglement の扱い方を紹介する. まず, $2$ 量子ビットの場合に次の Segre embedding $\sigma_{1,1}$ を考える.

$$\begin{aligned} \sigma_{1,1} : \mathbb{C}P^1 \times \mathbb{C}P^1 &\longrightarrow \mathbb{C}P^3, \\ \sigma_{1,1}: ([a_0:a_1], [b_0:b_1]) &\longmapsto [a_{0}b_{0}:a_{0}b_{1}:a_{1}b_{0}:a_{1}b_{1}]. \end{aligned}$$

定義式に斉次座標を使ったが, この定義は斉次座標のとり方によらずにうまく定義されている ($[a_0:a_1]$ や $[b_0:b_1]$ をそれぞれゼロでない複素数スカラー倍しても $\sigma_{1,1}$ の行き先は変わらない).

$\mathbb{C}P^1 \times \mathbb{C}P^1$ は $1$ 量子ビットを独立に $2$ つ並べただけである. $\mathbb{C}P^3$ は $2$ 量子ビットの一般の状態を表すことのできる空間である. Segre embedding $\sigma_{1,1}$ は $1$ 量子ビットの $2$ つの状態のテンソル積の成分を斉次座標として並べたものである.

$$\begin{pmatrix} a_0 \\ a_1 \end{pmatrix} \otimes \begin{pmatrix} b_0 \\ b_1 \end{pmatrix} = \begin{pmatrix} a_{0}\,b_{0} \\ a_{0}\,b_{1} \\ a_{1}\,b_{0} \\ a_{1}\,b_{1} \end{pmatrix}.$$

Segre embedding $\sigma_{1,1}$ は $1$ 量子ビットの独立な $2$ つの状態を $2$ 量子ビットの分離可能状態として埋め込む写像である.

$\mathbb{C}P^3$ の斉次座標を $[z_0:z_1:z_2:z_3]$ とすると, Segre embedding $\sigma_{1,1}$ の像は $2$ 次多項式

$$Q(z_0, z_1, z_2, z_3) := z_{0}z_{3} - z_{1}z_{2}$$

によって定義される二次曲面 (quadric) となる.

$$\sigma_{1,1}(\mathbb{C}P^1 \times \mathbb{C}P^1) = \{ [z_0:z_1:z_2:z_3] \in \mathbb{C}P^3 \:|\: Q(z_0, z_1, z_2, z_3)=0 \}.$$

次に一般の $\mathbb{C}P^m$ と $\mathbb{C}P^{m^{\prime}}$ の Segre embedding $\sigma_{m, m^{\prime}}$ を考える.

$$\begin{aligned} \sigma_{m, m^{\prime}} : \mathbb{C}P^m \times \mathbb{C}P^{m^{\prime}} &\longrightarrow \mathbb{C}P^{(m+1)(m^{\prime}+1)-1}, \\ \sigma_{m, m^{\prime}}: ([a_0:\dots :a_m], [b_0:\dots :b_m]) &\longmapsto [a_{0}b_{0}:\dots :a_{0}b_{m^{\prime}}:\dots :a_{m}b_{0}:\dots :a_{m}b_{m^{\prime}}]. \end{aligned}$$

この定義も $2$ 量子ビットの Segre embedding のときと同様に独立に $\mathbb{C}P^m$ の量子状態と $\mathbb{C}P^{m^{\prime}}$ の量子状態の $2$ つの状態を分離可能状態として埋め込む写像である. $\sigma_{m, m^{\prime}}$ に対応する $2$ 次多項式は $0\leq i \leq j \leq m$, $0\leq k \leq l \leq m^{\prime}$ を満たす整数 $i$, $j$, $k$, $l$ に対して,

$$Q_{(i,j),(k,l)} := z_{(m^{\prime}+1)i+k}z_{(m^{\prime}+1)j+l} - z_{(m^{\prime}+1)i+l}z_{(m^{\prime}+1)j+k} \tag{14}$$

と与えられる. $0\leq i \leq j \leq m$, $0\leq k \leq l \leq m^{\prime}$ を満たす全ての整数 $i$, $j$, $k$, $l$ に対して $Q_{(i,j),(k,l)}=0$ を満たす $\mathbb{C}P^{(m+1)(m^{\prime}+1)-1}$ の点集合が $\sigma_{m, m^{\prime}}$ の像である.

Grover iteration での entanglement の計算

論文^[2:7]の entanglement の定義と Grover アルゴリズムの繰り返し計算による量子状態の軌道上での entanglement の計算結果を述べる.

Grover iteration での量子状態が分離可能状態であるための条件

$\mathbb{C}P^{N-1}$ ($N=2^n$) の $k$ 回目の Grover iteration による量子状態 $\ket{\psi(k)}$ は, 式 (13) を斉次座標 $[z_0:\dots :z_{N-1}]$ で書くことによって,

$$z_{j \neq w} = \frac{\cos(k+\frac{1}{2})\theta}{\sqrt{N-1}},\; z_{w} = \sin(k+\frac{1}{2})\theta \tag{15}$$

と表せる. $w$ 番目の量子ビットと他の量子ビットの成分が分離できる ($\ket{\psi(k)} \in \sigma_{m,m^{\prime}}(\mathbb{C}P^{2^{n-1}-1}\times\mathbb{C}P^{1})$) ための条件は, 式 (14) で $m=2^{n-1}-1$, $m^{\prime}=1$ とした式を適用して,

$$\frac{\cos(k+\frac{1}{2})\theta \, \sin(k+\frac{1}{2})\theta}{\sqrt{N-1}} - \frac{\cos^2(k+\frac{1}{2})\theta}{N-1} = 0 \tag{16}$$

となる. この条件から以下の $2$ 通りの場合が考えられる.

1. $\cos(k+\frac{1}{2})\theta \neq 0$.
   この場合は式 (16) は $\tan(k+\frac{1}{2})\theta = 1/(\sqrt{N-1}) = \tan(\theta/2)$ となるので, $(k+1/2)\theta = \theta/2$ or $\theta/2+\pi$ (mod $2\pi$).
2. $\cos(k+\frac{1}{2})\theta = 0$.
   この場合は式 (16) は $(k+1/2)\theta = \pi/2$ or $3\pi/2$ (mod $2\pi$).

この条件 1, 2 は $\ket{\psi(k)}$ が完全に分離可能である ($(\mathbb{C}P^1)^n$) ための十分条件にもなっている. 以上より, Grover アルゴリズムの計算で分離可能状態となっているのは $\ket{a}$, $\ket{w}$ だけで, Grover アルゴリズムの繰り返し計算の途中の量子状態はいずれも entangled の状態にあることがわかった.

entanglement の量 (強さ)

$\mathbb{C}P^{N-1}$ の量子状態は, 完全に分離可能である状態の集合 $(\mathbb{C}P^1)^n$ から離れているほど entanglement が強いと考えられるため, $\ket{\psi} \in \mathbb{C}P^{N-1}$ の entanglement の量 $E(\ket{\psi})$ を $(\mathbb{C}P^1)^n$ の元 $\ket{\varphi}$ の中で $\ket{\psi}$ までの距離が最も短いものの値と定義する.

$$E(\ket{\psi}) := \min_{\ket{\varphi} \in (\mathbb{C}P^1)^n} s(\ket{\psi}, \ket{\varphi}).$$

$s$ は $\mathbb{C}P^{N-1}$ の Fubini-Study 計量についての距離関数であるが, 論文^[2:8]での Fubini-Study 計量は本記事の $2$ 倍として定義されている. entanglement についての議論の詳細は論文^[2:9]を参照.

$2$ 量子ビットでの計算

$\mathbb{C}P^{3}$ ($N=2^2$) の最後の成分が探索対象の番号 $w=3$ であるとする. $k$ 回目の Grover iteration による量子状態 $\ket{\psi(k)}$ は, 式 (15) から斉次座標で以下のように表される.

$$\left[\frac{\cos(k+\frac{1}{2})\theta}{\sqrt{3}}: \frac{\cos(k+\frac{1}{2})\theta}{\sqrt{3}}: \frac{\cos(k+\frac{1}{2})\theta}{\sqrt{3}}: \sin(k+\frac{1}{2})\theta \right].$$

これを最後の成分についての非斉次座標で表示し直すと ($\cot=\cos / \sin$),

$$\left(\frac{\cot(k+\frac{1}{2})\theta}{\sqrt{3}},\, \frac{\cot(k+\frac{1}{2})\theta}{\sqrt{3}},\, \frac{\cot(k+\frac{1}{2})\theta}{\sqrt{3}} \right).$$

論文^[2:10]より

$$\begin{aligned} u &:=\frac{\cot\left(k+\frac{1}{2}\right)\theta}{\sqrt{3}}, \\ v_{M} &:= \frac{u-1+\sqrt{(u-1)^2 + 4u^2}}{2u}, \end{aligned}$$

とおいて, 以下が得られる.

$$E(\ket{\psi(k)}) = 2\arccos \sqrt{\frac{u^2}{3u^2+1}\left( \frac{v_{M}+1}{v_{M}} \right)^2}.$$

$t=(k+\frac{1}{2})\theta$ を連続的に動かすと $E(\ket{\psi(k)})$ の値は最大でも $0.34$ ほどの値にしかならない. $E$ がとりうる最大値は $\pi/2$ なので, entanglement はあまり大きくない.

一般の $n$ 量子ビットでの近似計算

$2$ 量子ビットでの計算と同様, 簡単のため, $\mathbb{C}P^{N-1}$ の最後の成分が探索対象の番号 $w$ であるとし, $k$ 回目の Grover iteration による量子状態 $\ket{\psi(k)}$ の非斉次座標成分を $u$ とおく.

$$u :=\frac{\cot\left(k+\frac{1}{2}\right)\theta}{\sqrt{N-1}}.$$

一般の $n$ 量子ビットでの $E(\ket{\psi(k)})$ の直接計算はかなり厳しく, 論文^[2:11]では以下の近似式が計算されている.

$$E(\ket{\psi(k)}) \sim 2\arccos \sqrt{\frac{[u(r_{M}+1)^n + 1 -u]^2}{[(N-1)u^2 +1](r_{M}^2 +1)^n}}.$$

$r_{M}:= u/(1-(n-1)u)$ としている. 右辺を $t=(k+\frac{1}{2})\theta$ についての関数として表示すると以下のことがわかる^[2:12].

1. $n$ が大きいほど entanglement $E(\ket{\psi(k)})$ の値が大きくなり, 最大限に使われるようになる.
2. entanglement が最も小さくなるのは初期状態 $\ket{a}$ と探索対象の状態 $\ket{w}$.

一般化された Grover アルゴリズムと計算時間評価

任意の量子状態を初期状態とする Grover アルゴリズム

Grover iteration の定義式 (式 (5))

$$G := I_{a} \circ I_{r}$$

は初期量子状態が $\ket{a}$ でなければ意味を持たないが, 鏡映変換の部分をこれから説明するよう変更すれば, 任意の量子状態 $\ket{y}$ からターゲットとなる量子状態 $\ket{w}$ を得るアルゴリズムとなる. 初期量子状態が $\ket{a}$ であれば, Grover iteration は $\{ \ket{r}, \ket{w} \}$ を正規直交基底とする実 $2$ 次元部分空間内の回転 $U_a(\theta)$ とみなすことができるが, 任意の量子状態 $\ket{y}$ をとると, この実 $2$ 次元部分空間からはずれてしまう. そこで論文^[2:13]に従って, Grover iteration を以下のように計算する (論文^[2:14]では鏡映変換の定義が異なるが, $-1$ 倍の違いなので, $I_{a} \circ I_{w}$ の結果は同じである).

$$G = - I_{a} \circ I_{w}.$$

この定義をまねて, 任意の量子状態 $\ket{y}$ に対しても Grover iteration を定義できる.

$$G := - I_{y} \circ I_{w}.$$

任意の量子状態 $\ket{y}$ としたが, Grover アルゴリズムでターゲットとなる量子状態 $\ket{w}$ を得るためには以下の条件を満たさなければならない.

1. エルミート内積 $\langle w | y \rangle$ が実数である.
2. $\langle w | y \rangle > 0.$

条件 1, 2 を満たす状態 $\ket{w}$, $\ket{y}$ を in phase あるいは parallel という^[7:1].

条件 1 はどんな $\ket{y}$ でも phase を選び直せば満たされる. もし正の実数 $r, \varphi$ に対して,

$$\langle w | y \rangle = r e^{i\varphi}$$

であれば, $\ket{y}$ のかわりに $e^{i\varphi}\ket{y}$ をとればよい ($\mathbb{C}P^{N-1}$ の元としては同じ). 条件 2 も $\langle w | y \rangle \neq 0$ であれば同様に $\ket{y}$ の phase の選び直しで満たされるようにできる. また, $\ket{w}$ も $\ket{y}$ も $S^{2N-1}$ 上の点なので, $\langle w | y \rangle =1$ となると $\ket{w}=\ket{y}$ となってしまい, 探索の意味がなくなる.

$\ket{w}$, $\ket{y}$ が in phase であるとき, $q:=\langle w|y \rangle$ と置いて,

$$\ket{r^{\prime}} := \frac{\ket{y} -q\ket{w}}{\sqrt{1-q^2}} \tag{17}$$

とすると, $\ket{y}$ は $\{ \ket{r^{\prime}}, \ket{w} \}$ を正規直交基底とする実 $2$ 次元部分空間に含まれる. さらに $\sin(\eta/2):=q$ とおくと, この部分空間と正規直交基底での Grover iteration $G= - I_{y} \circ I_{w} = I_{y} \circ I_{r^{\prime}}$ の表現行列は $\ket{a}$ を初期状態としたときと同様に,

$$U_y(\eta) = \begin{pmatrix} \cos\eta & -\sin\eta \\ \sin\eta & \cos\eta \end{pmatrix} \tag{18}$$

となる. 初期状態 $\ket{y}$ の $k$ 回の Grover iteration による量子状態は

$$\ket{\psi(k)} := G^{k}\ket{y} = \cos\left( k + \frac{1}{2} \right)\eta \ket{r^{\prime}} + \sin\left( k + \frac{1}{2} \right)\eta \ket{w} \tag{19}$$

と計算され, その軌道は正規直交基底 $\{ \ket{r^{\prime}}, \ket{w} \}$ が定義する $S^{2N-1}$ の水平測地線上にある.

$\mathbb{C}P^{N-1}$ 上の量子状態の間の距離

上記の $\ket{y}$, $\ket{w}$ が in phase であり, これらを結ぶ $S^{2N-1}$ の水平測地線 $\tilde{c}$ の Hopf fbration による射影 $f\circ \tilde{c}$ が $f(\ket{y})$, $f(\ket{w})$ を結ぶ $\mathbb{C}P^{N-1}$ 上の最短線であるとする. $S^{2N-1}$ 上の $\text{Re}\langle \cdot | \cdot \rangle$ についての距離を $d$ とし, $\mathbb{C}P^{N-1}$ 上の Fubini-Study 計量についての距離を $s$ とすると, $d(\ket{y}, \ket{w})$ は $\ket{y}$ から $\ket{w}$ までの水平測地線 $\tilde{c}$ (大円) の弧長となっているので,

$$\cos(s(f(\ket{y}), f(\ket{w}))) = \cos(d(\ket{y}, \ket{w})) = \text{Re}\langle y | w \rangle = \langle y | w \rangle. \tag{20}$$

である^[7:2].

$S^{2N-1}$ の水平測地線は全体では $S^{2N-1}$ 上の閉曲線で, 長さは $2\pi$ であるが, これを Hopf fibration $f$ によって $\mathbb{C}P^{N-1}$ 上の測地線に写すと, 水平測地線は Hopf fibration によって半分つぶれて, 長さが $\pi$ となる.

計算時間の評価

Grover iteration $1$ 回あたりのスピード $V(k)$ は量子状態 $\ket{\psi(k+1)}$, $\ket{\psi(k)}$ の間の $\mathbb{C}P^{N-1}$ 上の距離と考えられるので, 式 (18), (19), (20) と $q=\sin(\eta/2)=\langle w|y \rangle$ と論文^[2:15]では Fubini-Study 計量が本記事の $2$ 倍であることより,

$$\begin{aligned} V(k) &= s(f(\ket{\psi(k+1)}), f(\ket{\psi(k)})) \\ &= 2\arccos\langle \psi(k+1) | \psi(k) \rangle = 2\eta = 4\arcsin q. \tag{21} \end{aligned}$$

式 (17) で定義された状態 $\ket{r^{\prime}}$ から $\ket{w}$ までの距離は論文^[2:16]の Fubini-Study 計量で $\pi$ なので,

$$s(\ket{y}, \ket{w}) = \pi - \eta = \pi - 2\arcsin q.$$

これを使って $\ket{y}$ から $\ket{w}$ に達するまでに Grover アルゴリズムにかかる時間は,

$$T_{w} := \frac{s(\ket{y}, \ket{w})}{V} = \frac{\pi - \eta}{2\eta} = \frac{\pi - 2\arcsin q}{4\arcsin q}. \tag{22}$$

$V(k)$ は式 (21) から $k$ によらないので定数 $V$ とした.

式 (22) で距離をスピードで割っているので, Fubini-Study 計量の定義の $2$ 倍の違いは相殺される.

$\ket{y}$ を計算基底で表し, 正規化する.

$$\begin{aligned} &\ket{y} = \sum_{x=0}^{N-1}z_x \ket{x}, \\ &\sum_{x=0}^{N-1} |z_x|^2 = 1,\; z_0, \dots, z_{N-1} \in \mathbb{C}. \end{aligned}$$

量子探索を行う上で探索対象の番号 $w$ が不明である状況を考えると, $\ket{y}$ と $\ket{w}$ との位置関係は最悪な場合 ($q=\langle w|y \rangle$ が小さくなってしまい, $T_{w}$ が大きくなってしまう場合) を想定する必要がある. $w$ がどの $x$ であったとしてもできるだけ $q=\langle w|y \rangle$ を大きくするためには, すべての係数が等しい場合 $z_0 = \dots = z_{N-1} = 1/\sqrt{N}$ すなわち $\ket{y}=\ket{a}$ が最も適している. このとき $q=\langle w|a \rangle = 1/\sqrt{N}$ なので,

$$T_{w} = \frac{\pi - 2\arcsin(1/\sqrt{N})}{4\arcsin(1/\sqrt{N})}$$

である. $N$ が大きな数であるとき, $\arcsin(1/\sqrt{N}) \sim 1/\sqrt{N}$ であるから,

$$T_{w} \sim \frac{\pi}{4}\sqrt{N}$$

と評価できる.

まとめ

Hopf fibration の微分幾何を使って Grover アルゴリズムについて以下のことを調べた研究の紹介を行った.

1. 量子ビット数 $n$ が大きいほど entanglement $E(\ket{\psi(k)})$ の値が大きくなり, 最大限に使われるようになる.
2. Grover アルゴリズムの計算時間に本質的に関係するのはターゲットの量子状態と初期量子状態との内積の値であり, entanglement との関係は不明.

脚注

1. Quantum Computation and Quantum Information: 10th Anniversary Edition, Michael A. Nielsen & Isaac L. Chuang.

2. A. Miyake and M. Wadati, Geometric strategy for the optimal quantum search, Phys. Rev. A64, 042317 (2001).

3. 多様体, 測地線, 主束の接続については用語を検索すると解説記事や大学のレクチャーノートがヒットする. またこちらの教科書は説明が丁寧なのでおすすめである.

4. 本記事ではエルミート計量にブラケット記法^[5:2]を使う.

5. 量子論の基礎―その本質のやさしい理解のために（新版）清水 明【著】.

6. R. Montgomery, A tour of subriemannian geometries, their geodesics and applications, vol. 91 of Mathematical Surveys and Monographs (American Mathematical Society, Providence, Rhode Island, 2002).

7. Chruscinski, D. & Jamiolkowski, A. Geometric Phases in Classical and Quantum Mechanics. (Birkhäuser:, 2004).