$A$ はエルミート行列としたので、$U = e^{itA}$ はユニタリ行列である。ここで、$t$ の存在が気になるというか、$t=1$ にして良いんじゃ？と思える。原論文 [0811.3171] Quantum algorithm for solving linear systems of equations を見ると、ハミルトニアンによる時間発展を考えているから出てきているようにも見えるが、細かい見積もりをしないなら $t$ は定数にして考えたほうが混乱しなくて済みそうだ。書籍も textbook も書いているので一応は飾りとして見ておくことにする・・・。*1
・・・深くは追求しないことにして、$A$ の固有ベクトル $\ket{a_j}$ について、
$$
\begin{align*}
e^{itA} \ket{a_j} &= \sum_{k=0}^\infty \frac{1}{k!} (it)^k A^k \ket{a_j} \\
&= \sum_{k=0}^\infty \frac{1}{k!} (it)^k \lambda_j^k \ket{a_j} = e^{it\lambda_j} \ket{a_j}
\end{align*}
$$
より、$e^{itA}$ は固有値 $e^{it\lambda_j},\ j = 0, \cdots, n-1$ と固有ベクトル $\ket{a_j},\ j = 0, \cdots, n-1$ を持つ。
量子位相推定
量子位相推定を思い出すと、$U$ とその固有ベクトル $\ket{a_j}$ を 1 つとる時、2 つのレジスタは $\ket{0}^{\otimes n} \otimes \ket{a_j}$ で初期化するところから始まる。
- まず、アダマールゲート $H_1^{\otimes n}$ を第 1 レジスタに作用させて $\frac{1}{\sqrt{2^n}} (\ket{0} + \ket{1})^{\otimes n} \ket{a_j}$ を作るのであった。
- 次に、第 1 レジスタの第 $k$ 量子ビットを制御ビットとする $U$ を $2^{n-k}$ 回ずつ作用させるのであった。
- まずは第 1 量子ビットを考えると（第 2 ビット以降を $\ket{*} = (\ket{0} + \ket{1})^{\otimes n-1}$ としておく）:
$$
\begin{align*}
CU^{n-1} \frac{1}{\sqrt{2^n}}(\ket{0}\ket{*}\ket{a_j} + \ket{1}\ket{*}\ket{a_j}) &= \frac{1}{\sqrt{2^n}}(\ket{0}\ket{*}\ket{a_j} + \ket{1}\ket{*} U^{n-1} \ket{a_j}) \\
&= \frac{1}{\sqrt{2^n}}(\ket{0}\ket{*}\ket{a_j} + e^{i (n-1) t \lambda_j}\ket{1}\ket{*}\ket{a_j}) \\
& = \frac{1}{\sqrt{2^n}}(\ket{0} + e^{i (n-1) t \lambda_j}\ket{1})\ket{*}\ket{a_j}
\end{align*}
$$
$$
\begin{align*}
&\frac{1}{\sqrt{2^n}}(\ket{0} + e^{i (n-1) t \lambda_j}\ket{1})(\ket{0} + e^{i (n-2) t \lambda_j}\ket{1})\cdots(\ket{0} + e^{i t \lambda_j}\ket{1})(\ket{0} + \ket{1})\ket{a_j} \\
=&\ \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} e^{ikt \lambda_j} \ket{k} \otimes \ket{a_j}
\end{align*}
$$
- 最後に 1 レジスタに逆量子 Fourier 変換を適用すると:
$$
\begin{align*}
\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} e^{ikt \lambda_j} \left[ \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1}e^{-2 \pi i \frac{kx}{2^n}} \ket{x} \right] \otimes \ket{a_j} &= \frac{1}{2^n}\sum_{k=0}^{2^n-1} \sum_{x=0}^{2^n-1} e^{-2 \pi i \frac{k}{2^n} (x - 2^n \frac{t \lambda_j}{2\pi})} \ket{x} \otimes \ket{a_j} \\
&= \frac{1}{2^n}\sum_{k=0}^{2^n-1} \sum_{x=0}^{2^n-1} e^{-2 \pi i \frac{k}{2^n} (x - 2^n \lambda_j^\prime)} \ket{x} \otimes \ket{a_j}
\end{align*}
$$
ここで、$\lambda_j^\prime = \frac{t \lambda_j}{2\pi}$ である。$e^{i t \lambda_j} = e^{2 \pi i \lambda_j^\prime}$ であるので、$\lambda_j^\prime$ はユニタリ演算子 $e^{i t A}$ の固有値の位相に相当する。これで Qiskit (32) - らんだむな記憶 の (3) 式の形になった。
ここで簡単のため、$2^n \lambda_j^\prime \in \Z,\ 0 \leq 2^n \lambda_j^\prime \leq 2^n - 1$ が成立しているとすると第 1 レジスタの測定で、$2^n \lambda_j^\prime$ が確率 1 で観測できるので、式は (4) 式と同様に更に簡単にできる。すべての $j$ についてこの都合の良い状況が成立しているとすると、最後の式は $x \neq \lambda_j^\prime$ の時に消えて、
$$
\begin{align*}
|\lambda_j^\prime \rangle \otimes \ket{a_j}
\end{align*}
$$
だけが残る。ここで $|\lambda_j^\prime \rangle$ の意味について明確化する: 例えば、$n = 3$ であり、$2^3 \lambda_j^\prime = 4$ であったとする。この時、第 1 レジスタの測定で $\ket{100}$ が確率 1 で観測されることになる。この $\ket{100}$ を $|\lambda_j^\prime \rangle$ と書くことにするというものである。つまり、$2^n \lambda_j^\prime$ の $n$-bit バイナリ表現を ket の中に入れている。他の箇所との整合性を考えると、$| 2^n \lambda_j^\prime \rangle$ と書きたいところかもしれない。textbook では Solving Linear Systems of Equations using HHL で、
Where $\bar{\lambda}_j$ represents an $n_l$-bit binary approximation to $2^{n_l} \frac{\lambda_j t}{2 \pi}$.
とされている部分が該当する。（上のほうでは $\lambda_j$ の近似と書いてあるがこちらは間違いであろう）
よって、ここまでをまとめると、$\ket{0}^{\otimes n} \otimes \ket{a_j} \xrightarrow{QPE} |\lambda_j^\prime \rangle \otimes \ket{a_j}$ である。
—————
$\ket{a_j}$ ごとでの量子位相推定の結果が分かったので、全体の話に戻る。Qiskit (38) ― HHL アルゴリズム - らんだむな記憶 より、$\ket{b} = \sum_{j=0}^{n-1} \beta_j \ket{a_j}$ であったので、
$$
\begin{align*}
\ket{0}^{\otimes n} \otimes \ket{b} &= \ket{0}^{\otimes n} \otimes \left( \sum_{j=0}^{n-1} \beta_j \ket{a_j} \right) \\
&= \sum_{j=0}^{n-1} \beta_j \ket{0}^{\otimes n} \otimes \ket{a_j} \xrightarrow{QPE} \sum_{j=0}^{n-1} \beta_j |\lambda_j^\prime \rangle \otimes \ket{a_j}
\end{align*}
$$
を得る。この辺は書籍の式が何箇所か間違っているように感じるので、Solving Linear Systems of Equations using HHL を参考にした。また、「すべての $j$ についてこの都合の良い状況が成立している」としたが、それが成立しない場合についても textbook では扱っている。多少話がややこしくなるように見えるので、ここでは気にせず書籍で扱っている都合の良い場合の話だけに限定して先へ進む。
*1:と思ったが、シミュレーションをする時などに、適当に具体的な値を与えて計算を簡単にするために利用していたりするようだ・・・
