読者です 読者をやめる 読者になる 読者になる

倭算数理研究所

科学・数学・学習関連の記事を、「倭マン日記」とは別に書いていくのだ!

『Quantum Computing: A Gentle Introduction』の演習問題を解く A.3

量子コンピュータ

Quantum Computing: A Gentle Introduction (Scientific and Engineering Computation) (English Edition)

Quantum Computing: A Gentle Introduction (Scientific and Engineering Computation) (English Edition)

目次はこちら

Exercise A.3.

  • a. Show that the tensor product of a pure distribution is pure.
  • b. Show that any distribution is a linear combination of pure distributions. Conclude that the set of distributions on a finite set  { A } is convex.
  • c. Show that any pure distribution on a joint system  { A \times B } is uncorrelated
  • d. A distribution is said to be extremal if it cannot be written as a linear combination of other distributions. Show that the extremal distributions are exactly the pure distributions.

数学的に厳密でない箇所がいくつもありますが、適当に解釈して下さいませ。

a.
有限集合  { A } 上の確率分布  { \mu_a }

  { \displaystyle\begin{align*}
  \mu_a(a')
    = \begin{cases}
        1 & \textrm{if}\,\, a' = a \\
        0 & \textrm{otherwise}
      \end{cases}\qquad (a,\,a' \in A)
\end{align*}}

を満たしているとき純粋 (pure) であると定義されます。 これはまた、集合  { A } 上に定義されたクロネッカーデルタ*1  { \delta_{aa'}^A } を使うと

  { \displaystyle\begin{align*}
  \mu_a(a') = \delta_{aa'}^A
\end{align*}}

と書けます。

さて、 { \mu_a^A,\,\mu_b^B } をそれぞれ有限集合  { A,\,B } 上の純粋な確率分布とすると、これらのテンソル { \mu_a^A \otimes \mu_b^B }

  { \displaystyle\begin{align*}
  (\mu_a^A \otimes \mu_b^B)(a',\,b')
    &= \mu_a^A(a')\mu_b^B(b') \\
    &= \delta_{aa'}^A\delta_{bb'}^B \\
    &= \begin{cases}
        1 & \textrm{if}\,\, (a',\,b') = (a,\,b) \\
        0 & \textrm{otherwise}
      \end{cases}
\end{align*}}

となって、これは  { A \times B } 上の純粋な確率分布であることが分かります。

b.
 { A } 上の任意の確率分布  { \mu }

  { \displaystyle\begin{align*}
  \mu(a) &= \sum_{a' \in A} \mu(a')\delta_{aa'}^A
\end{align*}}

と変形できますが、 { \delta_{aa'}^A } { A } 上の純粋な確率分布なので、結局、任意の確率分布は純粋な確率分布の線形結合で書けることが分かりました。  { \delta_{aa'}^A } の係数である  { \mu(a') } { a = a' } となる確率なので、線形結合の係数  { c_a }

  { \displaystyle\begin{align*}
  0 \leqq c_a \leqq 1,\qquad \sum_{a \in A}c_a = 1
\end{align*}}

を満たすことも分かります。

1個のサイコロの出る目を考えましょう。  { A = \{1,\,2,\,\cdots,\,6\} } として、出る目の確率分布は

  { \displaystyle\begin{align*}
  \mu(a) = \tfrac{1}{6} \qquad (\forall a \in A)
\end{align*}}

ですが、これを純粋な確率分布  { \delta_{aa'} } (目  { a } だけが必ず出る確率分布。 上付きの  { A } は省略)の線形結合として表すと

  { \displaystyle\begin{align*}
  \mu(a)
    &= \sum_{a'=1}^6\tfrac{1}{6}\delta_{aa'} \\
    &= \tfrac{1}{6}\delta_{a1} + \tfrac{1}{6}\delta_{a2} + \cdots + \tfrac{1}{6}\delta_{a6}
\end{align*}}

となります。

確率分布の集合が凸であること 凸集合については「wikipedia:凸集合」などを参照。 大雑把には、任意の2つの元の間にある点がまたその集合の元になっているとして定義されます。

 { \mu,\,\nu } { A } 上に定義された2つの確率分布とします( { \mu,\,\nu \in \mathcal{P}^A })。 以下を満たす  { s,\,t }

  { \displaystyle\begin{align*}
  s + t = 1,\quad s \geqq 0,\quad t \geqq 0
\end{align*}}

を係数として  { \mu,\,\nu } の線形結合を考えると

  { \displaystyle\begin{align*}
  s\mu(a) + t \nu(a)
    &= s\sum_{a' \in A} \mu(a') \delta_{aa'} + t \sum_{a' \in A} \nu(a') \delta_{aa'} \\
    &= \sum_{a' \in A}\left\{s\mu(a') + t\nu(a')\right\}\delta_{aa'}
\end{align*}}

ここで、最後の和の係数を  { c_{a'} } とおく( { c_{a'} = s\mu(a') + t\nu(a') })と、この係数は

  { \displaystyle\begin{align*}
  c_{a'} \geqq 0 \\[2mm]
  \sum_{a' \in A} c_{a'}
    &= s \sum_{a' \in A} \mu(a') + t \sum_{a' \in A} \nu(a') \\
    &= s + t \qquad \left(\sum_{a' \in A} \mu(a') = \sum_{a' \in A} \nu(a') = 1\right) \\
    &= 1
\end{align*}}

となって、 { s\mu + t\nu } も確率分布となります。 よって  { A } 上に定義された確率分布の集合( { \mathcal{P}^A })は凸集合となります。

c.
 { \mu_{a,b}^{A \times B} } { A \times B } 上の純粋な確率分布とすると

  { \displaystyle\begin{align*}
  \mu_{a,b}^{A \times B}(a',\,b')
    &= \begin{cases}
        1 & \textrm{if}\,\,(a',\,b') = (a,\,b) \\
        0 & \textrm{otherwise}
      \end{cases} \\
    &= \delta_{aa'}^A\delta_{bb'}^B \\
    &= (\delta_a^A \otimes \delta_b^B)(a',\,b') \qquad
      \left(\textrm{where}\,\,\delta_a^A(a') = \delta_{aa'}^A,\quad\delta_b^B(b') = \delta_{bb'}^B\right) \\[2mm]
  \therefore\,\mu_{a,\,b}^{A \times B} &= \delta_a^A \otimes \delta_b^B
\end{align*}}

ここで  { \delta_a^A,\,\delta_b^B } がそれぞれ  { A,\,B } 上の関数なので、 { \mu_{a,\,b}^{A \times B} } { A,\,B } 上の関数のテンソル積で書け、定義より  { \mu_{a,\,b}^{A \times B} } が独立であることが示せました。

 { A = B = \{0, 1\} } として、 { A \times B } 上の純粋な関数  { \mu_{1,0}^{A \times B} } { (a,\,b) = (1,\,0) } のみが100%起こる確率分布)を前回のように表にすると

a \ b 0 1  { \mu_A }
0 0 0 0
1 1 0 1
 { \mu_B } 1 0 1

となります。 周辺分布は確実に起こる事象を含む行・列のもののみが1で、その他のものは0です。 したがって、もとの確率分布が周辺分布から再構成できることが簡単に分かり、この確率分布が独立であることが分かります。

d.

  • 「extremal distribution」の日本語訳が分からなかったので極値分布と書くことにします*2
  • 問題では、極値分布とは「他の確率分布の線形結合で書けない分布」であると定義されていますが、小問 b より、任意の確率分布は純粋な分布の線形結合で書けるので、おそらく極値分布の(もう少し)正確な定義は「2つ以上の正の係数を用いて(負の係数は用いない)他の線形結合として表せない確率分布」だと思います。

極値分布 ⇒ 純粋な関数  { \mu }極値分布とします。 小問 b より任意の確率分布は純粋な分布の線形結合で書けるので、その係数を  { c_{a'} } とすると

  { \displaystyle\begin{align*}
  \mu(a) = \sum_{a'\in A}c_{a'}\delta_{aa'} \qquad \left(\sum_{a' \in A}c_{a'} = 1,\,c_{a'} \geqq 0\right)
\end{align*}}

となりますが、 { \mu }極値分布なので、 { c_{a'} } はある1つの要素  { a'' } でのみ0ではありません。 つまり  { c_{a'} = \delta_{a'a''} }。 よって

  { \displaystyle\begin{align*}
  \mu(a) &= \sum_{a' \in A} \delta_{a'a''}\delta{aa'} \\
              &= \delta_{aa''}
\end{align*}}

となって、 { \mu } は純粋な分布となります。

極値分布ではない ⇒ 純粋な分布でない  { \mu }極値分布ではないとすると、ある2つの分布  { \nu,\,\eta } を用いて  { \mu(a) = s\nu(a) + t\eta(a) } (ただし  { s + t = 1,\,s,\,t > 0 })と書けます( { s,\,t } に0は含まない)。  { \nu,\,\eta } を純粋な関数で展開した係数をそれぞれ  { c_{a'},\,d_{a'} } とすると

  { \displaystyle\begin{align*}
  \nu(a)
    &= s\mu(a) + t\eta(a) \\
    &= s\sum_{a' \in A} c_{a'} \delta_{aa'} + t\sum_{a' \in A} d_{a'} \delta_{aa'} \\
    &= \sum_{a' in A} (sc_{a'} + td_{a'})\delta_{aa'}
\end{align*}}

となります。 ここで  { sc_{a'} + td_{a'} } は2つ以上の  { a' } の値について0ではないので、結局  { \mu } は純粋な分布ではないことが分かります。

*1:a, a' が整数とは限りませんが、まぁ適当に解釈して下さい。

*2:本来の極値分布は「extreme value distribution」。