矩阵分解

寻找输入矩阵的结构；

设计逐步分解的方法：分解过程的某一步可能产生特殊性质的矩阵；

评价分解成本以及复杂度；

这种矩阵分解方法，在什么情况下，能比其他分解方法更高效？

一个系统有 N 个量子比特，原始酉矩阵的维度是 2^N * 2^N ，在数学上，分解之后右边的一系列矩阵的维度和原矩阵维度一样。

真机支持的量子门一般都是单比特 和 双比特的，对应的矩阵最大也就 4x4。

所以数学上分解得到的酉矩阵，实际模拟时一般不会在内存里直接存储这个2^N * 2^N 的矩阵，而是记录小矩阵和作用位置。作用在系统上时，只局部修改要作用的比特。

下面分解方法只讨论方阵（酉矩阵是方阵）。

矩阵基础

实对称矩阵

两个式子：转置等于本身；aij=aij

正定矩阵

前提：先是实对称矩阵

核心定义：非零向量 x,有一个表达式；

性质：矩阵的性质从行列式、特征值想；矩阵分解，正定矩阵可以被分解成可逆阵 C 乘以 C 转置；

二次型为什么叫二次型？（每一项的次数之和等于 2）

欧拉公式

$$e^{i\theta} = \cos\theta + i\sin\theta$$

• 提到欧拉公式 应该想到什么：

  欧拉公式代表复平面上一个点（是一个复数）；这个点在 x 轴投影是，在 Y轴投影分别是什么？

  这个复数的运动轨迹是什么？

  这个复数的模长始终等于什么？为什么？复数的模长就是实部的平方加上虚部的平方开根号；

  $$\begin{aligned} \left| e^{i\theta} \right| &= \left| \cos\theta + i\sin\theta \right| \\ &= \sqrt{\cos^2\theta + \sin^2\theta} \\ &= 1 \end{aligned}$$

• 高阶理解

  欧拉公式当做一个算子（操作符）：一个复数乘以$e^{i\theta}$ 等于让这个复数逆时针旋转θ。因为模长为 1，他是不改变模长的。

  在量子力学中，一个态矢量乘以 欧拉形式的 $e^{-iHt}$ 就等于态矢量在希尔伯特空间旋转。所以时间演化算符写成 $e^{-iHt}$ 形式。

  可能会有一个疑问：对于复数来说，复数是二维的（在平面上），乘以欧拉公式之后对一个二维的量进行旋转；但态矢量是高维的，怎么欧拉公式能让二维的旋转 又能让高维的旋转？ 原因：在量子力学这里，欧拉公式指数位置不是一个变量，变成了一个矩阵。 此时欧拉公式是一个酉矩阵。

  在量子计算中，代表相位；相位我还是觉得很抽象。

后向舍入误差

知道有这么个概念。受限于计算机精度，分解出来的矩阵，乘回去不一定等于原矩阵。但是我们求出来的解，是原矩阵稍微扰动后的矩阵的精确分解。

优秀的矩阵分解法，后向舍入误差很小。

前向舍入误差是我们算出来的解和真实解之间的距离，因为我们不知道真实解是什么，所以很难评价前向舍入误差。

海森矩阵 Hessian Matrix

多元函数的二阶偏导构成的矩阵；实对称矩阵；在某一点时，当海森矩阵正定时，函数在该点取最小值；

$$H_{ij}(x_0) = \frac{\partial^2 f}{\partial x_i \partial x_j}(x_0)$$

Cholesky:第一种矩阵分解方法

乔里斯基分解法

对象

正定矩阵；

分解后的形式

正定矩阵 可等价于：下三角矩阵乘以上三角矩阵，且对角线元素都大于零；L 是上三角矩阵；

$$A = L^T L$$

Cholesky 时间复杂度

O(N^3) : $\frac{1}{3} n^3$ 次浮点运算；

有什么用

快速解线性方程组。如果一个方程组的系数是正定矩阵：

把原来一个大方程组的系数矩阵分解成两个上下三角矩阵，然后换元，变成两个线性方程组。但是这两个线性方程组系数都是三角矩阵，很好求。

问题：如何解线性方程组？

• 增广矩阵 初等行变换 化成行最简阶梯型；最简：每一行第一个非零元素是1；阶梯：每一行第一个非零元素一定在上一行的右边；
• 先得到线性通解。没有约束关系的是自由变量，然后能找到几个变量的关系。
• 把原等式右边的一列带上，解出一组特解，然后拼成通解。

LU 分解

Cholesky 分解是 LU 分解的一种特殊形式。

$$\boxed{ A = LU }\\ \boxed{ PA = LU }$$

下面是带主元的 LU 分解。

对象

我们只看方阵：因为我们酉矩阵是方阵；

任意一个非零方阵都可以通过带主元的 LU 分解。

分解后的形式

一个下三角矩阵 L （lower）乘以一个上三角矩阵 U（upper）；L 一定是方阵；

时间复杂度

分解一个大矩阵的时间复杂度是：O(N^3); 具体 $\frac{2}{3} n^3$ 次浮点运算；

求解每个右端矩阵的复杂度是： O(N^2);

分解方法

矩阵 A，用初等行变换变成上三角矩阵U，此时 L 矩阵记录的是变换过程中用到的系数。L 矩阵的对角线元素都是 1. 可以用初等行变换推出来。

有的时候 A 矩阵需要行变换，交换一下主元。等价于左乘 P；

• L 记录的系数

  系数对应位置在哪里？

  L 矩阵中存储的“乘数”（Multipliers），是做初等行变换时使用的系数的相反数

有什么用

依然可以解方程组；

QR 分解

将方阵分为一个列正交归一的方阵 Q 和上三角矩阵 R；

这么记：原矩阵分解得到的 Q 是将原矩阵的列向量正交化（施密特正交）；

分解得到的 R 记录的是： 原矩阵的列向量 是如何由 Q 矩阵 的向量组合而成。一些缩放的系数；

为保证唯一性，R 矩阵要求对角线是正的实数；

基础

列正交：是指各个列向量相互正交； 归一：是指列向量模长为 1；

向量 a 在向量 b 上的投影长度：

$$\frac{\mathbf{a}^T \mathbf{b}}{\|\mathbf{b}\|}$$

注意投影到 b，除以的是 b 的模长。其中：

$$\mathbf{a}^T \mathbf{b} = \|\mathbf{a}\| \cdot \|\mathbf{b}\| \cdot \cos \theta$$

这是向量的内积（点乘）。

施密特正交

原矩阵两个向量 a1, a2;

• 先把 a1 单位化得到 b1, 除以模长，模长是 R 矩阵一个系数；
• 减投影：a2 减去 它在 b1 方向上的投影，得到的向量就是和 b1 垂直的；记为 b2; 投影是系数，R 里面的值；
• 再把 b2 归一化，归一化的系数是 R 的值；

向量归一化的值，放在 R 的对角线位置；

如果有三个向量呢？求出前两个向量，第三个向量减去在前两个向量的投影，再归一化，得到 Q 的第三个向量；

理解一下不用记公式：知道投影的公式，知道减去在已正交的向量上的投影就行；

对象

一般方阵。

分解后的形式

一个正交矩阵乘以 上三角矩阵；

扩展到复数领域，这个正交矩阵就是 酉矩阵；

复数矩阵形式的 QR 分解：

$$A = QR, \quad Q^\dagger Q = I$$

分解方法

三种：常规的施密特正交；逐向量正交化；

Householder 不学；

Givens 旋转：用二维平面逐个消去元素，与酉矩阵分解关系最大；

Givens 分解

谱分解

把矩阵（酉矩阵一定能谱分解）分解为一个酉矩阵乘以 对角矩阵 乘以酉矩阵。两个酉矩阵互为共轭转置。

酉矩阵的列向量是原矩阵的特征向量。

谱分解就是求特征向量和特征值的。

$$\boxed{ A = Q \Lambda Q^\dagger }$$

对象

实对称矩阵、酉矩阵一定能谱分解。

分解方法

像求矩阵特征值特征向量一样。|λE-A|=0 求特征值，然后解特征方程得到特征向量。

应该掌握

1 最基本的计算要会，怎么求特征值、特征向量？

2 理解数学层面：矩阵在自己的特征向量 作用下 变成对角矩阵；

3 可以借助谱分解计算 (e^{-iHt})，但要把它变成原生量子门，通常还需要进一步进行电路合成。

实际例子 1：复杂酉矩阵变成几个酉矩阵乘积

矩阵能当指数、还能当三角函数值。

根据薛定谔方程解酉矩阵：（假设哈密顿量不随时间演化）

$$U(t) = e^{-iHt},$$

上面这一步，把 H 具体的值代入，U(t)是一个复杂的酉矩阵。

把哈密顿量的谱分解：

$$H = Q \Lambda Q^\dagger,$$

再把分解结果代入时间演化算符酉矩阵：

$$U(t) = e^{-i (Q \Lambda Q^\dagger) t}$$

根据矩阵指数运算的公式化简：指数上面的酉矩阵 Q 和酉矩阵转置可以拉下来：

$$U(t) = Q e^{-i \Lambda t} Q^\dagger.$$

化成这样有什么好处：这三个都是酉矩阵。把原来一个大的酉矩阵变成了三个酉矩阵。

实际例子 2：一个酉矩阵变成几个真正的量子门

哈密顿量：

$$H = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$$

谱分解后：

$$Q = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$

且：

$$Q^\dagger = Q = H_{\text{gate}}$$

中间的对角酉矩阵：

$$D(t) = \begin{bmatrix} e^{-i3t} & 0 \\ 0 & e^{-it} \end{bmatrix}$$

可以改写成：

$$D(t) = e^{-i2t} \begin{bmatrix} e^{-it} & 0 \\ 0 & e^{it} \end{bmatrix}$$

根据 $R_z$ 门的定义：

$$R_z(\theta) = \begin{bmatrix} e^{-i\theta/2} & 0 \\ 0 & e^{i\theta/2} \end{bmatrix}$$

因此：

$$D(t) = e^{-i2t} R_z(2t)$$

最终：

$$\boxed{U(t) = e^{-i2t} H_{\text{gate}} R_z(2t) H_{\text{gate}}}$$

需要面临的问题：当比特数较大时，分解出来的 Q 也很大，远大于真机量子门的 2x2.所以还得继续分解。

重要性质：

• e 的指数位置不是对角矩阵的情况下，$e^{A }$很难求，如果 A 是对角矩阵的话：指数后的矩阵是对角线元素变指数：

$$e^\Lambda = \begin{bmatrix} e^{\lambda_1} & 0 \\ 0 & e^{\lambda_2} \end{bmatrix}$$

• 对角矩阵取指数后，就变成酉矩阵

  （对角矩阵满足不同列向量内积为 0，但是不满足列向量模长为 1；）

Schor 分解

舒尔分解：跟谱分解一块记。

区别：因为我要讨论的是酉矩阵，所以谱分解 舒尔分解都可以。但是谱分解范围很更广，只要是方阵都能谱分解。所以把谱分解的对角矩阵放宽成了上三角矩阵。

$$U = Q D Q^\dagger$$

把酉矩阵分解为：酉矩阵乘以上三角矩阵乘以酉矩阵转置。

性质：Q 仍然是酉矩阵。还是先求特征值，特征向量。然后 Q 的列向量是特征向量。但是，不同的是，N 阶 酉矩阵 U 只有 M 个线性无关的特征向量，但是 Q 需要有N个列向量，此时 Q 的另外 N-M 个列向量怎么求？需要找 N-M 个彼此正交且和原来特征向量正交的向量。可能用到施密特正交法。

奇异值分解

SVD（Singular Value Decomposition）应用范围广，酉矩阵比较特殊，不需要学这个。杀鸡焉用牛刀。

上面是经典的矩阵分解方法，下面是和酉矩阵分解关系密切的分解方法。

Given 旋转值得再看；

欧拉角分解：怎样把一个 2x2 酉矩阵分解成单比特旋转门？

KAK分解：任意双比特酉矩阵合成；

CSD 分解：余弦-正弦分解；递归分解的重要基础；

QSD：量子香农分解；任意多比特酉矩阵到量子门序列的一类通用分解算法；

Trotter 分解，另一条路线了，从哈密顿量直接构造电路；

AQC：酉矩阵合成转化为优化问题；

QSD分解

大概

Quantum Shannon Decomposition 量子香农分解定理

量子计算中 非常重要的通用酉矩阵分解方法。

核心思想：递归使用 CSD（Cosine-Sine Decomposition）、Multiplexed Unitary 多路复用酉变换。

论文：一个大酉矩阵经过结构化分解，怎么一步步得到明确的单比特和双比特门？

数学流程

先把酉矩阵分 4 块

按 N 个量子比特其中的 1 个，将矩阵分块：

$$\boxed{ U = \begin{bmatrix} U_{00} & U_{01} \\ U_{10} & U_{11} \end{bmatrix} }$$

例如原来 8x8 矩阵分解为：4 个 4x4矩阵。

解释一下怎么根据一个量子比特将矩阵分为 4 块。

这里的分块涉及到原矩阵元素行列的置换。不是单单对矩阵来个十字架切分。

• 划分的原理：以 N=4 为例，第一个比特 q0作为划分比特。

  酉矩阵作用在原向量上，得到新向量。

  这个乘法过程，原向量的前两行q0都是 0，矩阵中和 q0=0相乘的就是前两列元素，因此前两列可以看作是把 q0 当做输入时，对应的元素；后两列自然是 q0=1 对应的系数；

  看新向量，新向量中 q0=0 对应向量的前两行，而新向量的前两行就是矩阵前两行乘以旧向量得到的；所以把 q0 看作输出，对应矩阵的元素，是前两行。

  简单说：把 q0 看作输入，看原向量，矩阵中乘以原向量中 q0=0 的分一起（列分）；

  把 q0 看作输出，看新向量，矩阵中对新向量 q0=0 有贡献的元素分一起。