位相推定問題

このレッスンのセクションでは、位相推定問題について説明します。 まず線形代数のスペクトル定理について簡単に説明し、その後、位相推定問題そのものの定式化に進みます。

スペクトル定理

スペクトル定理は線形代数における重要な定理であり、正規行列と呼ばれる特定の種類の行列が、シンプルかつ有用な形で表現できることを述べています。 このレッスンでは、ユニタリ行列に対してのみこの定理を使用しますが、シリーズのこの後の部分ではエルミート行列にも適用します。

正規行列

複素数を成分とする正方行列 $M$ は、その共役転置と可換である場合、すなわち $M M^{\dagger} = M^{\dagger} M$ が成り立つ場合に正規行列と呼ばれます。

すべてのユニタリ行列 $U$ は正規行列です。なぜなら

$$U U^{\dagger} = \mathbb{I} = U^{\dagger} U$$

が成り立つからです。

エルミート行列（自分自身の共役転置と等しい行列）は、正規行列の別の重要なクラスです。 $H$ がエルミート行列であれば、

$$H H^{\dagger} = H^2 = H^{\dagger} H,$$

が成り立つので、$H$ は正規行列です。

すべての正方行列が正規行列であるわけではありません。 例えば、次の行列は正規行列ではありません：

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$$

（これはしばしば考察に大変役立つ、シンプルながら優れた行列の例です。） これが正規行列でない理由は、

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}$$

であるのに対し、

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix}.$$

となり、両者が等しくないからです。

定理の主張

以下にスペクトル定理の主張を示します。

定理

スペクトル定理：$M$ を正規な $N\times N$ 複素行列とします。 $N$ 次元複素ベクトルの正規直交基底 $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ と複素数 $\lambda_1,\ldots,\lambda_N$ が存在して、

$$M = \lambda_1 \vert \psi_1\rangle\langle \psi_1\vert + \cdots + \lambda_N \vert \psi_N\rangle\langle \psi_N\vert.$$

が成り立ちます。

行列を

$$M = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert \tag{1}$$

の形で表現することは、一般にスペクトル分解と呼ばれます。 正規行列 $M$ が $(1)$ の形で表されているとき、すべての $j = 1,\ldots,N$ に対して

$$M \vert \psi_j \rangle = \lambda_j \vert \psi_j \rangle$$

が成り立たなければならないことに注目してください。 これは $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ が正規直交系であるという事実から導かれます：

$$M \vert \psi_j \rangle = \left(\sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\right)\vert \psi_j\rangle = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\psi_j \rangle = \lambda_j \vert\psi_j \rangle$$

つまり、各数 $\lambda_j$ は $M$ の固有値であり、$\vert\psi_j\rangle$ はその固有値に対応する固有ベクトルです。

• 例1。 次を考えます。

  $$\mathbb{I} = \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix},$$

  これは正規行列です。 定理より、$\mathbb{I}$ はある $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ $\vert\psi_2\rangle$ の選択のもとで $(1)$ の形に書けます。 有効な選択肢は複数あり、その一つは

  $$\lambda_1 = 1, \hspace{5pt} \lambda_2 = 1, \hspace{5pt} \vert\psi_1\rangle = \vert 0\rangle, \hspace{5pt} \vert\psi_2\rangle = \vert 1\rangle$$

  です。

  定理は複素数 $\lambda_1,\ldots,\lambda_N$ が互いに異なることを要求していないことに注意してください。同じ複素数が繰り返し現れることが可能であり、この例ではそれが必要です。 これらの選択が有効である理由は、

  $$\mathbb{I} = \vert 0\rangle\langle 0\vert + \vert 1\rangle\langle 1\vert$$

  が成り立つからです。

  実際、$\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ を任意の正規直交基底として選んでも等式は成立します。例えば、

  $$\mathbb{I} = \vert +\rangle\langle +\vert + \vert -\rangle\langle -\vert.$$

• 例2。 アダマール演算を考えます。

  $$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$

  これはユニタリ行列なので正規行列です。スペクトル定理より $H$ は $(1)$ の形に書けます。特に、

  $$H = \vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert$$

  が成り立ちます。ここで、

  $$\vert\psi_{\theta}\rangle = \cos(\theta)\vert 0\rangle + \sin(\theta) \vert 1\rangle$$

  です。

  より明示的に書くと、

  $$\begin{aligned} \vert\psi_{\pi/8}\rangle & = \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 - \sqrt{2}}}{2}\vert 1\rangle, \\[3mm] \vert\psi_{5\pi/8}\rangle & = -\frac{\sqrt{2 - \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 1\rangle \end{aligned}$$

  となります。

  この分解が正しいことは、必要な計算を実行することで確認できます：

  $$\vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert = \begin{pmatrix} \frac{2 + \sqrt{2}}{4} & \frac{\sqrt{2}}{4}\\[2mm] \frac{\sqrt{2}}{4} & \frac{2 - \sqrt{2}}{4} \end{pmatrix} - \begin{pmatrix} \frac{2 - \sqrt{2}}{4} & -\frac{\sqrt{2}}{4}\\[2mm] -\frac{\sqrt{2}}{4} & \frac{2 + \sqrt{2}}{4} \end{pmatrix} = H.$$

上記の最初の例が示すように、固有ベクトルの選び方には自由度があり得ます。 しかし、固有値の選び方には、その順序付けを除いて自由度は全くありません：行列 $M$ の選択が決まれば、同じ複素数の繰り返しを含む $N$ 個の複素数 $\lambda_1,\ldots,\lambda_N$ は、式 $(1)$ において常に同じものが現れます。

次に、ユニタリ行列に焦点を当てましょう。 複素数 $\lambda$ と非ゼロベクトル $\vert\psi\rangle$ が

$$U\vert\psi\rangle = \lambda\vert\psi\rangle \tag{2}$$

を満たすとします。

つまり、$\lambda$ は $U$ の固有値であり、$\vert\psi\rangle$ はこの固有値に対応する固有ベクトルです。

ユニタリ行列はユークリッドノルムを保存するので、$(2)$ から次のことが導かれます。

$$\bigl\| \vert\psi\rangle \bigr\| = \bigl\| U \vert\psi\rangle \bigr\| = \bigl\| \lambda \vert\psi\rangle \bigr\| = \vert \lambda \vert \bigl\| \vert\psi\rangle \bigr\|$$

$\vert\psi\rangle$ が非ゼロであるという条件から $\bigl\| \vert\psi\rangle \bigr\|\neq 0$ が導かれるので、両辺を割ると

$$\vert \lambda \vert = 1$$

が得られます。

これにより、ユニタリ行列の固有値は絶対値が必ず1でなければならないことがわかります。つまり、固有値は単位円上に存在します。

$$\mathbb{T} = \{\alpha\in\mathbb{C} : \vert\alpha\vert = 1\}$$

（記号 $\mathbb{T}$ は複素単位円の一般的な名称です。$S^1$ という名称もよく使われます。）

位相推定問題の定式化

位相推定問題では、$n$ 量子ビットの量子状態 $\vert \psi\rangle$ と、$n$ 量子ビットに作用するユニタリ量子回路が与えられます。 その回路の作用を記述するユニタリ行列 $U$ の固有ベクトルが $\vert \psi\rangle$ であることが保証されており、目標は $\vert \psi\rangle$ に対応する固有値 $\lambda$ を計算または近似することです。 より正確には、$\lambda$ は複素単位円上に存在するので、

$$\lambda = e^{2\pi i \theta}$$

と書けます。ここで、$0\leq\theta<1$ を満たす一意の実数 $\theta$ です。 この問題の目標は、この実数 $\theta$ を計算または近似することです。

位相推定問題

入力：$n$ 量子ビット演算 $U$ のユニタリ量子回路と $n$ 量子ビット量子状態 $\vert\psi\rangle$
保証：$\vert\psi\rangle$ は $U$ の固有ベクトルである
出力：$U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$ を満たす $\theta\in[0,1)$ の近似値

この問題の定式化について、いくつかの注意点を述べます：

1. 位相推定問題は、入力に量子状態が含まれるという点で、コースでこれまでに見てきた他の問題とは異なります。通常は古典的な入力と出力を持つ問題に焦点を当てますが、このような量子状態の入力を考えることを妨げるものは何もありません。実際的な関連性という観点では、位相推定問題は通常、このレッスンの後半で整数の素因数分解の文脈で見るように、より大きな計算の中の部分問題として遭遇します。

2. 上記の位相推定問題の定式化では、$\theta$ の近似がどのようなものであるかについて具体的ではありませんが、必要に応じてより精密な問題の定式化を行うことができます。整数の素因数分解の文脈では $\theta$ に対して非常に精密な近似を要求しますが、他の場合には非常に粗い近似で十分なこともあります。要求する精度が解の計算コストにどのような影響を与えるかについては、後ほど説明します。

3. 位相推定問題において $\theta = 0$ から $\theta = 1$ に向かうにつれ、単位円を一周することになります。$e^{2\pi i \cdot 0} = 1$ から始まり、反時計回りに $e^{2\pi i \cdot 1} = 1$ に向かいます。つまり、$\theta = 1$ に達すると $\theta = 0$ の出発点に戻ります。したがって、近似の精度を考える際には、$1$ に近い $\theta$ の値は $0$ に近いものとして扱われるべきです。例えば、$\theta = 0.999$ という近似は、$\theta = 0$ から $1/1000$ 以内にあると考えるべきです。