プログラマのための量子アルゴリズム入門　付録. 数学に関する補足


この文章は「[プログラマのための量子アルゴリズム入門](https://note.mu/snuffkin/n/n8affc7eabf45)」の一部です。
全体の目次・記載方針を確認する場合は、次の画像をクリックしてください。

[![title.png](https://qiita-image-store.s3.amazonaws.com/0/13107/1d34511a-d79b-7dac-8ed8-4f315f4d1771.png)](https://note.mu/snuffkin/n/n8affc7eabf45)


# **今回の内容**
量子アルゴリズムを説明する際に必要な数学の記法と性質について簡単に説明します。
盛り込み過ぎず、必要な話題に絞って説明したいと思います。
(と言っても、ブラケット、ユニタリ行列、テンソル積あたりの説明は不足していると思うので、いずれ追記します)

知っていることは飛ばして構いませんし、知らないことも本文に登場した段階で読んで構いません。

# **集合**
## 集合とは
「ものの集まり」を**集合(set)**といいます。
これでは何を言っているか分かりませんが、ここでの目的は集合を厳密に定義することではないため、素朴な集合のイメージで話を進めます。

## 外延的記法と内包的記法
1, 3, 5, 7, 9という数の集まりを例に、集合の記法で表す方法を説明します。
大きく分けて2つの記法があり、そのときどきで使いやすいものを使います。

1つ目は**外延的記法**というもので、集合を構成しているものすべて並べることで表現します。

```math
\begin{align}
\{1, 2, 3, 4, 5\}
\end{align}
```

2つ目は**内包的記法**というもので、集合を構成しているものの性質を記載することで表現します。

```math
\begin{align}
& \{n  \mid nは1から5までの自然数\} \\
& \{n  \mid nは1 \le n \le 5を満たす自然数\}
\end{align}
```

内包的記法のカッコ内の書き方については説明が必要ですね。
カッコ内の「$\mid$」の左には集合を構成しているものの変数を書きます。
また、「$\mid$」の右には集合を構成しているものの性質を書きます。

## 要素
集合$\{1, 2, 3, 4, 5\}$を構成するひとつひとつのものを**要素**(element)といいます。 
「$1$が$\{1, 2, 3, 4, 5\}$の要素である」ということを

```math
\begin{align}
1 \in \{1, 2, 3, 4, 5\}
\end{align}
```
と書きます。「$6$は$\{1, 2, 3, 4, 5\}$の要素でない」ということは

```math
\begin{align}
6 \notin \{1, 2, 3, 4, 5\}
\end{align}
```
と書きます。
「$1と2$が$\{1, 2, 3, 4, 5\}$の要素である」というように複数の要素について書くときは、

$$
\begin{align}
1, 2 \in \{1, 2, 3, 4, 5\}
\end{align}
$$

というようにカンマ区切りで要素を並べます。 

集合$\{1, 2, 3\}$のすべての要素は、集合$\{1, 2, 3, 4, 5\}$の要素になっています。
これを「集合$\{1, 2, 3\}$は集合$\{1, 2, 3, 4, 5\}$に含まれる」といい、

```math
\begin{align}
\{1, 2, 3\} \subset \{1, 2, 3, 4, 5\}
\end{align}
```
と書きます。

## 定義式
数学の概念を定義するとき、便利な記法があります。
例えば「集合\{1, 2, 3, 4, 5\}を$A$と定義する」ことは次のように書きます。

```math
\begin{align}
A := \{1, 2, 3, 4, 5\}
\end{align}
```
これは、「$:=$」の右辺を使って左辺を定義する、ということを表します。

## よく使う集合の記号
次の集合は、プログラミング言語でいうビルトイン関数のようなもので、数学では特に説明なしに使われることも多いです。

```math
\begin{align}
\mathbb{N} & := 自然数全体の集合(1, 2, 3,...) \\
\mathbb{Z} & := 整数全体の集合(...,-3, -2, -1, 0, 1, 2, 3,...) \\
\mathbb{R} & := 実数全体の集合(1, \pi, \sqrt{2}など) \\
\mathbb{C} & := 複素数全体の集合(1, i, 1+\sqrt{2}iなど。後ほど詳しく説明します)
\end{align}
```

数学以外ではあまり見かけないかもしれない種類のボールドフォントです。  
また、各アルファベットの由来は次の通りです。 

- $\mathbb{N}$は自然数(natural number)の頭文字「n」に由来します。
- $\mathbb{Z}$は整数(integer)の頭文字「i」に由来する、、、訳ではなく、ドイツ語で「数」を意味する単語Zahlenに由来します。
- $\mathbb{R}$は実数数(real number)の頭文字「r」に由来します。
- $\mathbb{C}$は複素数(complex number)の頭文字「c」に由来します。

これらの集合には次のような包含関係があります。

```math
\begin{align}
\mathbb{N} \subset \mathbb{Z} \subset \mathbb{R} \subset \mathbb{C} 
\end{align}
```

この記号を使用し、集合$\{1, 2, 3, 4, 5\}$を次のような内包的記法で書くこともできます。

```math
\begin{align}
\{n\in\mathbb{N} \mid 1 \le n \le 5\}
\end{align}
```

## 積集合
複数の集合の組(tuple)を表す集合を**積集合**(product set)といいます。
2つの$\mathbb{R}$の組を表す集合は記号「$\times$」を使って

```math
\begin{align}
\mathbb{R}\times\mathbb{R}
\end{align}
```
と書きます。$\mathbb{R}$を2つ並べてものであるため、

```math
\begin{align}
\mathbb{R}^2
\end{align}
```
とも書きます。積集合の要素は

```math
\begin{align}
(1, 0)
\end{align}
```
のように、丸カッコ内にカンマ区切りで要素を並べて書きます。$(1, 0) \in \mathbb{R}\times\mathbb{R}$です。
コンピュータの世界では、ビットを0と1で表します。そのため、ビットの集合を

```math
\begin{align}
\{0, 1\}
\end{align}
```
と書きます。
また、$n$ビットは「$n$個のビットの組」です。そのため、積集合の記法を使うと $n$ ビットの情報の集合を

```math
\begin{align}
\{0, 1\}^n
\end{align}
```
と書くことができます。例えば、2ビットの情報の集合の要素を書き出すと

```math
\begin{align}
(0,0), (0,1), (1,0), (1,1) \in \{0, 1\}^2
\end{align}
```
となります。

# **複素数**
## 虚数単位と複素数の演算
実数を2乗すると0以上になるため、「2乗すると-1になる数」は実数の範囲には存在しません。
数の概念を実数から拡張し、「2乗すると-1になる数」を「$i$」と書き、**虚数単位**(imaginary unit)といいます。

```math
\begin{align}
i^2 = -1
\end{align}
```

「$i$」は添え字(index)を表す記号としても使われるため、文脈から区別する必要があります。
この文章では文脈上混同しやすい場合は、添え字に $i$ を使わないようにします。

2つの実数 $x, y$ と虚数単位 $i$ を使い、

```math
\begin{align}
x + yi
\end{align}
```

と表すことができる数を**複素数**(complex number)といいます。 
複素数全体の集合は、次のように書くこともできます。

```math
\begin{align}
\mathbb{C} = \{x + yi \mid x,y \in \mathbb{R} \}
\end{align}
```

2つの複素数

```math
\begin{align}
z_1=x_1+y_1i && (x_1,y_1は実数)\\
z_2=x_2+y_2i && (x_2,y_2は実数)
\end{align}
```
に対し、和と積を次のように定義します。

```math
\begin{align}
z_1 + z_2 & := (x_1+x_2) + (y_1+y_2)i \\
z_1 \cdot z_2 & := (x_1 x_2 - y_1 y_2) + (x_1 y_2 + x_2 y_1)i
\end{align}
```

積の記号は省略し、単に「$z_1 z_2$」と書くことが多いです。

## 絶対値
実数$x,y$を使って$z=x+yi$と書いたとき、複素数$z$の**絶対値**(absolute value)を次のように定義します。

```math
\begin{align}
|z| := \sqrt{x^2 + y^2}
\end{align}
```
絶対値は複素数の大きさ($0$からの距離)を表す概念で、$0$以上の実数になります。

実数$x_1,x_2,y_1,y_2$に対して

```math
\begin{align}
(x_1 x_2 - y_1 y_2)^2 + (x_1 y_2 + x_2 y_1)^2 = (x_1^2 + y_1^2)(x_2^2 + y_2^2)
\end{align}
```
となるため、「積の絶対値」と「絶対値の積」は等しくなります。

```math
\begin{align}
|z_1 z_2| = |z_1||z_2|
\end{align}
```

## 複素共役
実数 $x, y$ を使って $z=x+yi$ と書いたとき、複素数 $z$ の**複素共役**(complex conjugate)を次のように定義します。

```math
\begin{align}
\overline{z} := x - yi
\end{align}
```
複素共役について、次のことが成り立ちます。

```math
\begin{align}
&|z|  = |\overline{z}| \\
&|z|^2 = z\overline{z} = x^2 + y^2 \in \mathbb{R} \\
\end{align}
```

# **行列**
## 行列の定義
縦と横に数を並べたものを**行列**(matrix)といいます。
例えば、次のようなものは行列です。

```math
\begin{align}
\left(
    \begin{array}{cc}
      1 & 2 \\
      3 & 4
    \end{array}
\right), \quad 
\left(
    \begin{array}{cc}
      \sqrt{5} & 2 \\
      i & 3+i
    \end{array}
\right), \quad 
\left(
    \begin{array}{c}
      1 \\
      0
    \end{array}
\right), \quad 
\left(
    \begin{array}{cc}
      1 & 2 
    \end{array}
\right), \quad 
\left(
    \begin{array}{ccc}
      4 & 3 & 8 \\
      9 & 5 & 1 \\
      2 & 7 & 6
    \end{array}
\right)
\end{align}
``` 

ここでは、

```math
\begin{align}
\left(
    \begin{array}{cc}
      1 & 2 \\
      3 & 4
    \end{array}
\right)
\end{align}
```
を例に、行列の用語について説明します。

まず、行列の横方向を**行**(row)といい、上から下に向かって順に第1行、第2行、、、と数えます。この例では、

```math
\begin{align}
第1行が \,
\left(
    \begin{array}{cc}
      1 & 2
    \end{array}
\right) \\
第2行が \,
\left(
    \begin{array}{cc}
      3 & 4
    \end{array}
\right)
\end{align}
```
です。
行列の縦方向を**列**(column)といい、左から右に向かって順に第1列、第2列、、、と数えます。この例では、

```math
\begin{align}
第1列が \,
\left(
    \begin{array}{c}
      1 \\ 3
    \end{array}
\right) \\
第2列が \,
\left(
    \begin{array}{c}
      2 \\ 4
    \end{array}
\right)
\end{align}
```
です。

また、行列に並べられた数字を**成分**(entry)といい、「第○行第×列」「$(○, ×)$成分」といいます。この例では、

```math
\begin{align}
\left(
    \begin{array}{cc}
      第1行第1列 & 第1行第2列 \\
      第2行第1列 & 第2行第2列
    \end{array}
\right), \quad
\left(
    \begin{array}{cc}
      (1,1)成分 & (1,2)成分 \\
      (2,1)成分 & (2,2)成分
    \end{array}
\right)
\end{align}
```
となります。  
行列の大きさを表すとき、行数と列数を明示して「$2 \times 2$行列」のようにいいます。

```math
\begin{align}
\left(
    \begin{array}{c}
      1 \\
      0
    \end{array}
\right)
\end{align}
```
は $2 \times 1$ 行列です。行数と列数が同じものを**正方行列**といいます。  

行が1つの行列を**行ベクトル**、列が1つの行列を**列ベクトル**といいます。例えば、

```math
\begin{align}
\left(
    \begin{array}{cc}
      1 & 2
    \end{array}
\right) は行ベクトル \\
\left(
    \begin{array}{c}
      1 \\ 3
    \end{array}
\right) は列ベクトル
\end{align}
```
です。

行列の成分の部分を変数の添え字として表すことができます。添え字の1つ目の変数は行を表し、2つ目の変数は列を表します。

```math
\begin{align}
(a_{ij}), \quad 
\left(
    \begin{array}{cc}
      a_{11} & a_{12} \\
      a_{21} & a_{22}
    \end{array}
\right)
\end{align}
```

## 単位行列と逆行列
$n \times n$ 正方行列で「行と列が同じ成分が1で、行と列が異なる成分が0」となるものを**単位行列**といい、$\mathbb{I}_n$ と書きます。

```math
\begin{align}
\mathbb{I}_n := 
\left(
    \begin{array}{cccc}
      1 & 0 & \cdots & 0 \\
      0 & 1 & \cdots & 0 \\
      \vdots & \vdots & \ddots & \vdots \\
      0 & 0 & \cdots & 1 \\
    \end{array}
\right)
\end{align}
```

文脈上、$n$ が明らかな場合は単に $\mathbb{I}$ と書きます。
また、任意の $n \times n$ 正方行列 $A$ に対して、

```math
\begin{align}
A \mathbb{I}_n = \mathbb{I}_n A = A
\end{align}
```
となります。

$n \times n$ 正方行列 $A$ に対し、

```math
\begin{align}
AB = \mathbb{I}_n, \quad BA = \mathbb{I}_n
\end{align}
```
となる $n \times n$ 正方行列 $B$ が存在するとき、$A$ を**正則行列**(regular matrix)といいます。また、$B$ を $A$ の**逆行列**(inverse matrix)といい、$A^{-1}$ と書きます。 

## 転置行列と随伴行列
行列 $A$ の行と列を入れ替えた行列を**転置**(transpose)といい、$A^T$と書きます。例えば、

```math
\begin{align}
\left(
    \begin{array}{cc}
      1 & 2 \\
      3 & 4
    \end{array}
\right)^T = 
\left(
    \begin{array}{cc}
      1 & 3 \\
      2 & 4
    \end{array}
\right), \quad
\left(
    \begin{array}{c}
      1 \\
      0
    \end{array}
\right)^T = 
\left(
    \begin{array}{cc}
      1 & 0
    \end{array}
\right), \quad
(a_{ij})^T = (a_{ji})
\end{align}
```
となります。$m \times n$ 行列の転置は $n \times m$ 行列になります。
行列 $A$ の各成分の複素共役にしたものを**複素共役行列**といい、 $\overline{A}$ と書きます。例えば、

```math
\begin{align}
\overline{\left(
    \begin{array}{cc}
      1 & 2 \\
      3 & 4
    \end{array}
\right)} = 
\left(
    \begin{array}{cc}
      1 & 2 \\
      3 & 4
    \end{array}
\right), \quad 
\overline{\left(
    \begin{array}{cc}
      \sqrt{5} & 2 \\
      i & 3+i
    \end{array}
\right)} =
\left(
    \begin{array}{cc}
      \sqrt{5} & 2 \\
      -i & 3-i
    \end{array}
\right), \quad 
\overline{(a_{ij})} = (\overline{a_{ij}})
\end{align}
```
となります。  

「複素共役して転置した行列」と「転置して複素共役した行列」は同じになります。これを**随伴行列**(adjoint matrix)といい、 $A^*$ と書きます。

```math
\begin{align}
A^* := \overline{A}^T =  \overline{A^T} 
\end{align}
```
例えば、

```math
\begin{align}
\left(
    \begin{array}{cc}
      1 & 2 \\
      3 & 4
    \end{array}
\right)^* = 
\left(
    \begin{array}{cc}
      1 & 3 \\
      2 & 4
    \end{array}
\right), \quad 
\left(
    \begin{array}{cc}
      \sqrt{5} & 2 \\
      i & 3+i
    \end{array}
\right)^* =
\left(
    \begin{array}{cc}
      \sqrt{5} & -i \\
      2 & 3-i
    \end{array}
\right), \quad 
(a_{ij})^* = (\overline{a_{ji}})
\end{align}
```
となります。  

## ユニタリ行列

随伴行列が逆行列となる $n \times n$ 正方行列 $U$ を**ユニタリ行列**(unitary matrix)といいます。

```math
\begin{align}
UU^* = \mathbb{I}_n, \quad U^*U = \mathbb{I}_n, \quad U^* = U^{-1}
\end{align}
```