信息论

发表于： 2022-10-28

字数：1832 阅读：≈ 4分钟浏览：

本文总结经典信息论和量子信息论的一些要点。经典部分写的稍微简单点。

写在前面的一些吐槽

~~为什么要有期中考试啊~~😟😟😟

1. 熵

1.1 香农熵

事件集合和对应概率分别为： $$ X=\{x_1,x_2,\dots,x_n\} $$ $$ P=\{p_1,p_2,\dots,p_n\} $$

香农熵定义（常以2为底）：

$$ H(X)\equiv H(p_1,\dots,p_n)=-\sum_x p_x \log p_x\in[0,\log n] $$

相对熵（Kullback-Leibler 散度）：

$$ D\left(p(x)||q(x)\right)\equiv\sum_x p(x)\log\frac{p(x)}{q(x)}\equiv-H(X)-\sum_x p(x)\log q(x) $$

联合熵：

$$ H(X,Y)\equiv-\sum_{x,y}p(x,y)\log p(x,y) $$

条件熵：

$$ H(X|Y)\equiv H(X,Y)-H(Y) $$

互信息（有的书上用$H(X:Y)$表示）：

$$ I(X;Y)\equiv H(X)+H(Y)-H(X,Y) $$

1.2 Von Neumann 熵

Von Neumann 熵定义为：

$$ S(\rho)\equiv-\mathrm{Tr}(\rho\log\rho)=-\sum_x a_x\log a_x $$

其中$a_x$是$\rho$的本征值。

量子相对熵：

$$ S(\rho||\sigma)\equiv\mathrm{Tr}(\rho\log\rho)-\mathrm{Tr}(\rho\log\sigma) $$

量子联合熵：

$$ S\left(\sum_i p_i \ket{i}\bra{i}\otimes\rho_i\right)=H(p_i)+\sum_i p_i S(\rho_i) $$

$\ket{i}$是一组正交基。

特别的，如果密度矩阵能写成张量积形式，其联合熵为： $$ S(\rho\otimes\sigma)=S(\rho)+S(\sigma) $$

量子条件熵：

$$ S(A|B)\equiv S(A,B)-S(B) $$

量子互信息：

$$ S(A:B)\equiv S(A)+S(B)-S(A,B) $$

性质：

Concavity $$ S\left(\sum_i p_i \rho_i\right)\ge\sum_i p_i S(\rho_i) $$
Subadditivity & Triangle inequality (Araki-Lieb inequality) $$ |S(A)-S(B)|\le S(A,B)\le S(A)+S(B) $$
Strong Subadditivity $$ S(A,B,C)+S(B)\le S(A,B)+S(B,C) $$

1.3 Holevo bound

考虑一个量子信息的传递过程：

Alice向Bob发送量子态$\{\rho_X\}$，$X=0,\dots,n$，概率为$p_0,p_1,\dots,p_n$。Bob在收到量子态之后，实施一组POVM测量$\{F_y\}=\{F_0,F_1,\dots,F_m\}$，得到结果为$\{Y\}$。 $$ \text{Alice}\xrightarrow{\{X,p_X\}}\fbox{Encoding}\xrightarrow{\mathcal{E}=\{\rho_X,p_X\}}\fbox{POVM}\xrightarrow{\{Y,p_Y\}}\text{Bob} $$

Holevo证明互信息存在上限： $$ \chi\equiv S\left(\sum_x p_x\rho_x\right)-\sum_x p_x S(\rho_x) $$ $$ I(X;Y)\le\chi $$

Bob从$Y$中可得到的关于$X$的信息量为： $$ I_{acc}(\mathcal{E})=\max_{\{F_y\}}I(X;Y) $$

于是有： $$ I_{acc}(\mathcal{E})\le\chi $$

不能用$n$个qubit传递$n$ bit的信息

假设{0,1}均匀分布，Alice做一种编码： $$\begin{align} &0\longrightarrow\ket{0}\\ &1\longrightarrow\cos\theta\ket{0}+\sin\theta\ket{1} \end{align}$$

其密度矩阵为： $$ \rho=\frac{1}{2}\begin{bmatrix} 1&0\\ 0&0\end{bmatrix} +\frac{1}{2}\begin{bmatrix} \cos^2\theta&\cos\theta\sin\theta\\ \cos\theta\sin\theta&\sin^2\theta\end{bmatrix} $$

本征值为$(1\pm\cos\theta)/2$。

计算Holevo上界 $$ \chi=H\left(\frac{1\pm\cos\theta}{2}\right)\le 1\text{bit} $$

因此，对于不取等号的情况，不能用一个qubit传递1bit的信息。这个结论可以进行推广。

数学上有 $$ S(\rho)-\sum_x p_x S(\rho_x)\le H(X) $$

因此，如果将$n$ bit的信息$X$编码在$n$个qubit上，那么POVM测量后可以得到的关于$X$的信息为： $$ I_{acc}(\mathcal{E})\le\chi\le H(X)= n\ \text{bit} $$

等号成立的情况是比较特殊的，对于大部分情况，等号是不成立的。因此，不能用$n$个qubit传递$n$ bit的信息。

关于用$n$个qubit编码$m$ bit的二元序列，Nayek有一个描述解码正确概率的公式： $$ \mathrm{P}(X=Y)\le\frac{2^n}{2^m} $$

同样可以解释为什么不能用$n$个qubit传递$n$ bit的信息。

证明参考UCB的讲义：

https://people.eecs.berkeley.edu/~vazirani/s07quantum/notes/lec17/lec17.pdf

2. 信息论

熵率的定义：考虑一个长度为n的序列的熵，当n趋向无穷的极限即为熵率。 $$ H(\chi)\equiv\lim_{n\to\infty}\frac{1}{n}H(X_1,X_2,\dots,X_n) $$

2.1 Shannon’s noiseless channel coding theorem（无失真信源编码定理）

经典信息编码和解码的过程： $$ \fbox{$x_1\dots x_n$}\xrightarrow{C^n}\fbox{$x_1’\dots x_m’$}\xrightarrow{D^n}\fbox{$x_1’’\dots x_n’’$} $$

$C^n$将序列$x=(x_1,\dots,x_n)$映射为长度为$nR$的二元序列。$D^n$将长度为$nR$的二元序列映射为$x=(x_1’’,\dots,x_n’’)$。

考虑一个独立同分布信源$\{X_i\}$，其熵率为$H(X)$。则对于$R>H(X)$，存在可靠编码方式；对于$R<H(X)$，不存在可靠编码方式。

可靠的意思是指当序列长度趋向无穷以后，解码后的序列等于原始序列的概率趋向1： $$ \lim_{n\to\infty}\mathrm{P}\left(D^n(C^n(x))=x\right)=1 $$

2.2 Schumacher’s noiseless channel coding theorem

量子信息编码和解码的过程： $$ \fbox{$\rho$}\xrightarrow{\mathcal{C}^n}\fbox{$\rho’$}\xrightarrow{\mathcal{D}^n}\fbox{$\rho’’$} $$

$\mathcal{C}^n$将$H^{\otimes n}$中的态映射为$2^{nR}$维空间的一个态。$\mathcal{D}^n$将$2^{nR}$维空间的一个态映射为$H^{\otimes n}$中的态。

考虑一个独立同分布量子信源$\{H,\rho\}$。则对于$R>S(\rho)$，存在可靠编码方式；对于$R<S(\rho)$，不存在可靠编码方式。

可靠的意思是指当序列长度趋向无穷以后，原始序列和解码后的序列之间的保真度趋向1： $$ \lim_{n\to\infty}F(\rho^{\otimes n},\mathcal{D}^n\circ\mathcal{C}^n)=1 $$

2.3 Shannon’s noisy channel coding theorem

对于噪声信道$\mathcal{N}$，信道容量$C(\mathcal{N})$定义为每次使用信道时可以无错误地传输的最大信息量。 $$ C(\mathcal{N})=\max_{p(x)}I(X;Y) $$

2.4 Holevo-Schumacher-Westmoreland (HSW) theorem

假设编码函数将序列$x=(x_1,\dots,x_n)$映射为张量积形式的密度矩阵$\rho_1\otimes\rho_2\otimes\dots$，这种前提下的信道容量记为$C^{(1)}(\mathcal{E})$。假设$\mathcal{E}$具有保迹性。 $$ C^{(1)}(\mathcal{E})=\chi(\mathcal{E})\equiv\max_{\{p_j,\rho_j\}}\left[S\left(\mathcal{E}\left(\sum_j p_j \rho_j\right)\right)-\sum_j p_j S(\mathcal{E}(\rho_j))\right] $$

对于编码函数将经典信息编码为纠缠态的情况，猜测其信道容量的上限也为上式，但是还没有得到证明。

klucas 的个人网站

信息论