十、张量网络收缩算法

1. 张量网络的基本定义

---

       通过前面的学习，我们对张量网络有了简单的了解，这里我们给出张量网络的一般定义：由多个张量按照一定的收缩规则构成的模型，被称为张量网络。

       其中，收缩规则由张量网络形成的图确定，网络中的一个节点代表一个张量，与该节点连接的边代表该张量的指标，连接不同节点的边代表对应张量的共有指标，我们需要把这些共有指标收缩掉从而计算整个张量网络的结果。

       之前我们提到的 MPS 是一种特殊的张量网络，MPS 中两个不同张量所共有的指标称为 辅助指标（也称为虚拟指标或几何指标）；没有被共有的指标代表物理空间的自由度，称为 物理指标。

       在张量网络中，我们统一的将仅连接一个节点的指标称为 开放指标 ，连接两个节点的指标称为 几何指标 。当张量网络被用于表示量子态时，开放指标代表物理空间的自由度，所以又称为物理指标。

       从张量网络的一般定义出发，我们可以看出，张量网络就是张量的一种表示形式，任意张量网络其实就是一个张量，该张量的指标就是张量网络的开放指标。

       张量网络可以记为：
$$T=\mathrm{tTr}(A,B,\cdots )$$

其中 $T$ 代表收缩所有集合指标后得到的张量，$A、B、\cdots$ 等代表张量网络中的每个张量，$\mathrm{tTr}$ 表示对所有的几何指标求和。

       一个高阶张量可以表示为不同形式的张量网络。如下图所示的两种张量网络都可以表示一个五阶张量 $T_{s_1{s}_2{s}_3{s}_4{s}_5}$ 。

       我们称没有开放指标的张量网络为 闭合张量网络 。闭合张量网络因为没有开放指标，也就是没有自由指标，表示一个标量。闭合张量网络可以用来表示一大类的问题。

2. 张量网络的低秩近似

---

       有了张量网络的定义，我们考虑以下问题，在给定的张量网络中，如何裁剪某一几何指标的维数，使得裁剪前后的张量保持原有的结构，但是两者有着最小的误差。

       这里我们只考虑无圈张量网络中几何指标维数的裁剪。也就是整个张量网络图中不存在环路。

       以下图的张量网络 $T_{s_1{s}_2{s}_3{s}_4{s}_5}$ 为例，我们考虑对途中红色的几何指标进行维数裁剪。

通过矩阵的最优低秩问题进行裁剪

       这是一种比较简单的裁剪方式，我们首先将张量网络矩阵化，也就是沿要裁剪的指标将张量变成矩阵，再对矩阵进行 SVD 分解，实现维数裁剪。

       对于上图的张量，我们可以将其 reshape 成为维数分别为 $s_1\times s_2$ 与 $s_3\times s_4\times s_5$ 的矩阵，表示为 $T_{[s_1{s}_3][s_3{s}_4{s}_5]}$ 。我们对得到的矩阵进行 SVD 分解，保留指定维数的奇异谱，就能实现对张量的裁剪。

       一般情况下我们不推荐使用这种方式对张量网络进行维数裁剪，因为对张量网络 $T$ 的 SVD 分解的复杂度是随着开放指标的维数呈指数上升的，我们将张量转换为张量网络的目的就是为了避免该指数问题，所以我们并不使用这种方式实现维数裁剪。

引入非方的裁剪矩阵进行维数裁剪

       这种方式的基本思路为：通过引入非方的裁剪矩阵，与连接待裁剪指标的张量进行收缩，实现该指标的维数裁剪。

       对于一个要裁剪的指标，我们首先假设连接待裁剪指标的张量分别为 $A^{(1)}$ 与 $A^{(3)}$ ，假设待裁剪指标 $a$ 的维数为 $D$ ，裁剪后的指标维数为 $\chi$ ，我们引入维数为 $D\times \chi$ 的矩阵 $V^L$ 与 $V^R$ ，将矩阵的指标和张量中待裁剪指标进行收缩：
$$A_{s_1{a}_1{a}_2{a}^{\prime }}^{\prime (1)}=\sum _a{A}_{s_1{a}_1{a}_{2}a}^{(1)}{V}_{a{a}^{\prime }}^L$$

$$A_{s_3}^{\prime (3)}{a}_3{a}_4{a}_{\prime }=\sum _a{A}_{s_3{a}_3{a}_{4}a}^{(3)}{V}_{a{a}^{\prime }}^R$$

我们可以用图形表示为，$V^L$ 与 $V^R$ 被称为裁剪矩阵：

       因为我们引入了裁剪矩阵，那么不可避免的就会对原仗张量网络造成影响，那么几何指标维数裁剪的问题就转换为，如何计算裁剪矩阵，使得裁剪误差极小化。

一种常用的算法步骤如下：

1. 通过规范变化，将张量网络变换为中心正交形式，正交中心为连接待裁剪指标的两个张量中的其中一个。如下图所示，正交中心为 $A^{(3)}$ ，中心正交形式中，除正交中心张量外，其他张量满足正交性，我们用箭头表示正交条件，也就是该张量的所有内向指标对应与其共轭进行收缩，得到以外向指标为指标的单位阵。

2. 对正交中心的张量进行奇异值分解，由前 $\chi$ 个奇异向量构成 $V^L$ ，且 $V^L=V^R$ 。以 $A^{(3)}$ 为例，我们对其进行奇异值分解，即：
   $$A_{s_3{a}_3{a}_{4}a}^{(3)}=\sum _{a^{\prime }}{U}_{s_3{a}_3{a}_4{a}^{{}^{\prime }}}{\Lambda }_{a^{{}^{\prime }}}{V}_{aa}^{\ast }$$

那么 $V$ 的前 $\chi$ 个奇异向量构成裁剪矩阵，即 $V^L=V^R=V_{:,0:\chi }$ 。

由于 $V^L$ 的正交性，可以得到：

1. 更新后 $A^{{}^{\prime }(1)}$ 的正交性不变，即
   $$A_{s_1{a}_1{a}_2{a}^{\prime }}^{\prime (1)}=\sum _a{A}_{s_1{a}_1{a}_{2}a}^{(1)}{V}_{a{a}^{\prime }}^L$$

2. 变换后的 $A^{(3)}$ 可写成定义在指标 $a$ 上的 $\Lambda$ 乘上正交张量 $U$ ，此时张量网络的正交中心为 $\Lambda$ ，即：
   $$A_{s_3{a}_3{a}_4{a}^{\prime }}^{\prime (3)}={\Sigma }_a{A}_{s_3{a}_3{a}_{4}a}^{(3)}{V}_{a{a}^{\prime }}^R=\sum _{a^{\prime }=0}^{\chi -1}{U}_{s_3{a}_3{a}_4{a}^{\prime }}{\Lambda }_a$$

3. 通过上面的讨论可以得出，上述的裁剪方式实际上是保留了 $\Lambda$ 中 $\chi$ 个最大奇异值以及相关的奇异向量，且由于 $\Lambda$ 为正交中心，整个张量网络 $T=\mathrm{tTr}\left(A^{(1)},\cdots A^{(5)}\right)$ 在指标 $a$ 二分时的前 $\chi$ 个奇异谱为 $\Lambda$ 。如果想保持张量网络的形式不变，可以将 $\Lambda$ 乘入 $A^{{}^{\prime }(3)}$ ，那么整个张量网络的正交中心变为 $A^{{}^{\prime }(3)}$ 。

4. 因为 $\Lambda$ 为正交中心，其余张量都是正交的，对 $A^{(3)}$ 进行的局域奇异值裁剪实际就是全局最优的裁剪，也就是极小化了裁剪误差
   $$ϵ=\left|\mathrm{tTr}\left(A^{(1)},A^{(2)},A^{(3)},A^{(4)},A^{(5)}\right)-\mathrm{tTr}\left(A^{\prime (1)},A^{(2)},A^{\prime (3)},A^{(4)},A^{(5)}\right)\right|$$

而且其避免了计算整个张量网络 $T_{[s_1{s}_3][s_3{s}_4{s}_5]}$ 的奇异值分解，避免了指数大的问题。

3. 张量重整化群(TRG)算法

---

       下面我们考虑一种特殊的张量网络收缩计算，即 由无穷多个张量构成的闭合张量网络，且所有张量都相等。我们记该类张量网络为
$$Z=\mathrm{tTr}\left([T{]}^{\infty }\right)$$

$T$ 被称为构成该张量网络的 不等价张量 ，整个张量网络都是由 $T$ 组成。

该类张量网络由两个因素完全确定：

1. 不等价张量
2. 张量网络的几何结构

       下面我们以定义在无穷大正方格子上的张量网络为例计算这种类型网络的收缩。如下图所示，显然，严格收缩该张量网络的计算复杂度会随着收缩的进行呈指数上升。

       我们使用 张量重整化群(TRG) 算法，通过引入合理的近似，将计算复杂度控制到多项式级。该算法的步骤如下：

1. 在第 $t$ 次的循环中，利用 SVD 对不等价张量 $T$ 做下面两种不同的分解。

   一种是将不等价张量矩阵化为两个维度分别为 $s_1\times s_2$ 与 $s_3\times s_4$ 的矩阵，然后对其进行 SVD 分解，其中的奇异谱可以任意收缩到 $U$ 或 $V$ 中：
   $$T_{\left[s_1{s}_2\right]\left[s_3{s}_4\right]}^{(t)}\cong \sum _{s^{\prime }=0}^{\chi -1}{U}_{\left[s_1{s}_2\right]s^{\prime }}{V}_{\left[s_3{s}_4\right]s^{\prime }}$$

   另外一种是将不等价张量矩阵化为两个维度分别为 $s_1\times s_4$ 与 $s_2\times s_3$ 的矩阵，再对其进行奇异值分解，其中的奇异谱可以任意收缩到 $P$ 或 $Q$ 中：
   $$T_{\left[s_1{s}_4\right]\left[s_2{s}_3\right]}^{(t)}\cong \sum _{s^{\prime \prime }=0}^{\chi -1}{P}_{\left[s_1{s}_4\right]s^{\prime \prime }}{Q}_{\left[s_2{s}_3\right]s^{\prime \prime }}$$

   在进行 SVD 分解时，当奇异谱的维数大于截断维数 $\chi$ 时，则仅保留前 $\chi$ 个最大的奇异值对应的奇异向量。

   该步用图形表示如下：
   

2. 经过第一步的分解，我们将每个张量都替换为上面两种 SVD 分解其中一种得到的张量，整个张量网络被变换为如下的形式。我们可以将图中虚线框内的张量收缩，得到一个四阶张量：
   $$T_{s_1^{\prime }{s}_2^{\prime }{s}_3^{\prime }{s}_4^{{}^{\prime }}}^{\prime (t)}=\sum _{s_1{s}_2{s}_3{s}_4}{V}_{s_3{s}_4{s}_1^{{}^{\prime }}}{Q}_{s_2{s}_3{s}_2^{{}^{\prime }}}{U}_{s_1{s}_2{s}_3^{{}^{\prime }}}{P}_{s_1{s}_4{s}_4^{{}^{\prime }}}$$

3. 对每一个收缩后的张量进行归一化处理
   $$C^{(t)}=\left|T_{s_1^{\prime }{s}^{\prime }{s}_3^{\prime }{s}_4^{\prime }}^{\prime (t)}\right|$$

   $$T_{s_1^{\prime }{s}_2^{\prime }{s}_3^{\prime }{s}_4^{\prime }}^{(t+1)}=\frac{T_{s_1^{\prime }{s}_2^{\prime }{s}_3^{\prime }{s}_4^{\prime }}^{\prime (t)}}{C^{(t)}}$$

   其表示对第 $t$ 次收缩后的张量求其范数，归一化后得到下次收缩的初始张量 $T^{(t+1)}$ 。之后张量网络又变成了正方格子网络，但是经过前面的操作，我们先将一个张量变成了两个，之后收缩四个张量为一个张量，总的张量个数会减少一半，经过 $t$ 次收缩整个张量网络变为：

   $$\mathrm{tTr}\left({\left[T^{(t+1)}\right]}^{\frac{\infty }{2^t}}\right)$$

   张量总个数为最初的 $\frac{1}{2^t}$ 倍。$C^{(t)}$ 被称为 重整化因子 。

4. 检查不等价张量是否收敛 ，如果未达到收敛阈值，则返回第一步，如果收敛，计算张量网络收缩的结果
   $$Z=\prod _{t=1}^{\tilde{t}}{\left[C^{(t)}\right]}^{\frac{N}{2^t}}=\prod _{t=1}^{\tilde{t}}{\left[C^{(t)}\right]}^{2^{(t-t)}}$$

   其中，N 为收敛时张量网络中每个张量等效代表的原始张量 $T^{(0)}$ 的个数，这个过程就称为重整化群，满足 $N=2^{\tilde{t}}$ ，$\tilde{t}$ 为收敛时的迭代次数。因为每进行一步迭代，张量网络中张量的个数减少一半，相当于收缩后的每个张量等效地代表收缩之前的两个张量。

   之所以可以用 $Z$ 代表整个张量网络的收缩结果，是因为如果我们没有进行归一化，直接对 $T^t$ 进行收缩就是整体的结果，但是由于我们在每一步进行了归一化处理，即每一步除以一个重整化因子 $C^{(t)}$ ，所以我们整个张量网络的收缩结果就可以用 $Z$ 来表示。

       上式中的 $Z$ 是难以计算的，其取值取决于收敛次数，它可能是发散的，这里我们定义张量网络的 平均自由能 来刻画张量网络：
$$F=-\frac{\ln Z}{N}=\ln \left[\frac{{\prod }_{t=1}^{\tilde{t}}{\left[C^{(t)}\right]}^{2^{(t-t)}}}{2^{\tilde{t}}}\right]=-\sum _{t=1}^{\tilde{t}}{2}^{-t}\ln C^{(t)}$$

当不等价张量收敛时，重整化因子 $C^{(t)}$ 收敛于 1 ，所以求和项随 $t$ 指数减小，当 $t$ 足够大时，$F$ 收敛，且收敛的 $F$ 与迭代次数 $\tilde{t}$ 无关。

        TRG 算法并没有严格地计算张量网络的收缩。在第一步中，设张量 $T^{(t)}$ 的维数为 $D\times D\times D\times D$ ，如果进行严格的奇异值分解，则分解出的新的指标为 $D^2$ ，即张量 $T^{(t+1)}$ 的维数为 $D^2\times D^2\times D^2\times D^2$ 。可以看出，如果每次迭代都进行严格的奇异值分解，则不等价张量的指标维数将会随着迭代次数呈指数上升。

       如果奇异值分解出的指标维数大于截断维数 $\chi$ ，那么进行维数裁剪，保留前 $\chi$ 个奇异谱对应的奇异向量。该近似中的误差，对于被分解的不等价张量来说是最小化的，因此，不等价张量 $T^{(t)}$ 被称为裁剪环境，所以 TRG 的裁剪环境是局域的，即对整个张量网络而言，其裁剪并不是最优的，这也是限制 TRG 精度的主要因素。

4. 角转移矩阵重整化群算法 (CTMRG)

---

       在 TRG 中，其裁剪环境是局域的，因此整个张量网络的裁剪并不是最优的，这里我么介绍 角转移矩阵重整化群算法 (CTMRG) ，其裁剪环境为非局域的裁剪环境，所以精度更高。

       我们仍然考虑收缩一个不等价张量构成的无穷闭合大张量网络：
$$Z=\mathrm{tTr}\left([T{]}^{\infty }\right)$$

       在角转移矩阵重整化群算法中，我们假设在无穷远的张量网络中有一个 “边界” ，我们在边界处放一些变分张量，记定义在边上的三阶张量 $S$ 为边张量，定义在角上的二阶张量 $C$ 为角矩阵。边张量和角矩阵可以随机初始化。如下图所示：

       考虑到张量网络边的长度（边张量的个数）为无穷大，且由于张量网络具有平移不变性，我们设所有边张量相等，所有角矩阵相等。

       解决该问题的思路为，设计一种迭代收缩的过程，使得边张量与角矩阵达到收敛。

       我们首先将边张量与角矩阵和他们直接相邻的不等价张量进行收缩，其迭代的收缩过程如下图所示：

在收缩过程中包括两种形式的收缩，如下所示：

第一种是边张量和相邻张量的收缩，其收缩的结果是一个新的边张量；第二种是角矩阵与相邻张量和边张量的收缩，其收缩为一个新的角矩阵。

       通过图示，我们可以知道，每进行一次收缩，边张量与角矩阵的指标（上图黄色指标）维数扩大 $d$ 倍，因此，需要使用矩阵或张量的低秩近似对增大的指标维数进行裁剪，否则指标的维数会呈指数增大。其裁剪的方法并不唯一，不同的裁剪方法实际上对应于不同的裁剪环境。