量子情報理論の基本：エントロピー（１） #量子コンピュータ

$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$

はじめに

量子情報理論というからには量子の観点で情報を扱わないといけないのですが、これまでの記事では、主に、量子状態をどのように定量化して扱うかとか、それがどのように時間変化するかとか、最終的になされる測定はどう記述されるのか、といったあたりをウロウロしていました。今回から、情報理論らしい話題も取り入れていきます。まず、「エントロピー(entropy)」です。長くなりそうなので、２回に分けます。今回の（１）では、古典的な情報理論におけるエントロピーについておさらいし、次回の（２）で量子情報理論におけるエントロピーについて勉強します。

参考にさせていただいたのは、以下の文献です。

エントロピー（古典的なエントロピー、シャノン・エントロピー）

定義

生起確率が$p \space (0 \leq p \leq 1)$である事象Aがあったとします。その事象が実際に生起したときに得られる情報量は、どのように定義されるべきでしょうか？情報の量というからには正の値になっていてほしいです。また、確率が小さい事象が生起したときの方が情報量（＝びっくり度＝インパクト＝得られる知識量）が大きい感覚がありますので、情報量はpについて単調減少とするのが良いです。さらに、２つの事象が同時に発生する確率は両者の積になりますが、そのときに得られる情報量は、各事象が生起したときに得られる情報量の和とする（加法性の要請）のが自然な感覚です¹。

ということを考え合わせ、なるべく簡単な関数形にしたいとすると、情報量を

-\log p  \tag{1}

のように定義するのが良い、ということがわかります²。

情報量を別の言い方で規定することもできます。その事象が生起する前に立ち返ってみると、情報量とは「不確実さの度合い」を表していると言っても良いです。その事象が生起することによって、有限だった不確実さがゼロになり、その分、ゼロだった情報量が有限の値になるという見方です。つまり、「ある事象が生起する前の不確実さの度合い」＝「ある事象が生起したときに得られる情報量」という考え方ですね。

古典的なエントロピー（シャノン・エントロピーとも呼ばれますが、本記事ではいちいち面倒なので、以後、単にエントロピーと呼ぶことにします）というのは、事象が生起する前の「不確実さの度合い」の平均値（期待値）として定義されます。すなわち、いま、$n$個の事象$\{ A_1,\cdots,A_n\}$があり、その各々の生起確率が$\{ p_1, \cdots , p_n\}$だったとすると、この状況におけるエントロピーは、

H(A) \equiv H(p_1, \cdots, p_n) \equiv -\sum_{i=1}^{n} p_i \log p_i  \tag{2}

と定義されます³。ここで、

\sum_{i=1}^{n} p_i =1  \tag{3}

です。

もう少し説明を加えると、エントロピーというのは、起こり得る事象の系列と各確率がわかっているときに、その状況において定義される指標です。例えば、東京の天気が「晴れ、曇、雨、雪」になるという事象系列があり、各々の確率が「1/2,1/4,1/8,1/8」で与えられたという状況のもとで一意に決まる値です。もし各確率が別の値「1/4,1/4,1/4,1/4」だったとすると、エントロピーは別の値になります。この例の場合、前者と後者を比べると不確実さはどちらが大きいでしょうか？前者の場合、だいたい晴れで、そうでなければ曇りかなーと思っておけば良いのに対し、後者の場合、生起確率が全事象で均一になっているので、どんな天気になるかは全く不明確です。という意味で、不確実さは後者の方が大きいと言えます（つまり、後者の方がエントロピーが大きいです。式(3)に代入して計算してもわかりますが）。そんな感覚を定量化するものであると理解しておけば良いと思います。

さらにもう少し説明を加えると、上の例では東京の天気しか考えていませんでしたが、当然別の状況もあり得ます。例えば、大阪の天気が「晴れ、曇、雨、雪」になる可能性と各確率がわかっているという状況とか、あるいは、天気ではなく、いまここにあるサイコロを振ったときの目が「１から６のいずれか」になる可能性と各確率がわかっているといった状況も考えられます。その各々についてエントロピーが定義できます。そのような複数の事象系列の可能性があったときに、それを結合した複合事象についてのエントロピー（結合エントロピー）や、ある事象が生起したことがわかったときに得られるエントロピー（条件付きエントロピー）等々の指標も考えることができます。これらも情報理論的に重要な概念ですが、その話は次節以降で説明することにします。

その前に、まず、エントロピーの定義からわかる、いくつかの重要な性質についておさえておきます。

性質

エントロピーには、以下の性質があります。

(1) エントロピーの最小値は0（非負）
(2) エントロピーの最大値はlog(n)
(3) エントロピーは凹関数

順に確認します。

(1) エントロピーの最小値は0（非負）

H = - \sum_{i=1}^{n} p_i \log p_i \geq 0  \tag{4}

が成り立ちます。$-p_i \log p_i \geq 0$であることから明らかです。等号が成り立つのは、$p_i \log p_i$がすべて0になる場合です。$\sum_i p_i = 1$なので、$\{ p_i \}$のうちでどれか一つが1で、それ以外がすべて0という場合のみ、等号が成り立つことになります。つまり、どれか一つの事象が必ず生起する場合ですね。何が起きるか決まっているので不確実さはゼロ、すなわちエントロピーはゼロになります。

(2) エントロピーの最大値はlog(n)

H = - \sum_{i=1}^{n} p_i \log p_i \leq \log n  \tag{5}

が成り立ちます。

【証明】

$\sum_{i=1}^{n} p_i = 1$という制約条件のもとで、式(5)を最大化したいので、ラグランジェの未定乗数法を使います。未定乗数を$\lambda$とし、関数、

f(p_1,\cdots,p_n,\lambda) = - \sum_{i=1}^{n} p_i \log p_i + \lambda (\sum_{i=1}^{n} p_{i} - 1) \tag{6}

を最大化する変数の組$\{ p_i \}$を求めます。そのため、各変数で偏微分したものが0という条件で連立方程式を解きます⁴。

\frac{\partial}{\partial p_i} (- \sum_{i}^{n} p_i \log p_i + \lambda (\sum_{i}^{n} p_{i} - 1)) = -\log p_i - \log e +\lambda = 0  \tag{7}

となります。ここで、

\log p = \log e \cdot \ln p  \tag{8}

を使いました。式(7)より、

\begin{align}
\log p_i &= - \log e + \lambda \\
p_i &= \frac{2^{\lambda}}{e}  \tag{9}
\end{align}

となり、$p_i$は$i$に依存しない一定値になることがわかります。$\sum_{i=1}^{n} p_i = 1$なので、$p_i = \frac{1}{n}$となり、エントロピーは、

H = n \times \frac{1}{n} (-\log \frac{1}{n}) = \log n  \tag{10}

となります。すべての確率が同じ値、つまり、生起確率に偏りが全くない場合、エントロピーは最大値になります。（証明終）

ここで、大事なことを付け加えておきます。それは、「エントロピーはビット数に等しい」ということです。いま、ある事象が確率的に連続して発生するような情報源があったとします。先程は天気の例を出しましたが、今の場合、あまり良い例ではないので、別の例にします。ちょっと抽象的になりますが、{a,b,c,d}という文字が何らかの出現確率で発生する情報源をイメージしてください。これを、デジタル信号にして（つまりビット化して）、ある受信者に間違いなく送信したいとします。さて、何ビット必要でしょうか？という問題を考えます。送信すべき文字が4つとも均等確率で発生するのであれば、容易にわかる通り、2ビット必要ですね。頭の中で$\log 4$を計算したと思います（多分）。文字が256種類あって均等確率で発生するなら、必要なビット数は8ビットですね（$\log 256$）。つまり、これは何を計算しているかというと、均等確率の場合のエントロピーを計算していることに相当します。では、出現確率が均等でなかった場合、どうでしょうか。4文字の例の場合で言うと、例えば、aとbの出願確率がとても高く、cやdは滅多に出現しない場合、ビット数は2ビットも必要ないです。極端な話、aとbしか出現しない場合は、1ビットでいけますね。これは、何を計算しているかというと、まさに出現確率が偏っている場合のエントロピーを計算していることになります。つまり、出現確率に応じてそのエントロピーを計算すれば、それが送信に最低限必要なビット数になるということです⁵。出現確率がわからない場合は、エントロピーの最大値である$\log n$に相当するビット数を用意しておけば十分です。

(3) エントロピーは凹関数

確率変数$\{ p_1, \cdots , p_n \}$をn次元ベクトル$p = (p_1, \cdots , p_n)$と見立てると、エントロピー、

H(p) = H(p_1, \cdots , p_n) \tag{11}

は、n次元ベクトルを変数とするスカラー関数とみなすことができます。としたときに、この関数（エントロピー）は、凹関数です。すなわち、任意の実数$x \space (0 \leq x \leq 1)$に対して、

H(xp + (1-x)q) \geq x H(p) + (1-x) H(q)  \tag{12}

が成り立ちます⁶。ここで、$p,q$は確率変数を表すn次元ベクトルです。

【証明】

まず、関数$f(t)=-t \log t$が凹関数であることを確認しておきます。$t$で微分すると、

f^{\prime}(t) = - \log t - log \space e  \tag{13}

となり、これは$t$について単調減少です。微分が単調減少なので、元の関数は上に凸（つまり下に凹）、つまり、$f(t)$は凹関数です。この知見を使うと、

\begin{align}
H(xp+(1-x)q) &= \sum_{i=1}^{n} f(xp_i + (1-x) q_i) \\
& \geq \sum_{i=1}^{n} (xf(p_i) + (1-x) f(q_i)) \\
&= x \sum_{i=1}^{n} f(p_i) + (1-x) \sum_{i=1}^{n} f(q_i) \\
&= x H(p) + (1-x) H(q)  \tag{14}
\end{align}

が成り立ちます。したがって、H(p)は凹関数です。（証明終）

エントロピーの性質がわかったところで、次に、複数の事象に対するエントロピーの間に成り立つ関係について説明します。まず、「結合(joint)エントロピー」と「条件付き(conditional)エントロピー」についてです。

結合エントロピーと条件付きエントロピー

定義

結合エントロピー

2つの事象の組、$A=\{ A_1, \cdots , A_n \}, \space B=\{ B_1, \cdots , B_m\}$が同時に起きるとき、その複合事象の生起確率を$p(A_i, B_j)$とすると、複合事象としての不確実さの度合い＝「結合エントロピー」は、以下のように定義されます。

H(A,B) \equiv - \sum_{i=1}^{n} \sum_{j=1}^{m} p(A_i,B_j) \log p(A_i,B_j)  \tag{15}

条件付きエントロピー

事象$A_i$が生起したという前提のもと、事象$B_j$が生起する条件付き確率は$p(B_j|A_i)$なので、事象$A_i$が生起したときの事象$B=\{ B_1, \cdots , B_m\}$の不確実さの度合い＝エントロピー$H(B|A_i)$は、

H(B|A_i) = - \sum_{j=1}^{m} p(B_j|A_i) \log p(B_j|A_i)  \tag{16}

と書けます。事象$A$が起きたという条件の下での事象$B$に関する不確実さの度合い＝「条件付きエントロピー」は、$A_i$についての平均（期待値）として、

H(B|A) = -\sum_{i=1}^{n} \sum_{j=1}^{m} p(A_i) p(B_j|A_i) \log p(B_j|A_i)  \tag{17}

と定義されます。ここで、$p(A_i) = \sum_{j} p(A_i, B_j)$を使いました。

性質

結合エントロピーと条件付きエントロピーには、以下に示す性質があります。

(4) 結合エントロピーと条件付きエントロピーとの関係：$H(A,B)=H(A)+H(B|A)$
(5) 条件付きエントロピーの最小値は0（非負）：$H(B|A) \geq 0$
(6) 結合エントロピーと各事象のエントロピーとの関係：$H(A),H(B) \leq H(A,B) \leq H(A)+H(B)$
(7) 条件付きエントロピーと各事象のエントロピーとの関係：$H(A) \geq H(A|B),\space H(B) \geq H(B|A)$

順に確認します。

(4) 結合エントロピーと条件付きエントロピーとの関係

H(A,B)=H(A)+H(B|A) \tag{18}

が成り立ちます。日本語で表現すると、事象Aと事象Bの結合エントロピーは、事象Aのエントロピーと、事象Aを知った後の事象Bのエントロピーとの和に等しい、です。

【証明】

$H(A,B)$の定義より、

\begin{align}
H(A,B) &= -\sum_{i,j} p(A_i,B_j) \log p(A_i,B_j) \\
&= -\sum_{i,j} p(A_i,B_j) \log (p(A_i)p(B_j|A_i)) \\
&= -\sum_{i,j} p(A_i,B_j) \log p(A_i) - \sum_{i,j} p(A_i,B_j) \log p(B_j|A_i) \\
&= -\sum_{i} p(A_i) \log p(A_i) - \sum_{i,j} p(A_i)p(B_j|A_i) \log p(B_j|A_i) \\
&= H(A) + H(B|A)  \tag{19}
\end{align}

となります。（証明終）

(5) 条件付きエントロピーの最小値は0（非負）

H(B|A) \geq 0  \tag{20}

が成り立ちます。定義より明らかですね。

(6) 結合エントロピーと各事象のエントロピーとの関係

H(A),H(B) \leq H(A,B) \leq H(A)+H(B)  \tag{21}

が成り立ちます。

【証明】

まず、左側の不等号について。

$H(A,B)=H(A)+H(B|A)$において、$H(B|A) \geq 0$なので、$H(A) \leq H(A,B)$が成り立ちます。同様に、$H(B) \leq H(A,B)$も成り立ちます。等号は、事象Aと事象Bが完全に相関している、すなわち、事象Aが決まると完全に事象Bが決まるときです。

次に、右側の不等号について。

$H(A,B)-H(A)-H(B)$が0以下であることを証明すれば良いです。

\begin{align}
H(A,B)-H(A)-H(B) &= -\sum_{i,j} p(A_i,B_j) \log p(A_i,B_j) + \sum_{i} p(A_i) \log p(A_i) + \sum_{i} p(B_i) \log p(B_i)  \\
&= -\sum_{i,j} p(A_i,B_j) \log p(A_i,B_j) + \sum_{i,j} p(A_i,B_j) \log p(A_i) + \sum_{i,j} p(A_i,B_j) \log p(B_j) \\
&= \sum_{i,j} p(A_i,B_j) \log \frac{p(A_i)p(B_j)}{p(A_i,B_j)} \tag{22}
\end{align}

ここで、

\begin{align}
\ln x \leq x-1 \\
\log x \leq \frac{x-1}{\ln 2} \tag{23}
\end{align}

を使うと、式(22)は、

\begin{align}
H(A,B)-H(A)-H(B) &\leq \frac{1}{\ln 2} \sum_{i,j} p(A_i,B_j) (\frac{p(A_i)p(B_j)}{p(A_i,B_j)}-1) \\
&= \frac{1}{\ln 2} \sum_{i,j} (p(A_i)p(B_j)-p(A_i,B_j)) \\
&= \frac{1-1}{\ln 2} = 0  \tag{24}
\end{align}

したがって、

H(A,B) \leq H(A) + H(B)  \tag{25}

が成り立ちます⁷。

等号は、式(24)からわかるように、$p(A_i)p(B_j)=p(A_i,B_j)$のときのみです。つまり、事象Aと事象Bが独立事象の場合のみです。（証明終）

(7) 条件付きエントロピーと各事象のエントロピーとの関係

H(A) \geq H(A|B),\space H(B) \geq H(B|A)  \tag{26}

が成り立ちます。

【証明】

\begin{align}
H(A|B) &= H(A,B)-H(B) \leq H(A)+H(B)-H(B) = H(A) \\
H(B|A) &= H(A,B)-H(A) \leq H(A)+H(B)-H(A) = H(B)  \tag{27}
\end{align}

したがって、式(26)が成り立ちます。等号が成り立つのは、$H(A,B)=H(A)+H(B)$のとき、すなわち、事象Aと事象Bが独立事象のときのみです。（証明終）

相互情報量

定義

事象Aと事象Bについての「相互情報量(mutual information)」は、事象Aを知ったときに事象Bの不確実さがどれだけ減るかを表す指標です。逆に言うと、事象Aがわかったときに、獲得できる事象Bについての情報量とも言えます。例えば、東京の天気が「雨」であることを知ったときに、大阪の天気についての不確実さがどれだけ減るかを表しています。または、東京の天気がわかったとき、大阪の天気についての情報量がどれだけ増えるかを表しています。確実には言えないけれど、東京が「雨」なら、大阪も「雨」という可能性が少し増えて、大阪の天気についての情報量（＝知識）が増えるような気がしますよね。そのような感覚を定量化したものだと思えば良いです。

相互情報量は、$I(A:B)$という記号で表し、以下のように定義されます。

I(A:B) = H(B) - H(B|A)  \tag{28}

これを確率で表現すると、以下のようになります。

\begin{align}
I(A:B) &= -\sum_{j} p(B_j) \log p(B_j) + \sum_{i,j} p(A_i) p(B_j|A_i) \log p(B_j|A_i) \\
&= -\sum_{i,j} p(A_i,B_j) \log p(B_j) + \sum_{i,j} p(A_i) \frac{p(A_i,B_j)}{p(A_i)} \log \frac{p(A_i,B_j)}{p(A_i)} \\
&= \sum_{i,j} p(A_i,B_j) \log \frac{p(A_i,B_j)}{p(A_i)p(B_j)}  \tag{29}
\end{align}

性質

相互情報量には、以下の性質があります。

(8) 相互情報量は対称：$I(A:B)=I(B:A)$
(9) 相互情報量の最小値は0（非負）：$I(A:B) \geq 0$
(10) 相互情報量と各事象のエントロピーとの関係：$I(A:B) \leq H(A),H(B)$
(11) 相互情報量と各事象のエントロピーおよび結合エントロピーとの関係：$I(A:B)=H(A)+H(B)-H(A,B)$

順に確認します。

(8) 相互情報量は対称

I(A:B)=I(B:A)  \tag{30}

が成り立ちます。式(29)の定義より、明らかです⁸。

(9) 相互情報量の最小値は0（非負）

I(A:B) \geq 0  \tag{31}

が成り立ちます。定義より明らかです。等号は、事象Aと事象Bが独立事象のときのみ成り立ちます。

(10) 相互情報量と各事象のエントロピーとの関係

I(A:B) \leq H(A),H(B)  \tag{32}

が成り立ちます。

【証明】

式(28)の定義と条件付きエントロピーが非負であることを使います。

I(A:B) = H(B) - H(B|A) \leq H(B)  \tag{33}

同様に、

I(A:B) = H(A) - H(A|B) \leq H(A)  \tag{34}

が成り立ちます。等号は、事象Aと事象Bが完全に相関している、すなわち、事象Aが決まると完全に事象Bが決まるときです。（証明終）

(11) 相互情報量と各事象のエントロピーおよび結合エントロピーとの関係

I(A:B)=H(A)+H(B)-H(A,B)  \tag{35}

が成り立ちます。

【証明】

\begin{align}
I(A:B) &= H(B) - H(B|A)  \\
&= H(B) - (H(A,B) - H(A)) \\
&= H(A) + H(B) - H(A,B)  \tag{36}
\end{align}

（証明終）

相対エントロピー

定義

最後に、「相対(relative)エントロピー」についてです。これは、２つの確率分布がどれだけ違うかを表すエントロピーに似た指標です。「カルバック・ライブラー距離(Kullback-Leibler distance)」または「カルバック・ライブラー・ダイバージェンス(Kullback-Leibler divergence)」とも呼ばれています。２つの確率分布$p(A_i),p(B_i)$に対する相対エントロピーは、以下のように定義されます。

\begin{align}
H(A||B) &\equiv \sum_{i} p(A_i) \log \frac{p(A_i)}{p(B_i)} \\
&= \sum_{i} p(A_i) (\log p(A_i) - \log p(B_i)) \\
&= - H(A) - \sum_{i} p(A_i) \log p(B_i) \tag{37} 
\end{align}

性質

相対エントロピーには、以下の性質があります。

(12) 相対エントロピーの最小値は0（非負）：$H(A||B) \geq 0$

確認します。

(12) 相対エントロピーの最小値は0（非負）

H(A||B) \geq 0  \tag{38}

が成り立ちます。

【証明】

定義および式(23)から、

\begin{align}
H(A||B) &= - \sum_{i} p(A_i) \log \frac{p(B_i)}{p(A_i)} \\
&geq \frac{1}{\ln 2} \sum_{i} p(A_i) (1 - \frac{p(B_i)}{p(A_i)}) \\
&= \frac{1}{\ln 2} \sum_{i} (p(A_i) - p(B_i)) \\
&= \frac{1}{\ln 2} (1-1) = 0 \tag{39}
\end{align}

が成り立ちます。等号は確率分布$p(A_i),p(B_i)$が完全に一致する場合のみです。（証明終）

両者一致している場合にゼロとなり、かつ、分布の違いを表す指標なので、カルバック・ライブラー「距離」と言ったりするのですが、距離の条件を満たしているわけではないので、正確には「距離」ではありません。

各種エントロピーの関係図

いろんな種類のエントロピー（やエントロピーもどき）について、その重要な性質を淡々と説明してきましたが、覚えるのが大変ですよね。というわけで、最後のまとめとして、便利な図を紹介します。「エントロピーの性質について完全に信頼できる道しるべではないが、エントロピーのいろいろな定義や性質を覚えるための記憶術として便利である」として、ニールセン・チャンに掲載してあった図に基づき描きました。

どうでしょう。単に公式を覚えやすくするための図というより、各エントロピーが意味するものを理解するという観点からも、すっと頭に入って来る便利な図ではないでしょうか。

おわりに

古典的な情報理論におけるエントロピーについて、基本的な事項に絞って説明しました。次回は、量子情報理論におけるエントロピーについて勉強していきます。今回の記事で理解した古典エントロピーの常識が、量子の世界では成り立たなくなる場合が多々あって、不思議かつ興味深いです。その面白さを十分味わうためにも、今回の古典のお話は大前提の知識になるので、しっかり理解しておくようにしましょう！

以上

もしかすると、ここで「ん？」と思われるかもしれませんが、さらっと流してください。こう考えると万事うまく行くのです。 ↩
情報理論の習慣に従い、$log$の底は2とし、自然対数(底がe)は$\ln$と書くことにします。 ↩
ここで確率pが0の場合もあり得るので、その場合$p \log p = 0 \log 0 = 0$であると約束しておきます。 ↩
ラグランジェの未定乗数法では、通常、$\lambda$に関する微分がゼロという条件も使うのですが、それをやらないでも答えが出ることもあります。 ↩
具体的にどんなビット割当をして符号化（＝データ圧縮）すればもっとも効率が良いのかという話題に踏み込むと、本記事がそれで終わってしまうので、感覚的な説明でとりあえずご勘弁ください。 ↩
下に凸な関数が凸関数で、下に凹（つまり上に凸）な関数が凹関数です。 ↩
この性質のことを「劣加法性」と言うようです。 ↩
数式的には一目瞭然の性質なのですが、日常感覚としては、ちょっと不思議な感じがして面白いです。例えば、東京の天気がわかったときに大阪の天気の不確実さがどれだけ減るか、ということと、逆に大阪の天気がわかったときに東京の天気の不確実さがどれだけ減るか、ということが値として等しいということです。これは、天気だけでなく、独立でない任意の事象同士で成り立ちます。 ↩