最小联合Tsallis信息熵问题算法研究

孙清扬,  胡海洋,  兰宗谕,  王颖喆

孙清扬, 胡海洋, 兰宗谕, 等. 最小联合Tsallis信息熵问题算法研究 [J]. 首都师范大学学报(自然科学版), 2025, 46(6): 26-33. DOI: 10.19789/j.1004-9398.2025.06.004
引用本文: 孙清扬, 胡海洋, 兰宗谕, 等. 最小联合Tsallis信息熵问题算法研究 [J]. 首都师范大学学报(自然科学版), 2025, 46(6): 26-33. DOI: 10.19789/j.1004-9398.2025.06.004
SUN Qingyang, HU Haiyang, LAN Zongyu, et al. An algorithm for minimum Tsallis entropy coupling [J]. Journal of Capital Normal University (Natural Science Edition), 2025, 46(6): 26-33. DOI: 10.19789/j.1004-9398.2025.06.004
Citation: SUN Qingyang, HU Haiyang, LAN Zongyu, et al. An algorithm for minimum Tsallis entropy coupling [J]. Journal of Capital Normal University (Natural Science Edition), 2025, 46(6): 26-33. DOI: 10.19789/j.1004-9398.2025.06.004

最小联合Tsallis信息熵问题算法研究

DOI: 10.19789/j.1004-9398.2025.06.004
基金项目: 

国家重点研发计划项目 2020YFA0712900;

国家自然科学基金项目 11871103;

国家级大学生创新创业项目 202210027020.

详细信息
    通讯作者:

    王颖喆, wangyz@bnu.edu.cn.

  • 中图分类号: O211.9; O236; O29; TP311.1

An algorithm for minimum Tsallis entropy coupling

  • 摘要: 在信息论领域,求解2个随机变量的最小联合信息熵是一个重要的开放问题。本文首次探讨了最小联合Tsallis信息熵问题及其理论性质,给出反例证明了无法将针对香农熵的近似算法推广到量子纠缠系统的Tsallis熵。针对此问题,创新地提出了一种基于供求匹配的贪心算法,并利用受控理论证明了所提出的新算法可以控制在所有系统中求解最小联合Tsallis熵问题的近似误差。

     

    Abstract: In the field of information theory, seeking the minimum entropy coupling of two random variables is an important open problem. This paper explores the minimum Tsallis entropy coupling problem and its theoretical properties for the first time. It provides counterexamples to demonstrate that the approximate algorithms for Shannon entropy cannot be extended to Tsallis entropy in quantum entangled systems. To tackle this problem, an innovative greedy algorithm based on supply-demand matching is proposed. Majorization theory is leveraged to prove that the proposed algorithm can control the approximation error in solving the minimum Tsallis entropy coupling problem across all systems.

     

  • 作为数据通信的重要研究对象,信息熵的研究始终是发展通信和信息传输的重中之重。该领域中的最小联合信息熵问题描述为:给定2个随机变量$ X$和$ Y$的分布,如何求解二者联合分布的最小信息熵$ H(X, Y)$?

    研究此问题的一个重要动机是对于香农极限的理论逼近。Shannon[1]在1948年提出,对于输入信号$ X$和输出信号$ Y$,互信息量$ I(X ; Y)$代表了在离散无记忆信道上有可能传输的信息的量度,而其信道容量(香农极限)则由关于所有输入分布的最大互信息量决定。一般地,根据$ H(X, Y)= H(X)+H(Y)-I(X ; Y)$,可知给定边缘分布时,最大化互信息量与最小化联合信息熵等价。此外,最小联合信息熵问题还广泛应用于因果推断与降维度量等领域,参见文献[2-5]。

    Roughgarden和Kearns[6]在2013年指出最小联合信息熵问题是一个开放问题;Kovačević等[7]进一步证明其为NP-难问题。因此近年来研究者们多致力于构造解决该问题的近似算法。对于最经典的香农熵,Kocaoglu等[8]提出了一种贪心算法,并证明该算法输出的近似解为局部极小点;Cicalese等[9]则通过构造一种不同的贪心机制用来分拆元素,将近似误差控制在1比特以内,并成功将算法推广至瑞利熵。

    然而已有算法并不能简单推广至全部信息熵,比如应用广泛的Tsallis信息熵。Tsallis[10]于1988年提出的Tsallis信息熵基于非广延统计的机制,可用于描述一维耗散系统和长程相互作用等复杂系统。近年来,国内外针对Tsallis熵的理论性质与应用展开了广泛研究,如文献[11-14]。然而针对最小联合Tsallis熵问题,无法简单推广已有算法进行解决。反例见2.1节。

    针对此问题,本文基于供求匹配的思想,通过改进文献[9]中算法的分拆机制,提出了解决最小联合Tsallis熵问题的贪心算法,并利用受控理论给出了新算法解决最小联合Tsallis熵问题的近似误差。

    本章给出需要用到的记号及Tsallis熵的定义。记2个离散型随机变量的概率分布为$ \boldsymbol{p}= \left(p_{1}, \cdots, p_{n}\right)$和$ \boldsymbol{q}=\left(q_{1}, \cdots, q_{m}\right)$,称$ n$和$ m$分别为2个随机变量的状态数。记$ \boldsymbol{M} \in \mathcal{C}(\boldsymbol{p}, \boldsymbol{q})$为以$ \boldsymbol{p}$和$ \boldsymbol{q}$为边缘分布的二元随机变量的联合分布矩阵,其中$ \mathcal{C}(\boldsymbol{p}, \boldsymbol{q})=\left\{\boldsymbol{M}=\left[m_{i j}\right]: \sum_{j} m_{i j}=p_{i}, \sum_{i} m_{i j}=q_{j}\right\}$。

    记$ \mathcal{P}_{n}:=\left\{\left(x_{1}, \cdots, x_{n}\right): \sum\limits_{i=1}^{n} x_{i}=1, x_{1} \geqslant x_{2} \geqslant \cdots \geqslant\right. \left.x_{n} \geqslant 0\right\}\left(n \in \mathbb{N}_{+}\right)$,即所有状态数为$ n$且各状态概率递减的一元离散型随机变量所构成的集合。以下均考虑边缘分布为$ \mathcal{P}_{n}$中元素的情形,因为信息熵对元素有排列不变性,而当2个分布不等长时,可在状态数少的末尾补0来对齐。对于$ \boldsymbol{p}, \boldsymbol{q} \in \mathcal{P}_{n}$,记$ \boldsymbol{p} \wedge \boldsymbol{q}:=\left(z_{1}, \cdots, z_{n}\right)$,其中$ z_{1}=\min \left\{p_{1}, q_{1}\right\}, z_{k}= \min \left\{\sum\limits_{j=1}^{k} p_{j}, \sum\limits_{j=1}^{k} q_{j}\right\}-\sum\limits_{j=1}^{k-1} z_{j}(k=2, \cdots, n)$。

    定义1.1(Tsallis熵)[10]   对$ \forall \alpha \geqslant 0$且$ \alpha \neq 1$,给定一元离散型随机变量$ \boldsymbol{p}=\left(p_{1}, \cdots, p_{n}\right)$,其Tsallis熵为

    $$ \begin{equation*} H_{\alpha}^{T}(\boldsymbol{p})=\frac{1}{1-\alpha}\left(\sum\limits_{i=1}^{n} p_{i}^{\alpha}-1\right), \end{equation*} $$ (1)

    其中$ \alpha$反映了系统的非广延程度。当$ \alpha \in(1, \infty)$时,称非遍历系统;当$ \alpha \in[0, 1)$时,称量子纠缠系统;当$ \alpha \rightarrow 1$时,Tsallis熵退化为经典的香农熵。对于一个二元随机变量而言,须先将联合分布矩阵中元素重排为一维概率分布向量,再通过式(1)计算Tsallis熵。

    本节将文献[9]中算法(下称算法A)推广到最小联合Tsallis熵问题中的反例。算法A可在多项式时间内给出$ \boldsymbol{M} \in \mathcal{C}(\boldsymbol{p}, \boldsymbol{q})$,使得针对香农熵的近似误差在1比特以内。然而下面的事实说明,对于$ \alpha \in[0, 1)$的量子纠缠系统而言,使用算法A解决最小联合Tsallis熵问题将不再奏效。具体反例构造见例2.1和2.2。

    事实2.1   存在$ \boldsymbol{p}, \boldsymbol{q} \in \mathcal{P}_{n}, \alpha \in[0, 1) $和$ \boldsymbol{N}_{0} \in \mathcal{C}(\boldsymbol{p}, \boldsymbol{q}) $,使得由算法A所给出的$ \boldsymbol{M}$有

    $$ H_{\alpha}^{T}(\boldsymbol{M})>H_{\alpha}^{T}\left(\boldsymbol{N}_{0}\right)+1 \text { 。 } $$

    例2.1   令2个边缘分布$ \boldsymbol{p}=(0.25, 0.25, 0.25, 0.25)$,$ \boldsymbol{q}=(0.375, 0.25, 0.25, 0.125)$,则存在联合分布矩阵$ \boldsymbol{N}_{4}$和由算法A给出的联合分布矩阵$ \boldsymbol{M}_{4}$,分别为

    $$ \begin{gathered} \boldsymbol{N}_{4}=\left(\begin{array}{cccc} 0.25 & 0 & 0 & 0 \\ 0 & 0.25 & 0 & 0 \\ 0 & 0 & 0.25 & 0 \\ 0.125 & 0 & 0 & 0.125 \end{array}\right), \\ \boldsymbol{M}_{4}=\left(\begin{array}{cccc} 0.25 & 0 & 0 & 0 \\ 0.125 & 0.125 & 0 & 0 \\ 0 & 0.125 & 0.125 & 0 \\ 0 & 0 & 0.125 & 0.125 \end{array}\right), \end{gathered} $$

    取$\alpha=0.1$,则由算法A所给出的近似最小联合Tsallis熵$H_{0.1}^{T}\left(\boldsymbol{M}_{4}\right)$约为$5.271, H_{0.1}^{T}\left(\boldsymbol{N}_{4}\right)$约为3.596,$H_{0.1}^{T}\left(\boldsymbol{M}_{4}\right) \geqslant H_{0.1}^{T}\left(\boldsymbol{N}_{4}\right)+1$,事实2.1成立。算法A在量子纠缠系统的最小联合Tsallis熵问题中失效。

    例2.2   对于一般的$n$为偶数,取$\boldsymbol{p}= \left(\frac{1}{n}, \frac{1}{n}, \cdots, \frac{1}{n}\right), \boldsymbol{q}=\left(\frac{3}{2 n}, \frac{1}{n}, \frac{1}{n}, \cdots, \frac{1}{n}, \frac{1}{2 n}\right)$,则算法A给出的近似最小联合Tsallis熵为

    $$ \begin{equation*} H_{\alpha}^{T}\left(\boldsymbol{M}_{n}\right)=\frac{1}{1-\alpha}\left[\left(\frac{1}{n}\right)^{\alpha}+(2 n-2)\left(\frac{1}{2 n}\right)^{\alpha}-1\right] 。 \end{equation*} $$ (2)

    可以类似例2.1构造出$ \boldsymbol{N}_{n} \in \mathcal{C}(\boldsymbol{p}, \boldsymbol{q})$,其Tsallis熵为

    $$ H_{\alpha}^{T}\left(\boldsymbol{N}_{n}\right)=\frac{1}{1-\alpha}\left[(n-1)\left(\frac{1}{n}\right)^{\alpha}+2\left(\frac{1}{2 n}\right)^{\alpha}-1\right]。 $$ (3)

    式(2和3)作差得

    $$ H_{\alpha}^{T}\left(\boldsymbol{M}_{n}\right)-H_{\alpha}^{T}\left(\boldsymbol{N}_{n}\right)=\frac{1}{1-\alpha}\left[\left(\frac{1}{2^{\alpha-1}}-1\right) \frac{n-2}{n^{\alpha}}\right]。 $$ (4)

    当$ \alpha \in[0, 1)$时,随$ n$增大,(4)式以$ O\left(n^{1-\alpha}\right)$的速度发散到无穷。这说明在量子纠缠系统中,算法A无法控制求解最小联合Tsallis熵问题的近似误差,因此需要提出新的算法进行求解。

    本文所提出的基于供求匹配的贪心算法(下称算法1)改进了文献[9]中分拆元素的策略,可以控制求解最小联合Tsallis熵问题的近似误差。命题与定理证明见第3章,算法流程及直观解释见第4章。下面首先给出命题2.1,为算法1的可行性提供理论保证。

    命题2.1   记$\boldsymbol{p}=\left(p_{1}, \cdots, p_{n}\right), \boldsymbol{q}=\left(q_{1}, \cdots, q_{n}\right) \in \mathcal{P}_{n}$,$\boldsymbol{z}=\boldsymbol{p} \wedge \boldsymbol{q}=\left(z_{1}, \cdots, z_{n}\right), \boldsymbol{r}_{p}=\boldsymbol{z}-\boldsymbol{p}=\left(r_{p 1}, \cdots, r_{p n}\right)$, $\boldsymbol{r}_{q}=\boldsymbol{z}-\boldsymbol{q}=\left(r_{q 1}, \cdots, r_{q n}\right)$,则对$\forall i \in[n]$,存在不交的2个集合$D_{p i}$和$D_{q i} \subseteq[n] \backslash[i]$,以及$0 \leqslant x_{p i}, x_{q i} \leqslant z_{i}$(令$x_{p 1}=x_{q 1}=0$),使得$\bigcap_{i=1}^{n} D_{p i}=\bigcap_{i=1}^{n} D_{q i}=\phi$,且

    $$ r_{p i}=x_{p i}-\sum\limits_{j \in D_{p i}} x_{p j}, $$ (5)
    $$ r_{q i}=x_{q i}-\sum\limits_{j \in D_{q i}} x_{q j } 。 $$ (6)

    同时$D_{p i}, D_{q i}, x_{p i}$和$x_{q i}$可在$O(n)$时间给出,见算法1的MATCH函数。

    下面的定理2.1和定理2.2给出了最小联合Tsallis熵的上界与下界,进而给出了算法1的近似误差。

    定理2.1   对于$\forall \boldsymbol{p}, \boldsymbol{q} \in \mathcal{P}_{n}, \alpha \in(1, \infty) $,可以得到

    $$ H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q}) \leqslant \min\limits_{\mathbf{N} \in \mathcal{C}(\boldsymbol{p}, \boldsymbol{q})} H_{\alpha}^{T}(\boldsymbol{N}) \leqslant 2^{1-\alpha} H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+\frac{2^{1-\alpha}-1}{1-\alpha} 。 $$ (7)

    即算法1求非遍历系统最小联合Tsallis信息熵问题的近似误差为$ \left(2^{1-\alpha}-1\right)\left[H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+1 /(1-\alpha)\right]$。

    定理2.2   对于$\forall \boldsymbol{p}, \boldsymbol{q} \in \mathcal{P}_{n}, \alpha \in(0, 1)$,可以得到

    $$ H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q}) \leqslant \min\limits_{\mathbf{N} \in \mathcal{C}(\boldsymbol{p}, \boldsymbol{q})} H_{\alpha}^{T}(\boldsymbol{N}) \leqslant H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+\frac{2^{1-\alpha}-1}{1-\alpha} s^{1-\alpha}, $$ (8)

    其中$s=\left\|\boldsymbol{x}_{p}\right\|_{0}+\left\|\boldsymbol{x}_{q}\right\|_{0} \leqslant n-1, \boldsymbol{x}_{p}=\left(x_{p 1}, \cdots, x_{p n}\right)$和$\boldsymbol{x}_{q}=\left(x_{q 1}, \cdots, x_{q n}\right)$由命题2.1给出。

    即算法1求量子纠缠系统最小联合Tsallis信息熵问题的近似误差为$ \left(2^{1-\alpha}-1\right) s^{1-\alpha} /(1-\alpha)$。

    对$\forall i \in[n]$,首先针对边缘$\boldsymbol{p}$,在$O(n)$时间中归纳地给出满足要求的$D_{p i}$和$x_{p i}$,然后针对边缘$\boldsymbol{q}$同理得到$D_{q i}$和$x_{q i}$,再证明$D_{p i} \cap D_{q i}=\phi$即可。为此需要先给出控制关系的定义。

    定义3.1(控制关系)[15]   给定2个随机变量$\boldsymbol{x}, \boldsymbol{y} \in \mathcal{P}_{n}$,定义$\mathcal{P}_{n}$上的一个二元关系$\leqslant$:记$\boldsymbol{x} \leqslant \boldsymbol{y}$,若$\sum_{k=1}^{i} x_{k} \leqslant \sum_{k=1}^{i} y_{k}, \forall i \in\{1, \cdots, n\}$。此时称$\boldsymbol{y}$控制$\boldsymbol{x}$,或$\boldsymbol{x}$被$\boldsymbol{y}$控制。

    易证($\mathcal{P}_{n}, \leqslant$)是一个$\mathcal{P}_{n}$上的偏序关系,且构成一个格[16]。因此对$\boldsymbol{p}, \boldsymbol{q} \in \mathcal{P}_{n}$存在唯一的最大下界。文献[16]进一步指出该最大下界就是$\boldsymbol{p} \wedge \boldsymbol{q}$,即对于任意$\boldsymbol{p}, \boldsymbol{q} \in \mathcal{P}_{n}$,有$\boldsymbol{p} \wedge \boldsymbol{q} \leqslant \boldsymbol{p}$且$\boldsymbol{p} \wedge \boldsymbol{q} \leqslant \boldsymbol{q}$,并对所有$\boldsymbol{z} \in \mathcal{P}_{n}$满足$\boldsymbol{z} \leqslant \boldsymbol{p}$且$\boldsymbol{z} \leqslant \boldsymbol{q}$,有$\boldsymbol{z} \leqslant \boldsymbol{p} \wedge \boldsymbol{q}$。

    令$D_{p n}=\phi$,由$\boldsymbol{p} \wedge \boldsymbol{q} \leqslant \boldsymbol{p}$知$x_{p n}=r_{p n} \geqslant 0$成立。假设对于$i+1 \in[n] \backslash\{1\}$,已经定义好一列两两不相交的集合$D_{p i+1}, \cdots, D_{p n}$和一列非负实数$x_{p i+1}, \cdots, x_{p n}$,满足任意$i^{\prime} \in[n] \backslash[i]$,有$D_{p i} \subseteq[n] \backslash$ [$i^{\prime}$]且

    $$ r_{p i^{\prime}}=x_{p i^{\prime}}-\sum\limits_{j \in D_{p i^{\prime}}} x_{p j } 。 $$ (9)

    下面定义$D_{p i}$和$x_{p i}$。令

    $$ D_{p i}=S \backslash \bigcup\limits_{k=i+1}^{n} D_{p k}, $$ (10)

    其中$S \subseteq[n] \backslash[i]$且所含元素均为正数,使得$r_{p i}+ \sum_{j \in S_{p i}} x_{p j} \geqslant 0$。下面论证集合$S$的存在性。注意到

    $$ \begin{align*} \sum\limits_{j \in\{i+1, \cdots, n\} \backslash \bigcup\limits_{k=i+1}^n D_{p k}} x_{p j} & =\sum\limits_{j=i+1}^{n} x_{p j}-\sum\limits_{k=i+1}^{n} \sum\limits_{j \in D_{p k}} x_{p j}= \\ \sum\limits_{j=i+1}^{n} x_{p j} & -\sum\limits_{j=i+1}^{n}\left(x_{p j}-r_{p j}\right)= \\ \sum\limits_{j=i+1}^{n} r_{p j} & =\sum\limits_{j=i}^{n} r_{p j}-r_{p i} \geqslant-r_{p i} , \end{align*} $$ (11)

    其中第2行的等号和第4行的不等号均可由式(9)得到。集合$S$的存在性得证。构造集合$D_{p i}$时,只需要从集合$[n] \backslash \cup_{k=i+1}^{n} D_{p k}$中从大到小将元素加入集合$D_{p i}$中,直到$r_{p i}+\sum_{j \in D_{p i}} x_{p j} \geqslant 0$,再取$x_{p i}= r_{p i}+\sum_{j \in D_{p i}} x_{p j}$即可。注意这个过程可在至多$O(n)$时间内完成,细节详见算法1的MATCH函数。

    仿照上述过程,同理可得$D_{q i}$和$x_{q i}$,下面只须证明$D_{p i} \cap D_{q i}=\phi_{\circ}$断言$z_{i} \in\left[\min \left\{p_{i}, q_{i}\right\}, \max \left\{p_{i}, q_{i}\right\}\right]$。事实上,不妨设$p_{i}<q_{i}$,则若$z_{i}<\min \left\{p_{i}, q_{i}\right\}=p_{i}$有

    $$ \begin{gather*} \sum\limits_{j=1}^{i-1} z_{j}=\sum\limits_{j=1}^{i} z_{j}-z_{i}=\min \left\{\sum\limits_{j=1}^{i} p_{j}, \sum\limits_{j=1}^{i} q_{j}\right\}-z_{i}> \\ \min \left\{\sum\limits_{j=1}^{i} p_{j}, \sum\limits_{j=1}^{i} q_{j}\right\}-p_{i}= \\ \min \left\{\sum\limits_{j=1}^{i-1} p_{j}, \sum\limits_{j=1}^{i-1} q_{j}+\left(q_{i}-p_{i}\right)\right\} 。 \end{gather*} $$ (12)

    然而

    $$ \sum\limits_{j=1}^{i-1} z_{j}=\min \left\{\sum\limits_{j=1}^{i-1} p_{j}, \sum\limits_{j=1}^{i-1} q_{j}\right\} \leqslant \min \left\{\sum\limits_{j=1}^{i-1} p_{j}, \sum\limits_{j=1}^{i-1} q_{j}+\left(q_{i}-p_{i}\right)\right\}, $$ (13)

    矛盾。故$z_{i} \geqslant \min \left\{p_{i}, q_{i}\right\}$。类似可证$z_{i} \leqslant \max \left\{p_{i}, q_{i}\right\}$。故$r_{p i}$和$r_{q i}$不会同时$<0$,因此至少可以令集合$D_{p i}$和$D_{q i}$中的一个为空集,另一个用算法1的MATCH函数求解,$D_{p i} \cap D_{q i}=\phi$成立。命题2.1证毕。

    首先对$\forall \boldsymbol{N} \in \mathcal{C}(\boldsymbol{p}, \boldsymbol{q})$和$\forall \alpha \geqslant 0$且$\alpha \neq 1$,证明$H_{\alpha}^{T}(\boldsymbol{N}) \geqslant H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})$成立,然后说明由算法1给出的联合分布矩阵$\tilde{\boldsymbol{M}}$满足$H_{\alpha}^{T}(\tilde{\boldsymbol{M}}) \leqslant 2^{1-\alpha} H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+ \left(2^{1-\alpha}-1\right) /(1-\alpha)$。为此先给出需要用到的概念和引理。

    定义3.2(聚合体)[8]   给定$\boldsymbol{x}=\left(x_{1}, \cdots, x_{n}\right) \in \mathcal{P}_{n}$,称$\boldsymbol{y}=\left(y_{1}, y_{2}, \cdots, y_{m}\right) \in \mathcal{P}_{m}(2 \leqslant m<n)$为$\boldsymbol{x}$的一个聚合体,若存在$1, \cdots, n$的一个不相交的划分指标集$I_{1}, \cdots, I_{m}$,使得$y_{j}=\sum_{i \in I_{j}} x_{i}, j=1, \cdots, m$。

    聚合体的概念与$\left(\mathcal{P}_{n}, \leqslant\right)$之间存在联系。令$\boldsymbol{y}$为$\boldsymbol{x}$的一个聚合体,则有$\boldsymbol{x} \leqslant \boldsymbol{y}$。证明详见文献[17]。

    引理3.1(Tsallis熵的Schur凹性)[18]   $\forall \alpha \geqslant 0$且$\alpha \neq 1$,对$\forall \boldsymbol{x}, \boldsymbol{y} \in \mathcal{P}_{n}$,满足$\boldsymbol{x} \leqslant \boldsymbol{y}$,记$H_{\alpha}^{T}$为非广延程度为$\alpha$的Tsallis熵,则有$H_{\alpha}^{T}(\boldsymbol{x}) \geqslant H_{\alpha}^{T}(\boldsymbol{y})$,当且仅当$x=y$时等号成立。

    根据聚合体的概念,可知$\forall \boldsymbol{N} \in \mathcal{C}(\boldsymbol{p}, \boldsymbol{q})$,将$\boldsymbol{N}$中元素重排为长度为$n^{2}$的一维概率分布向量$\boldsymbol{n}$,则$\boldsymbol{p}$与$\boldsymbol{q}$均为$\boldsymbol{n}$的聚合体,于是$\boldsymbol{n} \leqslant \boldsymbol{p}$且$\boldsymbol{n} \leqslant \boldsymbol{q}$,故$\boldsymbol{n} \leqslant \boldsymbol{p} \wedge \boldsymbol{q}$。又根据Tsallis熵的Schur凹性可知,对$\forall \mathbf{N} \in \mathcal{C}(\boldsymbol{p}, \boldsymbol{q})$和$\forall \alpha \geqslant 0$且$\alpha \neq 1$,有$H_{\alpha}^{T}(\boldsymbol{N})= H_{\alpha}^{T}(\boldsymbol{n}) \geqslant H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})$成立。

    下证由算法1给出的联合分布矩阵$\boldsymbol{M}$满足$H_{\alpha}^{T}(\tilde{\boldsymbol{M}}) \leqslant H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+1$。类似于文献[9],可以将$\tilde{\boldsymbol{M}}$中的非零元$z_{j}$划分为$n$对$z_{j}^{(r)}$与$z_{j}^{(d)}$,其中$z_{j}^{(r)}+ z_{j}^{(d)}=z_{j}, j=1, 2, \cdots, n$,则有

    $$ \begin{gather*} H_{\alpha}^{T}(\tilde{\boldsymbol{M}})=\frac{1}{1-\alpha}\left[\sum\limits_{j=1}^{n}\left(z_{j}^{(r)}\right)^{\alpha}+\sum\limits_{j=1}^{n}\left(z_{j}^{(d)}\right)^{\alpha}-1\right]= \\ \frac{1}{1-\alpha}\left\{2 *\left[\frac{1}{2} \sum\limits_{j=1}^{n}\left(z_{j}^{(r)}\right)^{\alpha}+\frac{1}{2} \sum\limits_{j=1}^{n}\left(z_{j}^{(d)}\right)^{\alpha}\right]-1\right\} \leqslant \\ \frac{1}{1-\alpha}\left[2 * \sum\limits_{j=1}^{n}\left(\frac{z_{j}}{2}\right)^{\alpha}-1\right]= \\ \frac{1}{1-\alpha}\left[2^{1-\alpha } *\sum\limits_{j=1}^{n} z_{j}{ }^{\alpha}-2^{1-\alpha}+\left(2^{1-\alpha}-1\right)\right]= \\ \frac{2^{1-\alpha}}{1-\alpha}\left(\sum\limits_{j=1}^{n} z_{j}{ }^{\alpha}-1\right)+\frac{2^{1-\alpha}-1}{1-\alpha}= \\ 2^{1-\alpha} H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+\frac{2^{1-\alpha}-1}{1-\alpha} , \end{gather*} $$ (14)

    其中第3行的不等号是对$x^{\alpha}$使用Jensen不等式得到,又因为$1 /(1-\alpha)<0$,故不等号反向。定理2.1证毕。

    证明分为2步进行。首先给出算法1求解量子纠缠系统中最小联合Tsallis熵问题的近似误差,然后说明$ \boldsymbol{p} \wedge \boldsymbol{q}$中每个元素至多被分拆一次,从而该近似误差可控。为此先给出Tsallis熵的广义香农可加性。

    引理3.2(Tsallis熵的广义香农可加性)[19]   对于$\forall \alpha \geqslant 0$且$\alpha \neq 1$,记$H_{\alpha}^{T}$为非广延程度为$\alpha$的Tsallis熵,$p_{i j} \geqslant 0, p_{i}=\sum_{j=1}^{m_{i}} p_{i j}\left(i \in[n], j \in\left[m_{i}\right]\right)$,有

    $$ \begin{gather*} H_{\alpha}^{T}\left(p_{11}, \cdots, p_{n m_{n}}\right)=H_{\alpha}^{T}\left(p_{1}, \cdots, p_{n}\right)+ \\ \sum\limits_{i=1}^{n} p_{i}^{\alpha} H_{\alpha}^{T}\left(\frac{p_{i 1}}{p_{i}}, \cdots, \frac{p_{i m_{i}}}{p_{i}}\right) 。 \end{gather*} $$ (15)

    记对角线中被分拆元素的编号所构成的集合为$I \subseteq[n]$,则有$|I|=S$。将算法1输出的$\tilde{\boldsymbol{M}}$中的被分拆的非零元素重组成$s$对$z_{j}^{(r)}$和$z_{j}^{(d)}$满足$z_{j}^{(r)}+z_{j}^{(d)}=z_{j}(j \in I)$。根据Tsallis熵的广义香农可加性,有

    $$ \begin{gather*} H_{\alpha}^{T}(\tilde{\boldsymbol{M}})=H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+\sum\limits_{j \in I} z_{j}^{\alpha} H_{\alpha}^{T}\left(\frac{z_{j}^{(r)}}{z_{j}}, \frac{z_{j}^{(d)}}{z_{j}}\right)= \\ H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+\sum\limits_{j \in I} \frac{z_{j}^{\alpha}}{1-\alpha}\left[\left(\frac{z_{j}^{(r)}}{z_{j}}\right)^{\alpha}+\left(\frac{z_{j}^{(d)}}{z_{j}}\right)^{\alpha}-1\right]= \\ H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+\frac{1}{1-\alpha} \sum\limits_{j \in I}\left[\left(z_{j}^{(r)}\right)^{\alpha}+\left(z_{j}^{(d)}\right)^{\alpha}-z_{j}^{\alpha}\right] \leqslant \\ H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+\frac{1}{1-\alpha} \sum\limits_{j \in I}\left[2 *\left(\frac{z_{j}}{2}\right)^{\alpha}-z_{j}^{\alpha}\right]= \\ H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+\frac{2^{1-\alpha}-1}{1-\alpha} \sum\limits_{j \in I} z_{j}^{\alpha} \leqslant \\ H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+\frac{2^{1-\alpha}-1}{1-\alpha} s\left(\frac{\sum\nolimits_{j \in I} z_{j}}{s}\right)^{\alpha} \leqslant \\ H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})+\frac{2^{1-\alpha}-1}{1-\alpha} s^{1-\alpha}, \end{gather*} $$ (16)

    式中:第4和6行的不等号是对$x^{\alpha}$使用Jensen不等式得到;第7行的不等号是因为$\sum_{j \in I} z_{j} \in[0, 1]$。

    又根据$\forall \boldsymbol{N} \in \mathcal{C}(\boldsymbol{p}, \boldsymbol{q})$和$\forall \alpha \geqslant 0$且$\alpha \neq 1$,有$H_{\alpha}^{T}(\boldsymbol{N}) \geqslant H_{\alpha}^{T}(\boldsymbol{p} \wedge \boldsymbol{q})$成立。因此算法1求解量子纠缠系统的最小联合Tsallis信息熵问题时的近似误差为$\left(2^{1-\alpha}-1\right) s^{1-\alpha} /(1-\alpha)$。

    下面说明算法1将$\boldsymbol{p} \wedge \boldsymbol{q}$中的每个元素至多分拆一次,即对算法1最终输出的辅助向量$\boldsymbol{x}_{p}$和$\boldsymbol{x}_{q}$而言,有$\forall i \in[n]$,$\min \left\{x_{p i}, x_{q i}\right\}=0$成立。类似于文献[20]中定理11,根据命题2.1可知,对$\forall i \in[n]$,存在不相交的2个集合$D_{p i}$和$D_{q i} \subseteq[n] \backslash [i]$,及$0 \leqslant x_{p i}, x_{q i} \leqslant z_{i}$(令$x_{p 1}=x_{q 1}=0$),使得$\bigcap_{i=1}^{n} D_{p i}=\bigcap_{i=1}^{n} D_{q i}=\phi$,且

    $$ r_{p i}=x_{p i}-\sum\limits_{j \in D_{p i}} x_{p j}, $$ (17)
    $$ r_{q i}=x_{q i}-\sum\limits_{j \in D_{q i}} x_{q j }。 $$ (18)

    固定$i \in[n] \backslash\{1\}$,不妨设$\sum_{k=1}^{i-1} p_{k} \leqslant \sum_{k=1}^{i-1} q_{k}$,则有

    $$ \sum\limits_{k=1}^{i-1} z_k=\min \left\{\sum\limits_{k=1}^{i-1} p_k, \sum\limits_{k=1}^{i-1} q_k\right\}=\sum\limits_{k=1}^{i-1} p_k \circ $$ (19)

    又由$\forall j \in D_{p i}, j>i$知

    $$ \begin{array}{r} 0=\sum\limits_{k=1}^{i-1}\left(p_{k}-z_{k}\right)=\sum\limits_{k=1}^{i-1}\left(\sum\limits_{j \in D_{p k}} x_{p j}-x_{p k}\right)= \\ \sum\limits_{k=1}^{i-1} \sum\limits_{j \in D_{p k}} x_{p j}-\sum\limits_{k=1}^{i-1} x_{p k}=\sum\limits_{k=1}^{i-1} \sum\limits_{j \geqslant i: j \in D_{p k}} x_{p j} \geqslant x_{p i \circ} \end{array} $$ (20)

    再根据$x_{p i}, x_{q i} \geqslant 0$,知min $\left\{x_{p i}, x_{q i}\right\}=x_{p i}=0$。该结果说明$\boldsymbol{p} \wedge \boldsymbol{q}$中的每个元素至多被分拆一次,因此$\boldsymbol{x}_{p}$和$\boldsymbol{x}_{q}$中非零元素个数$s=\left\|\boldsymbol{x}_{p}\right\|_{0}+\left\|\boldsymbol{x}_{q}\right\|_{0} \leqslant n-1$。定理2.2证毕。

    表  算法1  最小联合信息熵供求匹配算法
    输人: 概率分布$\boldsymbol{p}=\left(p_{1}, p_{2}, \cdots, p_{n}\right)$和$\boldsymbol{q}=\left(q_{1}, q_{2}, \cdots, q_{n}\right)$。
    输出: 1个$n \times n$的矩阵$\tilde{\boldsymbol{M}}=\left[m_{i j}\right]$, 使得$\sum_{j} m_{i j}=p_{i}$且$\sum_{i} m_{i j}=q_{j}$。
    2个辅助向量$\boldsymbol{x}_{\boldsymbol{p}}$和$\boldsymbol{x}_{\boldsymbol{q}}$。
    for $i=1, \cdots, n$ and $j=1, \cdots, n$ set $m_{i j} \leftarrow 0$
    if $\boldsymbol{p} \neq \boldsymbol{q}$, let $i=\max \left\{j \mid p_{j} \neq q_{j}\right\}$; if $p_{i}<q_{i}$ swap $\boldsymbol{p} \leftrightarrow \boldsymbol{q}$
    $z=\left(z_{1}, \cdots, z_{n}\right) \longleftarrow \boldsymbol{p} \wedge \boldsymbol{q}, \boldsymbol{r}_{p}=\left(r_{p 1}, \cdots, r_{p n}\right) \longleftarrow z-\boldsymbol{p}, \boldsymbol{r}_{\boldsymbol{q}}=\left(r_{q 1}, \cdots, r_{q n}\right) \longleftarrow z-\boldsymbol{q}$
    set $m_{i i} \leftarrow z_{i}$ for $i=1, \cdots, n$
    $S_{p} \leftarrow \phi, S_{q} \leftarrow \phi, \boldsymbol{x}_{p}=\left(x_{p 1}, \cdots, x_{p n}\right) \leftarrow \boldsymbol{r}_{p}, \boldsymbol{x}_{q}=\left(x_{q 1}, \cdots, x_{q n}\right) \leftarrow \boldsymbol{r}_{q}$
    $i \leftarrow n$
    while $i \geqslant 1$ do
        if $r_{p i}>0$ then
            $S_{p} \leftarrow S_{p} \cup\{i\}, m_{i i} \leftarrow p_{i}$
        end if
        else if $r_{p i}<0$ then
            $\left(D_{p i}, S_{p}, \boldsymbol{x}_{p}\right) \leftarrow \operatorname{MATCH}\left(i, S_{p}, \boldsymbol{x}_{p}\right)$
            for $\left(k, d_{k}\right)$ in $D_{p i}$ do $m_{i k} \leftarrow d_{k}$
        end else if
        if $r_{q i}>0$ then
            $S_{q} \leftarrow S_{q} \cup\{i\}, m_{i i} \leftarrow q_{i}$
        end if
        else if $r_{q i}<0$ then
            $\left(D_{q i}, S_{q}, \boldsymbol{x}_{q}\right) \leftarrow \operatorname{MATCH}\left(i, S_{q}, \boldsymbol{x}_{q}\right)$
            for $\left(k, d_{k}\right)$ in $D_{q i}$ do $m_{k i} \leftarrow d_{k}$
        end else if
        $i \leftarrow i-1$
    end while
    $\operatorname{match}(i, S, \boldsymbol{x})$
    $D_{i} \leftarrow \phi$
    for $k$ in $S$ do
        if $x_{i}<0$ then
            $x_{i} \leftarrow x_{i}+x_{k}, S \leftarrow S \backslash\{k\}, D_{i} \leftarrow D_{i} \cup\left\{\left(k, x_{k}\right)\right\}$
        end if
        else break
    end for
    if $x_{i}>0$ then $S \leftarrow S \cup\{i\}$
    return $\left(D_{i}, S, \boldsymbol{x}\right)$

    该算法可以从供求匹配的角度给出一个直观解释。称上述$\boldsymbol{r}_{p}$为$\boldsymbol{z}$相对于$\boldsymbol{p}$的供求向量,当$r_{p i}>0$时称$z_{i}$相对于$\boldsymbol{p}$为供给端,当$r_{p i}<0$时称$z_{i}$相对于$\boldsymbol{p}$为需求端,其中供给或需求量为$\left|r_{p i}\right| 。 \boldsymbol{z}$相对于$\boldsymbol{q}$的供求向量$\boldsymbol{r}_{q}$含义同理。算法分拆对角线上元素的过程可以看作$\boldsymbol{z}$相对于$\boldsymbol{p}$和$\boldsymbol{q}$进行供求匹配。具体叙述如下。

    文献[9]中算法A中的分拆策略是“供给侧导向”的。从联合分布矩阵的右下角向左上角开始迭代,当第$ i$行或列有供给时,将其放置在第$ i-1$行或列中。算法A虽能保证迭代过的行列均满足边缘分布要求,但是会造成原本不是需求端的行或列产生多余供给,造成不必要的元素分拆,从而导致信息熵增加。

    算法1中的分拆策略则是"需求侧导向"的。首先计算$\boldsymbol{z}$相对于$\boldsymbol{p}$和$\boldsymbol{q}$的供求向量,定位需求端和供给端。随后从联合分布矩阵的右下角向左上角依次判断对角线元素的供求情况。若位置$(i, i)$的元素相对于$\boldsymbol{p}$产生供给,则将编号$i$纳入供给集$S_{p}$;若其相对于$\boldsymbol{p}$有需求,则通过MATCH函数从供给集$S_{p}$中不断调动元素到该行,直至完全满足其需求,并将调动元素的编号和大小记录在需求集$D_{p i}$中。同时若调动后有超过需求的部分,则同样将其编号$i$纳入供给集$S_{p}$中。元素关于$\boldsymbol{q}$的操作同理。与算法A相比,MATCH函数跳过了所有已经供求平衡的元素,实现了供求的精准匹配。命题2.1保证MATCH函数应用于每个需求端元素时,当前迭代步供给集中的元素均能够完全满足其需求。同时,每个对角线上的元素不会同时相对于$\boldsymbol{p}$和$\boldsymbol{q}$有需求,避免了重复分拆。

    算法A和算法1中分别应用于例2.1时对于对角线上$\boldsymbol{p} \wedge \boldsymbol{q}$中元素的分拆过程如图 1所示。回忆例2.1中$\boldsymbol{p}=\boldsymbol{p} \wedge \boldsymbol{q}=(0.25, 0.25, 0.25, 0.25), \boldsymbol{q}=$($0.375, 0.25, 0.25, 0.125$)。算法A的分拆策略如图 1(a)所示,从右至左依次分拆$\boldsymbol{p} \wedge \boldsymbol{q}$中各元素以满足$\boldsymbol{q}$的要求,造成中间2个原本供求平衡的元素产生不必要的分拆,导致信息熵增加。而算法1的分拆策略如图 1(b)所示,首先计算了$\boldsymbol{p} \wedge \boldsymbol{q}$相对于$\boldsymbol{q}$的供求向量,第1个元素需要$1 / 8$第4个元素可以供给$1 / 8$,其余元素供求平衡。因此只需将第4个元素的供给与第1个元素的需求相匹配即可。显然,由算法1所得到的信息熵小于算法A。下面的例子直观展示了算法1的操作流程。

    图  1  2种分拆策略分别应用于例2.1(a)算法A; (b)算法1
    下载: 全尺寸图片

    例4.1   令$\boldsymbol{p}=(0.4, 0.3, 0.15, 0.08, 0.04, 0.03)$,$\boldsymbol{q}=(0.44, 0.18, 0.18, 0.15, 0.03, 0.02)$,可得$\boldsymbol{z}=\boldsymbol{p} \wedge \boldsymbol{q}=$($0.4, 0.22, 0.18, 0.13, 0.04, 0.03$),并将元素置于矩阵$\tilde{\boldsymbol{M}}_{z}$对角线上,$\tilde{\boldsymbol{M}}_{z}$其余元素置零。计算$z$相对于$\boldsymbol{p}$和$\boldsymbol{q}$的供求向量分别为$\boldsymbol{r}_{p}=\boldsymbol{z}-\boldsymbol{p}=(0, -0.08$,$0.03, 0.05, 0, 0)$和$\boldsymbol{r}_{q}=\boldsymbol{z}-\boldsymbol{q}=(-0.04, 0.04, 0$,$-0.02, 0.01, 0.01)$,并令$\boldsymbol{x}_{p}=\boldsymbol{r}_{p}, \boldsymbol{x}_{q}=\boldsymbol{r}_{q}$,供给集$S_{p}= S_{q}=\phi$。

    在第1次迭代中,处理$\tilde{\boldsymbol{M}}_{z}$矩阵$(6, 6)$位置的元素$z_{6}=0.03$,其相对于$\boldsymbol{p}$供求平衡,而相对于$\boldsymbol{q}$可以提供0.01供给。于是令$S_{q}=S_{q} \cup\{6\}=\{6\}$,然后令$m_{66}=q_{6}=0.02$,得到矩阵$\tilde{\boldsymbol{M}}^{(6)}$。

    $$ \begin{gathered} \tilde{\boldsymbol{M}}_{z}=\left(\begin{array}{cccccc} 0.4 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.22 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.18 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.13 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.04 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.03 \end{array}\right), \\ S_{p}=S_{q}=\phi, \\ \boldsymbol{x}_{p}=(0, -0.08, 0.03, 0.05, 0, 0), \\ \boldsymbol{x}_{q}=(-0.04, 0.04, 0, -0.02, 0.01, 0.01), \\ \tilde{\boldsymbol{M}}^{(6)}=\left(\begin{array}{cccccc} 0.4 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.22 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.18 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.13 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.04 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.02 \end{array}\right), \end{gathered} $$
    $$ S_p=\phi, S_q=\{6\}, $$
    $$ \boldsymbol{x}_{p}=(0, -0.08, 0.03, 0.05, 0, 0), $$
    $$ \boldsymbol{x}_{q}=(-0.04, 0.04, 0, -0.02, 0.01, 0.01)。 $$

    在第2次迭代中,处理$\tilde{\boldsymbol{M}}^{(6)}$矩阵$(5, 5)$位置的元素$z_{5}=0.04$,其相对于$\boldsymbol{p}$供求平衡,而相对于$\boldsymbol{q}$有0.01的供给。于是令$S_{q}=S_{q} \cup\{5\}=\{5, 6\}$,然后令$m_{55}=q_{5}=0.03$,得到矩阵$\tilde{\boldsymbol{M}}^{(5)}$。

    $$ \begin{gathered} \tilde{\boldsymbol{M}}^{(6)}=\left(\begin{array}{cccccc} 0.4 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.22 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.18 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.13 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.04 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.02 \end{array}\right), \\ S_p=\phi, S_q=\{6\}, \\ \boldsymbol{x}_p=(0,-0.08,0.03,0.05,0,0), \\ \boldsymbol{x}_q=(-0.04,0.04,0,-0.02,0.01,0.01 ), \\ \tilde{\boldsymbol{M}}^{(5)}=\left(\begin{array}{cccccc} 0.4 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.22 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.18 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.13 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.03 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.02 \end{array}\right), \\ S_p=\phi, S_q=\{5,6\}, \\ \boldsymbol{x}_p=(0,-0.08,0.03,0.05,0,0), \\ \boldsymbol{x}_q=(-0.04,0.04,0,-0.02,0.01,0.01)。 \end{gathered} $$

    在第3次迭代中,处理$\tilde{\boldsymbol{M}}^{(5)}$矩阵$(4, 4)$位置的元素$z_{4}=0.13$,其相对于$\boldsymbol{p}$可以提供0.05的供给,而相对于$\boldsymbol{q}$有0.02的需求。于是令$S_{p}= S_{p} \cup\{4\}=\{4\}$,然后令$m_{44}=p_{4}=0.08$。随后用MATCH函数实现$z_{4}$相对于$\boldsymbol{q}$的供求匹配,求得$D_{q 4}=\{(5, 0.01), (6, 0.01)\}, S_{q}=S_{q} \backslash\{5, 6\}=\phi$和$x_{q 4}=0$,令$m_{54}=m_{64}=0.01$,得到矩阵$\tilde{\boldsymbol{M}}^{(4)}$。

    $$ \begin{gathered} \tilde{\boldsymbol{M}}^{(5)}=\left(\begin{array}{cccccc} 0.4 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.22 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.18 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.13 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.03 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.02 \end{array}\right), \\ S_p=\phi, S_q=\{5,6\}, \\ \boldsymbol{x}_p=(0,-0.08,0.03,0.05,0,0), \\ \boldsymbol{x}_q=(-0.04,0.04,0,-0.02,0.01,0.01), \\ \tilde{\boldsymbol{M}}^{(4)}=\left(\begin{array}{cccccc} 0.4 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.22 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.18 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.08 & 0 & 0 \\ 0 & 0 & 0 & 0.01 & 0.03 & 0 \\ 0 & 0 & 0 & 0.01 & 0 & 0.02 \end{array}\right), \\ S_p=\{4\}, S_q=\phi, \\ \boldsymbol{x}_p=(0,-0.08,0.03,0.05,0,0), \\ \boldsymbol{x}_q=(-0.04,0.04,0,0,0.01,0.01)。 \end{gathered} $$

    类似可以得到$\tilde{\boldsymbol{M}}^{(3)}$和$\tilde{\boldsymbol{M}}^{(2)}$。在最后的第6次迭代,处理$\tilde{\boldsymbol{M}}^{(2)}$矩阵$(1, 1)$位置的元素$z_{1}=0.4$,其相对于$\boldsymbol{p}$供求平衡,而相对于$\boldsymbol{q}$有0.04的需求。于是用MATCH函数实现$z_{1}$相对于$\boldsymbol{q}$的供求匹配,求得$D_{q 1}=\{(2, 0.04)\}, S_{q}=S_{q} \backslash\{2\}=\phi$和$x_{q 1}=0$,令$m_{21}=0.04$,得到最终的矩阵$\tilde{\boldsymbol{M}}$。

    $$ \begin{gathered} \tilde{\boldsymbol{M}}^{(2)}=\left(\begin{array}{cccccc} 0.4 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.18 & 0.03 & 0.05 & 0 & 0 \\ 0 & 0 & 0.15 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.08 & 0 & 0 \\ 0 & 0 & 0 & 0.01 & 0.03 & 0 \\ 0 & 0 & 0 & 0.01 & 0 & 0.02 \end{array}\right), \\ S_p=\phi, S_q=\{2\}, \\ \boldsymbol{x}_p=(0,0,0.03,0.05,0,0), \\ \boldsymbol{x}_q=(-0.04,0.04,0,0,0.01,0.01), \\ \tilde{\boldsymbol{M}}=\left(\begin{array}{cccccc} 0.4 & 0 & 0 & 0 & 0 & 0 \\ 0.04 & 0.18 & 0.03 & 0.05 & 0 & 0 \\ 0 & 0 & 0.15 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.08 & 0 & 0 \\ 0 & 0 & 0 & 0.01 & 0.03 & 0 \\ 0 & 0 & 0 & 0.01 & 0 & 0.02 \end{array}\right), \\ S_p=S_q=\phi , \\ \boldsymbol{x}_p=(0,0,0.03,0.05,0,0), \\ \boldsymbol{x}_q=(0,0.04,0,0,0.01,0.01) \text { 。 } \end{gathered} $$

    对比算法1与文献[9]中算法A所给出的结果。取非广延程度$\alpha=0.5$,由算法A所给出的近似最小联合Tsallis熵约为3.696,而由算法1所给出的近似最小联合Tsallis熵约为3.677。

    本文首次探讨了求解最小联合Tsallis熵问题的近似算法。在量子纠缠系统中,利用文献[9]中的算法求解时无法控制近似误差。针对该问题,所提出的算法1通过改进分拆元素的贪心机制,给出了最小联合Tsallis熵的上界和下界,从而控制了求解最小联合Tsallis熵问题的近似误差。

  • 图  1   2种分拆策略分别应用于例2.1(a)算法A; (b)算法1

    下载: 全尺寸图片

    表  算法1   最小联合信息熵供求匹配算法

    输人: 概率分布$\boldsymbol{p}=\left(p_{1}, p_{2}, \cdots, p_{n}\right)$和$\boldsymbol{q}=\left(q_{1}, q_{2}, \cdots, q_{n}\right)$。
    输出: 1个$n \times n$的矩阵$\tilde{\boldsymbol{M}}=\left[m_{i j}\right]$, 使得$\sum_{j} m_{i j}=p_{i}$且$\sum_{i} m_{i j}=q_{j}$。
    2个辅助向量$\boldsymbol{x}_{\boldsymbol{p}}$和$\boldsymbol{x}_{\boldsymbol{q}}$。
    for $i=1, \cdots, n$ and $j=1, \cdots, n$ set $m_{i j} \leftarrow 0$
    if $\boldsymbol{p} \neq \boldsymbol{q}$, let $i=\max \left\{j \mid p_{j} \neq q_{j}\right\}$; if $p_{i}<q_{i}$ swap $\boldsymbol{p} \leftrightarrow \boldsymbol{q}$
    $z=\left(z_{1}, \cdots, z_{n}\right) \longleftarrow \boldsymbol{p} \wedge \boldsymbol{q}, \boldsymbol{r}_{p}=\left(r_{p 1}, \cdots, r_{p n}\right) \longleftarrow z-\boldsymbol{p}, \boldsymbol{r}_{\boldsymbol{q}}=\left(r_{q 1}, \cdots, r_{q n}\right) \longleftarrow z-\boldsymbol{q}$
    set $m_{i i} \leftarrow z_{i}$ for $i=1, \cdots, n$
    $S_{p} \leftarrow \phi, S_{q} \leftarrow \phi, \boldsymbol{x}_{p}=\left(x_{p 1}, \cdots, x_{p n}\right) \leftarrow \boldsymbol{r}_{p}, \boldsymbol{x}_{q}=\left(x_{q 1}, \cdots, x_{q n}\right) \leftarrow \boldsymbol{r}_{q}$
    $i \leftarrow n$
    while $i \geqslant 1$ do
        if $r_{p i}>0$ then
            $S_{p} \leftarrow S_{p} \cup\{i\}, m_{i i} \leftarrow p_{i}$
        end if
        else if $r_{p i}<0$ then
            $\left(D_{p i}, S_{p}, \boldsymbol{x}_{p}\right) \leftarrow \operatorname{MATCH}\left(i, S_{p}, \boldsymbol{x}_{p}\right)$
            for $\left(k, d_{k}\right)$ in $D_{p i}$ do $m_{i k} \leftarrow d_{k}$
        end else if
        if $r_{q i}>0$ then
            $S_{q} \leftarrow S_{q} \cup\{i\}, m_{i i} \leftarrow q_{i}$
        end if
        else if $r_{q i}<0$ then
            $\left(D_{q i}, S_{q}, \boldsymbol{x}_{q}\right) \leftarrow \operatorname{MATCH}\left(i, S_{q}, \boldsymbol{x}_{q}\right)$
            for $\left(k, d_{k}\right)$ in $D_{q i}$ do $m_{k i} \leftarrow d_{k}$
        end else if
        $i \leftarrow i-1$
    end while
    $\operatorname{match}(i, S, \boldsymbol{x})$
    $D_{i} \leftarrow \phi$
    for $k$ in $S$ do
        if $x_{i}<0$ then
            $x_{i} \leftarrow x_{i}+x_{k}, S \leftarrow S \backslash\{k\}, D_{i} \leftarrow D_{i} \cup\left\{\left(k, x_{k}\right)\right\}$
        end if
        else break
    end for
    if $x_{i}>0$ then $S \leftarrow S \cup\{i\}$
    return $\left(D_{i}, S, \boldsymbol{x}\right)$
  • [1] SHANNON C E. A mathematical theory of communication[J]. The Bell System Technical Journal, 1948, 27(3): 379-423. doi: 10.1002/j.1538-7305.1948.tb01338.x
    [2] VIDYASAGAR M. A metric between probability distributions on finite sets of different cardinalities and applications to order reduction[J]. IEEE Transactions on Automatic Control, 2012, 57(10): 2464-2477. doi: 10.1109/TAC.2012.2188423
    [3] KOCAOGLU M, DIMAKIS A G, VISHWANATHV S, et al. Entropic causal inference[C]//SINGH S, MARKOVITCH S. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. San Francisco: AAAI Press, 2017: 1156-1162.
    [4] LI C T, EL G A. Strong functional representation lemma and applications to coding theorems[J]. IEEE Transactions on Information Theory, 2018, 64(11): 6967-6978. doi: 10.1109/TIT.2018.2865570
    [5] PAINSKY A, ROSSET S, FEDER M. Innovation representation of stochastic processes with application to causal inference[J]. IEEE Transactions on Information Theory, 2019, 66(2): 1136-1154.
    [6] ROUGHGARDEN T, KEARNS M. Marginals-tomodels reducibility[C]//BURGES C J, BOTTOU L, WELLING M, et al. Advances in Neural Information Processing Systems 26. Lake Tahoe: NIPS, 2013: 1043-1051.
    [7] KOVAČEVIĆ M, STANOJEVIĆ I, ŠENK V. On the entropy of couplings[J]. Information and Computation, 2015, 242: 369-382. doi: 10.1016/j.ic.2015.04.003
    [8] KOCAOGLU M, DIMAKIS A G, VISHWANATHV S, et al. Entropic causality and greedy minimum entropy coupling[C]//MATHAR R, KRAMER G. 2017 IEEE International Symposium on Information Theory(ISIT). Aachen: IEEE, 2017: 1465-1469.
    [9] CICALESE F, GARGANO L, VACCARO U. Minimum-entropy couplings and their applications[J]. IEEE Transactions on Information Theory, 2019, 65(6): 3436-3451. doi: 10.1109/TIT.2019.2894519
    [10] TSALLIS C. Possible generalization of BoltzmannGibbs statistics[J]. Journal of Statistical Physics, 1988, 52: 479-487. doi: 10.1007/BF01016429
    [11] 吴贤东, 汪加梅, 李婉晴. 关于Tsallis型非对称熵的若干研究[J]. 纯粹数学与应用数学, 2019, 35(1): 100-108.
    [12] 杨松青, 蒋沅, 童天驰, 等. 基于Tsallis熵的复杂网络节点重要性评估方法[J]. 物理学报, 2021, 70(21): 273-284.
    [13] ALOMANI G, KAYID M. Further properties of Tsallis entropy and its application[J]. Entropy, 2023, 25(2): 199. doi: 10.3390/e25020199
    [14] TSALLIS C, PASECHNIK R. Medical applications of nonadditive entropies[J]. Entropy, 2023, 25(4): 578. doi: 10.3390/e25040578
    [15] MARSHALL A W, OLKIN I, ARNOLD B C. Inequalities: theory of majorization and its applications[M]. New York: Springer, 1979.
    [16] CICALESE F, VACCARO U. Supermodularity and subadditivity properties of the entropy on the majorization lattice[J]. IEEE Transactions on Information Theory, 2002, 48(4): 933-938. doi: 10.1109/18.992785
    [17] CICALESE F, GARGANO L, VACCARO U. Approximating probability distributions with short vectors, via information theoretic distance measures[C]//GUILLÉN FÀBREGAS A, MARTINEZ A, VERDÚ S. 2016 IEEE International Symposium on Information Theory. Barcelona: IEEE, 2016: 1138-1142.
    [18] FURUICHI S, YANAGI K, KURIYAMA K. Fundamental properties of Tsallis relative entropy[J]. Journal of Mathematical Physics, 2004, 45(12): 4868-4877. doi: 10.1063/1.1805729
    [19] FURUICHI S. On uniqueness theorems for Tsallis entropy and Tsallis relative entropy[J]. IEEE Transactions on Information Theory, 2005, 51(10): 3638-3645. doi: 10.1109/TIT.2005.855606
    [20] LI C T. Efficient approximate minimum entropy coupling of multiple probability distributions[J]. IEEE Transactions on Information Theory, 2021, 67(8): 5259-5268. doi: 10.1109/TIT.2021.3076986
WeChat 点击查看大图
图(1)  /  表(1)
出版历程
  • 收稿日期:  2023-12-27

目录

    /

    返回文章
    返回