Tensor PCA

Matrix PCA（主成分分析）寻找矩阵的最大 eigenvector，其全部理论基础是矩阵的谱定理。但高阶 tensor（三阶及以上）没有同样简单的 spectral theorem：没有与矩阵特征分解完全平行的理论，相关的计算问题在最坏情形下甚至是 NP-hard 的。Quantum tensor PCA 的思路是绕开”张量谱理论缺失”这一障碍：把 tensor entries 写成一个多体 bosonic Hamiltonian，用量子态的对称子空间隐式表示指数维的对象，再用 Hamiltonian simulation、phase estimation 和 amplitude amplification 找到与隐藏 spike 对齐的低能/高能方向。在特定弱信号与资源模型下，它相对已知 classical spectral method 给出”二次再二次”、合计 quartic（四次方）的指数率改善。

本词条面向已学过的读者。我们会用到 相位估计、振幅放大 与 Hamiltonian simulation / block encoding 作为黑盒工具，引用时只做回顾、不再重新推导。

1. 背景：从矩阵 PCA 到张量 PCA

1.1 矩阵 PCA 回顾

经典 PCA 的输入是一个对称矩阵 $M\in {\mathbb{R}}^{N\times N}$（例如样本协方差矩阵），目标是其最大 eigenvalue 对应的 eigenvector $u_1$——数据方差最大的方向。谱定理保证对称矩阵可以正交对角化：

$$M=\sum _{i=1}^N{\mu }_i{u}_i{u}_i^T,⟨u_i,u_j⟩={\delta }_{ij},$$

于是 $u_1$ 可以用 power iteration 求得：从随机向量 $x$ 出发反复计算 $x\leftarrow Mx/\Vert Mx\Vert$，只要 $|{\mu }_1|>|{\mu }_2|$ 且初态与 $u_1$ 不正交，就几何速度收敛。每次迭代是一次矩阵–向量乘法，稠密情形下代价 $O(N^2)$。这一切之所以简单，是因为矩阵有谱定理：特征向量张成整个空间，power iteration 只是在”放大最大特征方向的分量”。

1.2 Spiked matrix 与相变现象

一个更有统计味道的问题是 spiked matrix 模型：观测矩阵是一个隐藏的秩一信号加上随机噪声，

$$M=\mu u{u}^T+W,$$

其中 $\Vert u\Vert =1$，$W$ 是随机噪声矩阵（如 Wigner 矩阵），$\mu$ 是信号强度。这个模型最深刻的已知结果是存在相变：当 $\mu$ 低于某个阈值时，$M$ 的最大特征值贴在噪声谱的边缘上，对应的 eigenvector 与 $u$ 的 overlap 渐近为零——信号完全淹没在噪声里；当 $\mu$ 超过阈值，最大特征值从噪声谱中”脱出”，其 eigenvector 突然获得与 $u$ 的非消失 overlap。这就是著名的 BBP 相变（Baik–Ben Arous–Péché）。要点是：对矩阵而言，“谱方法何时失效”有精确答案，而且失效边界本身就是尖锐的相变点。

1.3 张量为什么没有同样好办的理论

把矩阵推广为 $p$ 阶张量后，几乎所有好性质都消失了：

• 没有普适的谱定理。矩阵特征值问题的许多等价刻画（Rayleigh 商、变分原理、正交对角化）在张量上各奔东西，不同定义给出不同的”特征值”概念，且张量一般不能正交”对角化”。
• 最坏情形困难。张量特征值、最佳秩一逼近等问题的判定版本在最坏情形下是 NP-hard 的，所以任何高效算法都必须利用输入的统计结构，而不是对任意张量奏效。
• 经典 PCA 的工具箱失灵。power iteration 的推广（张量幂迭代）不再有全局收敛保证；flattening（把张量摊成矩阵，见第 3 节）能用，但要付出维度膨胀的代价。

然而，统计物理风格的随机模型告诉我们，困难与不可能之间有一条鸿沟，这正是本词条问题的舞台。

1.4 Spiked tensor 模型与统计–计算鸿沟

Spiked tensor 模型（由 Richard 与 Montanari 于 2014 年系统提出）是 spiked matrix 的张量版本：观测

$$T=\lambda v^{\otimes p}+G,$$

即从噪声张量 $G$ 中检测并恢复隐藏的”尖峰”方向 $v$。围绕这个模型，过去十余年的研究揭示了三条彼此分离的阈值：

1. 信息论阈值：信号强到某个（很低的）程度后，$v$ 在原理上可以被恢复——例如用指数时间的穷搜或 Bayes 最优估计。
2. 多项式时间算法阈值：已知的多项式时间经典算法（flattening 等谱方法、张量幂迭代、平方和（sum-of-squares）半正定规划）需要显著更强的信号才能工作。
3. 两者之间就是著名的统计–计算鸿沟 (statistical–computational gap)：当 $p\ge 3$ 时这条鸿沟不关闭，且被普遍猜想为本质性的。

换句话说，张量 PCA 是一个”原则上容易、计算上困难”的问题——这正是量子算法可能有所作为的典型地形。

1.5 量子机会的直觉

量子算法面对指数维对象时的标准策略是：不显式构造对象，而是把它编码为 Hamiltonian，用量子动力学去”感受”它的谱。第 4 节会看到，$p$ 阶张量 $T$ 可以自然地写成 $N$ 个玻色模式之间的 $p$-体相互作用 $H(T)$；spike 方向 $v$ 对应一个特殊的玻色模式，信号项倾向于让玻色子”凝聚”到该模式上。凝聚是一种相干放大机制：信号贡献随玻色子数相干增长，而随机噪声的贡献只按非相干方式增长。于是”检测弱 spike”被翻译成”在一个固定玻色子数的对称子空间中，找出 $H(T)$ 谱中由信号主导的窗口”——后者恰好是 phase estimation 与 amplitude amplification 的主场。

2. Spiked tensor 模型

现在给出问题的形式化定义。考虑 order-$p$ 的 symmetric tensor（指标任意置换下不变的张量）

$$T=T_0=\lambda v^{\otimes p}+G,v\in {\mathbb{R}}^N,\Vert v\Vert =\sqrt{N},$$

其中各符号的含义是：

• $v^{\otimes p}$ 是 $v$ 的 $p$ 次张量积，即 $(v^{\otimes p}{)}_{i_1\dots i_p}=v_{i_1}{v}_{i_2}\cdots v_{i_p}$；
• $\Vert v\Vert =\sqrt{N}$ 是归一化约定：它使得 $v$ 的典型分量是 $O(1)$ 量级（例如 $v=(1,1,\dots ,1)$），从而 $v^{\otimes p}$ 的典型元素也是 $O(1)$，不同 $N$ 之间可以公平比较；
• $G_{i_1\dots i_p}$ 是适当归一化的 Gaussian noise（独立高斯元，方差按问题的缩放选好）；
• $\lambda \ge 0$ 是 signal strength（信噪比旋钮）。

恢复目标不是逐项恢复 $v$（弱信号下这不可能），而是输出一个 estimator $\hat{v}$，它与 $v$ 有非消失的归一化 overlap：

$$\frac{|⟨\hat{v},v⟩|}{\Vert \hat{v}\Vert \Vert v\Vert }\ge c>0,$$

其中 $c$ 是与 $N$ 无关的常数。这叫弱恢复 (weak recovery)：只要输出方向与真方向有恒定相关性，就算成功——它远弱于 $\Vert \hat{v}-v\Vert \to 0$ 的强恢复，但在统计上已经有意义（例如可以作为后续局部算法的初始化）。

信号强度的缩放。统计上与计算上可恢复的 threshold 不一定相同（第 1.4 节的鸿沟）。所讨论的量子算法关注 classical spectral regime 附近的弱信号区域，常写

$$\lambda =\alpha N^{-p/4},$$

其中 $\alpha$ 是不随 $N$ 增长的参数。这个指数 $-p/4$ 不是随意的：在 $\Vert v\Vert =\sqrt{N}$ 的约定下，它正是 flattening 类谱方法”勉强还能工作”的信号尺度，因此把算法放在这个 scaling 下比较，比的是各方法在各自能力边界附近的表现。

Warning

这里的 normalization 很重要；改变 $G$ 或 $v$ 的尺度会改变表面 threshold。文献中另一种常见约定是 $\Vert v\Vert =1$ 并把噪声方差写成 $1/N$ 级别，两种约定下阈值的具体数值看起来完全不同，但物理内容一致。比较不同工作的复杂度结论时，第一步永远是核对归一化。

3. 为什么经典谱方法先想到 flattening

既然张量没有谱定理，经典谱方法的自然策略是把张量摊回矩阵。当 $p$ 为偶数，把前 $p/2$ 个 indices 合并为一个”大行指标”、后 $p/2$ 个合并为一个”大列指标”，得到矩阵

$$M_{(i_1\dots i_{p/2}),(i_{p/2+1}\dots i_p)}=T_{i_1\dots i_p}.$$

这就是张量的一个 flattening（也叫 unfolding 或 matricization）。大行指标取遍 $N^{p/2}$ 种组合，所以 $M$ 的维数是 $N^{p/2}\times N^{p/2}$。关键观察是 spike 项摊成了秩一矩阵：由 $(v^{\otimes p}{)}_{i_1\dots i_p}=v_{i_1}\cdots v_{i_p}$ 可以分离变量，

$$\lambda v^{\otimes p}\stackrel{\text{flatten}}{\to }\lambda \left(v^{\otimes p/2}\right)(v^{\otimes p/2}{)}^T,$$

即 $M$ 的 spike 方向是

$$v^{\otimes p/2}\in {\mathbb{R}}^{N^{p/2}}.$$

于是问题形式上退化为我们熟悉的 spiked matrix：Power iteration 或 eigensolver 可抓住 $M$ 的最大 eigenvector，再把分量重新排布回张量指标，即得 $v$ 的估计。

代价在哪里。这个”化未知为已知”的方案付出了指数级的空间与带宽代价：

• 显式保存 $M$ 需要 $N^p$ 级 entries（$N^{p/2}\times N^{p/2}$ 个元素），每次矩阵–向量乘法也要触及这么多项；
• 即使利用对称性、只在指标的多重集（multiset）上工作——也就是只在”每种占据数组合”上保留一个分量——对称化后的维数仍随合并的副本数 $p/2$ 快速增长（确切公式见第 4.2 节）。

换句话说，flattening 把一个”代数上秩一”的对象放进了一个指数维的向量空间，而经典算法必须为这个空间的维度买单。这正是量子 state space 可隐式表示的结构：量子态天然生活在张量积（以及它的对称子空间）中，维度 $N^{p/2}$ 只对应 $\frac{p}{2}{\log }_{2}N$ 个 qubit。下一个问题是如何把 $T$ 本身变成作用在该空间上的算符。

4. 从张量到 bosonic Hamiltonian

4.1 Fock 空间与产生湮灭算符

引入 $N$ 个 modes（模式）的 creation/annihilation operators $a_i^{†},a_i$，满足正则对易关系 (canonical commutation relations)

$$[a_i,a_j^{†}]={\delta }_{ij},[a_i,a_j]=[a_i^{†},a_j^{†}]=0.$$

真空态 $|0⟩$ 被所有湮灭算符消灭：$a_i|0⟩=0$。一般的 Fock 基态由占据数 (occupation numbers) 标记：

$$|n_1,n_2,\dots ,n_N⟩=\prod _{i=1}^N\frac{(a_i^{†}{)}^{n_i}}{\sqrt{n_i!}}|0⟩,n_i\in \{0,1,2,\dots \},$$

表示第 $i$ 个模式上有 $n_i$ 个玻色子。分母 $\sqrt{n_i!}$ 是归一化因子，它来自对易关系的反复使用：$(a_i{)}^m(a_i^{†}{)}^n|0⟩=\frac{n!}{(n-m)!}(a_i^{†}{)}^{n-m}|0⟩$（当 $m\le n$）。

数算符 ${\hat{n}}_i=a_i^{†}{a}_i$ 测量第 $i$ 个模式的占据数：${\hat{n}}_i|n_1,\dots ,n_N⟩=n_i|n_1,\dots ,n_N⟩$。我们固定总 boson 数

$$\sum _{i=1}^N{a}_i^{†}{a}_i=n_{\mathrm{bos}},$$

即只在这个总粒子数算符的某个本征子空间——称为 fixed-boson sector——内工作。

4.2 Fixed-boson sector 就是对称子空间

这个 sector 等价于 $n_{\mathrm{bos}}$ 个 $N$ 维 qudits 的 symmetric subspace（在任意置换下不变的张量积态构成的子空间）。等价关系是具体的：把占据数态 $|n_1,\dots ,n_N⟩$ 对应到”第 $i$ 个 qudit 取值 $i$ 出现 $n_i$ 次”的对称化张量积态。

该 sector 的维数等于方程 $n_1+\cdots +n_N=n_{\mathrm{bos}}$ 的非负整数解个数，由 stars and bars（隔板法）计数为

$$D=\left(\genfrac{}{}{0ex}{}{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}\right).$$

推导一下：把 $n_{\mathrm{bos}}$ 个不可区分的”星”（玻色子）排成一行，用 $N-1$ 块”隔板”把它们分成 $N$ 组（允许空组），第 $i$ 组的星数就是 $n_i$。星与隔板共 $n_{\mathrm{bos}}+N-1$ 个位置，从中选出 $n_{\mathrm{bos}}$ 个放星（等价地，$N-1$ 个放隔板），方案数即 $\left(\genfrac{}{}{0ex}{}{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}\right)$。每个方案唯一对应一个 Fock 基态，反之亦然，故维数得证。

作为参照：$N$ 固定、$n_{\mathrm{bos}}$ 增长时 $D\approx n_{\mathrm{bos}}^{N-1}/(N-1)!$；$n_{\mathrm{bos}}$ 固定、$N$ 增长时 $D\approx N^{n_{\mathrm{bos}}}/n_{\mathrm{bos}}!$。后一种 regime 正是”对称子空间维数随副本数多项式增长”的定量表达。

4.3 Hamiltonian 的构造

对偶数 $p$，用 tensor 系数定义 number-preserving 的 $p$-body interaction（略去 normalization 常数）

$$H(T)=\sum _{i_1,\dots ,i_p}{T}_{i_1\dots i_p}{a}_{i_1}^{†}\cdots a_{i_{p/2}}^{†}{a}_{i_{p/2+1}}\cdots a_{i_p}.$$

逐项解读这个定义：

• 前 $p/2$ 个指标配产生算符、后 $p/2$ 个配湮灭算符，正好对应第 3 节 flattening 的行/列划分：$H(T)$ 就是把摊平矩阵 $M$ “第二次量子化”后得到的算符。
• Number-preserving：每一项产生 $p/2$ 个、湮灭 $p/2$ 个玻色子，因此 $[H(T),{\sum }_i{\hat{n}}_i]=0$，fixed-boson sector 是 $H(T)$ 的不变子空间——我们可以在该 sector 内部自洽地讨论它的谱。
• Hermiticity：因为 $T$ 是对称张量且元为实数，取 $H(T)$ 的 Hermitian 共轭只是把每一项的产生/湮灭角色互换并重排求和哑指标，结果不变，即 $H(T{)}^{†}=H(T)$。这是把它当作 Hamiltonian 来模拟的前提。

4.4 信号项的化简：完整推导

若 $T=\lambda v^{\otimes p}$（暂时忽略噪声），则 $T_{i_1\dots i_p}=\lambda v_{i_1}\cdots v_{i_p}$，求和完全分离变量：

$$H_{\mathrm{signal}}=\lambda \sum _{i_1,\dots ,i_p}{v}_{i_1}\cdots v_{i_p}{a}_{i_1}^{†}\cdots a_{i_{p/2}}^{†}{a}_{i_{p/2+1}}\cdots a_{i_p}=\lambda {\left(\sum _i{v}_i{a}_i^{†}\right)}^{p/2}{\left(\sum _j{v}_j{a}_j\right)}^{p/2}.$$

第二步成立的理由：所有产生算符彼此对易（$[a_i^{†},a_j^{†}]=0$），所有湮灭算符彼此对易（$[a_i,a_j]=0$），所以 ${\left({\sum }_i{v}_i{a}_i^{†}\right)}^{p/2}$ 按多项式定理展开后逐项正是 $v_{i_1}\cdots v_{i_{p/2}}{a}_{i_1}^{†}\cdots a_{i_{p/2}}^{†}$，与上式的产生算符部分一一对应；湮灭部分同理。

现在定义归一化的组合模式算符

$$b_v^{†}=\frac{1}{\sqrt{N}}\sum _i{v}_i{a}_i^{†},b_v=\frac{1}{\sqrt{N}}\sum _i{v}_i{a}_i.$$

它确实是一个合法的玻色模式，即满足单模正则对易关系。验证：

$$[b_v,b_v^{†}]=\frac{1}{N}\sum _{i,j}{v}_i{v}_j[a_i,a_j^{†}]=\frac{1}{N}\sum _{i,j}{v}_i{v}_j{\delta }_{ij}=\frac{1}{N}\sum _i{v}_i^2=\frac{\Vert v{\Vert }^2}{N}=1,$$

其中第一步用了对易关系的双线性与 $[a_i,a_j^{†}]={\delta }_{ij}$，最后一步用了归一化约定 $\Vert v\Vert =\sqrt{N}$。这正是该约定的深层原因：它让 $v$ 方向上的组合模式成为标准的玻色模式。

于是 ${\sum }_i{v}_i{a}_i^{†}=\sqrt{N}{b}_v^{†}$，代入得

$$H_{\mathrm{signal}}=\lambda N^{p/2}(b_v^{†}{)}^{p/2}(b_v{)}^{p/2}.$$

这是一个非常紧凑的结果：整个 $N^p$ 项的信号张量，塌缩成了未知单模式 $v$ 上的一个算符单项式。

4.5 物理图像：凝聚放大弱信号

$(b_v^{†}{)}^{p/2}(b_v{)}^{p/2}$ 这个算符做什么？把它作用在”全部 $n_{\mathrm{bos}}$ 个玻色子都占据模式 $v$“的凝聚态

$$|v;n_{\mathrm{bos}}⟩=\frac{(b_v^{†}{)}^{n_{\mathrm{bos}}}}{\sqrt{n_{\mathrm{bos}}!}}|0⟩$$

上：湮灭算符部分先把 $p/2$ 个玻色子从模式 $v$ 上移除，产生算符部分再放回去。利用 $(b_v{)}^m(b_v^{†}{)}^n|0⟩=\frac{n!}{(n-m)!}(b_v^{†}{)}^{n-m}|0⟩$（第 4.1 节的公式，取 $m=p/2$、$n=n_{\mathrm{bos}}$），得到期望值

$$⟨v;n_{\mathrm{bos}}|H_{\mathrm{signal}}|v;n_{\mathrm{bos}}⟩=\lambda N^{p/2}\frac{n_{\mathrm{bos}}!}{(n_{\mathrm{bos}}-p/2)!}=\lambda N^{p/2}{n}_{\mathrm{bos}}(n_{\mathrm{bos}}-1)\cdots (n_{\mathrm{bos}}-\frac{p}{2}+1).$$

当 $n_{\mathrm{bos}}\gg p$ 时，这个能量约为 $\lambda N^{p/2}{n}_{\mathrm{bos}}^{p/2}$。因式 $n_{\mathrm{bos}}^{p/2}$ 就是玻色增强 (bosonic enhancement)：信号能量随玻色子数幂次增长，而不是线性增长。直觉上，$p/2$ 个玻色子”协同”参与一次相互作用，参与方式有 $\sim n_{\mathrm{bos}}^{p/2}$ 种组合，且因为全同玻色子的对称性，这些贡献相干地相加。

相比之下，一个不沿着 $v$ 的态（例如随机方向的模式或分散在多个模式上的态）从信号项获得的能量要小得多。因此 $H(T)$ 的谱中出现一个信号主导的窗口：能量绝对值最大的本征态集中在与 $v$ 高度重叠的方向上。检测 spike 的问题被翻译成了谱问题。

4.6 噪声项的角色

把 $G$ 代入同一构造，$H(G)$ 是一个系数随机的多体算符——一个随机多体背景。它的贡献与信号的本质区别在于相干性：信号项的 $N^p$ 个系数有共同的可分解结构，在凝聚态上相干叠加；噪声项的系数符号随机，贡献按非相干方式（方差相加而非振幅相加）积累。这正是”凝聚能放大信噪比”的代数根源。增大 $n_{\mathrm{bos}}$ 时，信号窗口与噪声背景的能量分离被进一步拉开（其定量标度决定了第 8 节的参数选择），phase estimation 才有可分辨的目标。

5. 量子算法流水线

有了 Hamiltonian，算法本身是工具的标准组装。可概括为五步：

1. 初态制备：在 fixed-boson sector 制备易实现的 initial state 或其随机 ensemble（例如某个容易构造的占据数态，或若干随机模式的叠加）。初态不需要与 $v$ 有大 overlap——它只需不以概率 $1$ 完全避开信号子空间。
2. Hamiltonian simulation：用 tensor-access oracle（对张量元或张量块结构的查询访问）把 $H(T)$ block-encode 进一个更大的酉算符，再模拟 $e^{-itH(T)}$。技术细节见 block encoding 教程；这里的要点是模拟代价取决于 $H(T)$ 的访问模型与范数，而不是显式写出 $D$ 维矩阵。
3. Phase estimation：对 $e^{-itH(T)}$ 做 相位估计，把初态按 $H(T)$ 的能量本征值分解，标记 signal-dominated spectral window（能量绝对值足够大的窗口，即第 4.5 节由信号项拉开的谱区）。
4. Amplitude amplification：相位估计测量把态投影到该窗口的概率 $p_{\mathrm{hit}}$ 可能很小，用 振幅放大 把命中信号窗口的小振幅从”平均重复 $1/p_{\mathrm{hit}}$ 次”提升为”$1/\sqrt{p_{\mathrm{hit}}}$ 次”。
5. 读出：对得到的态测量一体 reduced density matrix

$${\Gamma }_{ij}=\frac{⟨a_i^{†}{a}_j⟩}{n_{\mathrm{bos}}},$$

其 principal eigenvector 估计 $v$。第 6 节解释为什么这个矩阵承载 $v$ 的信息。

最后一步有一个重要的成本提示：若要列出 $\hat{v}$ 的全部 $N$ 个坐标，仍需 $\Omega (N)$ 级 classical output（本质上是对 $\Gamma$ 做 tomography 再经典对角化，见 量子态层析教程）；若下游任务只需要计算 $\hat{v}$ 与某些给定向量的 overlap，则可以一直留在 quantum form，避免逐项读出。本词条 principal eigenvector 一篇对”量子态输出 vs 经典描述输出”的区分有更系统的讨论。

6. 读出：一体约化密度矩阵

为什么 $\Gamma$ 的主特征向量是 $v$？对理想情形直接计算。设算法产出的态接近完全凝聚态 $|v;n_{\mathrm{bos}}⟩$。先算单个湮灭算符的作用：由 $[a_j,b_v^{†}]=\frac{1}{\sqrt{N}}{\sum }_i{v}_i[a_j,a_i^{†}]=v_j/\sqrt{N}$（用对易关系与 $b_v^{†}$ 的定义）以及求导式的对易恒等式 $[a_j,(b_v^{†}{)}^n]=n\frac{v_j}{\sqrt{N}}(b_v^{†}{)}^{n-1}$，得

$$a_j|v;n_{\mathrm{bos}}⟩=\frac{1}{\sqrt{n_{\mathrm{bos}}!}}[a_j,(b_v^{†}{)}^{n_{\mathrm{bos}}}]|0⟩=\sqrt{n_{\mathrm{bos}}}\frac{v_j}{\sqrt{N}}|v;n_{\mathrm{bos}}-1⟩,$$

其中第一步用了 $a_j|0⟩=0$。于是

$$⟨a_i^{†}{a}_j⟩=⟨a_i\psi \mid a_j\psi ⟩=n_{\mathrm{bos}}\frac{v_i{v}_j}{N},$$

即

$$\Gamma =\frac{v{v}^T}{N}.$$

这是一个秩一矩阵，其唯一的非零 eigenvalue 为 $\frac{v^{T}v}{N}=1$，对应的 eigenvector 恰为 $v/\sqrt{N}$。完全凝聚态的一体密度矩阵精确地以 $v$ 为主特征向量；算法产出的态只要与凝聚态有高 overlap，$\Gamma$ 的主特征向量就与 $v$ 有非消失 overlap，满足第 2 节的弱恢复判据。

这里还藏着一个物理直觉：$\Gamma$ 是”单粒子可观测量”的期望矩阵。多体态本身可能很复杂，但如果玻色子显著地聚集在某个单粒子模式上，这个模式就会以主特征向量的形式在 $\Gamma$ 中暴露出来——这是玻色–爱因斯坦凝聚在密度矩阵层面的标准判据。量子算法做的正是”制备凝聚态、读取凝聚方向”。

7. 两次平方根从哪里来

与 classical spectral procedure 对比时，量子运行时间中有两个 quadratic gain，合计给出指数率上的 $1/4$：

• 第一个平方根：量子谱线性代数。classical spectral method 在 flattening 之后必须显式处理 $N^{p/2}\times N^{p/2}$（或对称化后 $D$ 维）的矩阵——存储、逐项构造、反复矩阵–向量乘法；quantum Hamiltonian simulation 在 $D$ 维空间中不显式保存或逐项乘巨大矩阵，谱信息通过 oracle 访问与相位估计间接提取。在论文的弱信号渐近分析中，这一替换把指数率常数压缩到原来的一半。
• 第二个平方根：amplitude amplification。命中信号谱窗的成功概率 $p_{\mathrm{hit}}$ 很小时，经典式的”失败就重来”平均需要 $1/p_{\mathrm{hit}}$ 次重复，amplitude amplification 把它降为 $1/\sqrt{p_{\mathrm{hit}}}$ 次——又贡献一个指数率常数上的一半。

论文在固定弱信号比例、适当取 $n_{\mathrm{bos}}$ 的渐近分析中得到

$$\frac{\log T_Q}{\log T_C}⟶\frac{1}{4},$$

即 quantum runtime 的指数率约为对应 classical spectral runtime 的四分之一，同时 quantum space 为 polynomial。

这个极限式的准确含义值得展开。若记 $T_C=\exp (A)$ 与 $T_Q=\exp (A/4+o(A))$（$A$ 是随弱信号参数增长的量），则 $\log T_Q/\log T_C\to 1/4$。也就是说，比较的不是运行时间的比值 $T_Q/T_C$（它依然指数巨大），而是”指数的比值”：量子算法把经典谱方法运行时间的指数砍掉了四分之三，两个平方根相乘得到四分之一。“四次方加速”一词指的就是这个指数率上的因子 $4$。

Warning

这是对特定 classical spectral family 和 oracle model 的结果，不是对所有 classical algorithms 的无条件 quartic lower bound。它不排除存在更强的经典算法（例如基于平方和或消息传递的方法在某些 regime 表现不同），也不承诺在任意张量访问模型下保持同样的加速。阅读或使用这一结论时，必须连同它的模型假设一起引用。

8. 参数与资源边界

$n_{\mathrm{bos}}$ 是放大弱 spike 的旋钮。由第 4.5 节，信号窗口的能量尺度随 $n_{\mathrm{bos}}^{p/2}$ 增长：信号越弱（$\lambda$ 越小），就需要更多玻色子把信号窗口从噪声背景中拉开。在论文的分析中，$n_{\mathrm{bos}}$ 随 ${\lambda }^{-1}$ polynomial 增长，而 runtime 对弱信号参数仍可能 exponential——“多项式空间”与”多项式时间”在此问题上是两回事，第 7 节的四次方结论砍的是指数的常数，不是把指数变成多项式。

实际资源还依赖以下每一项，逐项说明：

• tensor entry / block-encoding oracle 的实现：$H(T)$ 的模拟代价取决于张量如何被访问。若张量只能逐元查询，构造 oracle 本身可能要扫过 $N^p$ 个元素（见习题 4）；若有结构化的数据访问（如 QRAM 式的块访问），代价模型才支撑得起加速声明。
• $\Vert H(T)\Vert$、simulation time 与 phase-estimation precision：相位估计要把信号窗口与噪声背景在能量上区分开，所需能量分辨率决定了演化时间 $t$ 与查询次数，分辨率越精细代价越高。
• signal spectral window 和 noise gap：窗口宽度与间隙大小由 $n_{\mathrm{bos}}$、$\lambda$ 与噪声范数共同决定，是分析中最技术性的部分。
• initial overlap 及 amplitude-amplification 次数：$p_{\mathrm{hit}}$ 决定第二个平方根节省的绝对量级。
• 读出 $v$ 所需的 copies / tomography：每次运行只产出一个态副本，估计 $\Gamma$ 的 $O(N^2)$ 个矩阵元（或其主特征向量）需要重复整个流水线多次。

因此”polynomial quantum space”不等于近期硬件可运行：fixed-boson encoding 需要在多模式玻色系统（或等效的对称子空间编码）上精确控制，深 Hamiltonian simulation 和 fault-tolerant phase estimation 都是强要求。该算法的定位是理论上的复杂度分离结果，而非 NISQ 时代的候选应用。

9. $p=2$ 的 sanity check

把算法退回到 $p=2$ 是一个必要的健康检查：此时问题有已知答案（普通 PCA），量子构造必须复现它。

$p=2$ 时 $T=\lambda v{v}^T+G$ 是 spiked matrix，Hamiltonian 退化为

$$H(T)=\sum _{ij}{T}_{ij}{a}_i^{†}{a}_j.$$

在 single-boson sector（$n_{\mathrm{bos}}=1$），取基 $|i⟩:=a_i^{†}|0⟩$（$i=1,\dots ,N$，即”唯一玻色子在第 $i$ 个模式”）。计算 $H(T)$ 在此基下的矩阵元：由对易关系 $a_j{a}_k^{†}={\delta }_{jk}+a_k^{†}{a}_j$，

$$H(T)|j⟩=\sum _{ik}{T}_{ik}{a}_i^{†}{a}_k{a}_j^{†}|0⟩=\sum _{ik}{T}_{ik}{a}_i^{†}({\delta }_{kj}+a_j^{†}{a}_k)|0⟩=\sum _i{T}_{ij}|i⟩,$$

最后一步用了 $a_k|0⟩=0$（第二项消失）与 ${\delta }_{kj}$ 收起对 $k$ 的求和。于是

$$⟨i|H(T)|j⟩=T_{ij}:$$

在 single-boson sector，$a_i^{†}{a}_j$ 就是 $|i⟩⟨j|$，故 $H(T)$ 与矩阵 $T$ 相同。 Phase estimation 寻找 principal eigenstate，恢复普通 PCA。高阶算法可视为把这一 spectral idea 延伸到 symmetric many-boson space：$n_{\mathrm{bos}}=1$ 时它就是 PCA，$n_{\mathrm{bos}}>1$ 时玻色增强机制（第 4.5 节）开始起作用。

10. 一个可手算的小例子

取最小非平凡的配置：$N=2$ 个模式、$n_{\mathrm{bos}}=2$ 个玻色子，隐藏方向 $v=(1,1)$（满足 $\Vert v\Vert =\sqrt{2}=\sqrt{N}$），并暂时令噪声 $G=0$、$\lambda =1$、$p=2$，即 $T=v{v}^T=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$。

第一步：对称 sector 的维数与基。 由 stars and bars，

$$D=\left(\genfrac{}{}{0ex}{}{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}\right)=\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3,$$

三个 Fock 基态为 $|2,0⟩,|1,1⟩,|0,2⟩$。

第二步：写出凝聚态。 组合模式 $b_v^{†}=\frac{1}{\sqrt{2}}(a_1^{†}+a_2^{†})$，凝聚态为

$$|v;2⟩=\frac{(b_v^{†}{)}^2}{\sqrt{2!}}|0⟩=\frac{1}{2\sqrt{2}}((a_1^{†}{)}^2+2a_1^{†}{a}_2^{†}+(a_2^{†}{)}^2)|0⟩.$$

用归一化的占据数基 $|2,0⟩=\frac{(a_1^{†}{)}^2}{\sqrt{2}}|0⟩$、$|1,1⟩=a_1^{†}{a}_2^{†}|0⟩$、$|0,2⟩=\frac{(a_2^{†}{)}^2}{\sqrt{2}}|0⟩$ 改写：

$$|v;2⟩=\frac{1}{2}|2,0⟩+\frac{1}{\sqrt{2}}|1,1⟩+\frac{1}{2}|0,2⟩.$$

检查归一化：$\frac{1}{4}+\frac{1}{2}+\frac{1}{4}=1$。系数 $\left(\frac{1}{2},\frac{1}{\sqrt{2}},\frac{1}{2}\right)$ 正是二项分布 $\left(\genfrac{}{}{0ex}{}{2}{k}\right)/2^2$ 的平方根——凝聚态在占据数基下是二项式叠加，每个玻色子独立地以均等概率落在两个模式上。

第三步：验证信号能量。 由第 4.5 节的公式（$N=2$、$p=2$、$\lambda =1$、$n_{\mathrm{bos}}=2$），

$$⟨v;2|H_{\mathrm{signal}}|v;2⟩=\lambda N^{p/2}\frac{n_{\mathrm{bos}}!}{(n_{\mathrm{bos}}-1)!}=1\cdot 2\cdot 2=4.$$

也可以直接验证：$p=2$ 时 $H_{\mathrm{signal}}=N{b}_v^{†}{b}_v=2{\hat{n}}_v$，其中 ${\hat{n}}_v=b_v^{†}{b}_v$ 是模式 $v$ 的数算符，而凝聚态是它的本征态（本征值 $n_{\mathrm{bos}}=2$），故期望值为 $2\times 2=4$，一致。

第四步：计算一体密度矩阵并读出 $v$。 逐个矩阵元计算。对角元是平均占据数：

$$⟨a_1^{†}{a}_1⟩=2\cdot \frac{1}{4}+1\cdot \frac{1}{2}+0\cdot \frac{1}{4}=1,⟨a_2^{†}{a}_2⟩=1\text{（同理）}.$$

非对角元：$a_1^{†}{a}_2|1,1⟩=a_1^{†}|1,0⟩=\sqrt{2}|2,0⟩$，且 $a_1^{†}{a}_2|0,2⟩=\sqrt{2}{a}_1^{†}|0,1⟩=\sqrt{2}|1,1⟩$，所以

$$a_1^{†}{a}_2|v;2⟩=\frac{1}{\sqrt{2}}\cdot \sqrt{2}|2,0⟩+\frac{1}{2}\cdot \sqrt{2}|1,1⟩=|2,0⟩+\frac{1}{\sqrt{2}}|1,1⟩,$$

与 $⟨v;2|=\frac{1}{2}⟨2,0|+\frac{1}{\sqrt{2}}⟨1,1|+\frac{1}{2}⟨0,2|$ 作内积得

$$⟨a_1^{†}{a}_2⟩=\frac{1}{2}\cdot 1+\frac{1}{\sqrt{2}}\cdot \frac{1}{\sqrt{2}}=\frac{1}{2}+\frac{1}{2}=1.$$

于是

$$\Gamma =\frac{1}{n_{\mathrm{bos}}}\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)=\frac{v{v}^T}{N},$$

其特征值为 $1$ 与 $0$，principal eigenvector 为 $\frac{1}{\sqrt{2}}(1,1)=v/\sqrt{N}$。与第 6 节的一般公式 $\Gamma =v{v}^T/N$ 精确吻合：即使只有 $2$ 个模式、$2$ 个玻色子，读出机制也完整工作。

11. 小结与习题

• Spiked tensor PCA 从 $T=\lambda v^{\otimes p}+G$ 恢复隐藏方向，成功标准是与 $v$ 有非消失 overlap 的弱恢复。
• 当 $p\ge 3$ 时张量没有普适谱定理，且存在统计–计算鸿沟：信息论可恢复的信号强度低于已知多项式时间经典算法所需的强度。
• 经典谱方法用 flattening 把张量摊成 $N^{p/2}\times N^{p/2}$ 矩阵，代价是必须显式处理指数维空间。
• Tensor 被映射为 fixed-boson symmetric sector（维数 $D=\left(\genfrac{}{}{0ex}{}{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}\right)$）中的多体 Hamiltonian；信号项精确等于 $\lambda N^{p/2}(b_v^{†}{)}^{p/2}(b_v{)}^{p/2}$，玻色凝聚把弱信号相干放大。
• 流水线 = 初态制备 + Hamiltonian simulation + phase estimation（标记信号谱窗）+ amplitude amplification + 一体密度矩阵读出。
• Hamiltonian simulation 与 amplitude amplification 各贡献一次平方根改善，合计 $\log T_Q/\log T_C\to 1/4$。
• Quartic 指数率结论依赖 Gaussian model、normalization、访问模型和比较对象；它是复杂度分离结果，不是无条件加速下界，也不代表近期可实现。

习题

1. 计算 $N=4,n_{\mathrm{bos}}=3$ 时 symmetric sector 的维数（用 stars and bars 公式），并列出一种把它映射到 qubit 对称子空间时需要多少个 qubit 的估算方式。
2. 验证 signal Hamiltonian 可写成 $b_v$ 的多项式：从 $H_{\mathrm{signal}}=\lambda ({\sum }_i{v}_i{a}_i^{†}{)}^{p/2}({\sum }_j{v}_j{a}_j{)}^{p/2}$ 出发，明确指出每一步用了哪条对易关系，并说明 $p$ 为奇数时这个构造在哪里失效。
3. 对 $p=2$ 推导一体 density matrix 的 principal eigenvector 与 $v$ 对齐（沿第 6 节的路线，补全 $[a_j,(b_v^{†}{)}^n]=n\frac{v_j}{\sqrt{N}}(b_v^{†}{)}^{n-1}$ 的归纳证明）。
4. 列出若 tensor 以普通磁盘数组给出，oracle 构造会增加的成本：构造 block encoding 前需要多少次元素读取？这对第 7 节的加速声明意味着什么？
5. 对第 10 节的例子（$N=2$、$v=(1,1)$）取 $n_{\mathrm{bos}}=3$，写出凝聚态在占据数基下的展开，并验证 $⟨a_1^{†}{a}_1⟩=\frac{3}{2}$、$\Gamma =\frac{v{v}^T}{2}$。（提示：系数是 $\left(\genfrac{}{}{0ex}{}{3}{k}\right)/2^3$ 的平方根。）
6. 设 $T_C=\exp (A)$、$T_Q=\exp (A/4)$。验证 $\log T_Q/\log T_C=1/4$，并取 $A=40$ 算出 $T_C$ 与 $T_Q$ 的量级；用此例向同学解释为什么”指数率改善为四分之一”不等于”快四倍”，以及为什么该结论不排斥存在更强的经典算法。

参考文献与 Zoo 覆盖

• Zoo 编号 424：Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray, Xin Wang, S. Chakraborty 与 S. Lloyd, Quantum algorithms for the tensor principal component problem。
• 本词条对应 Zoo 的“Tensor principal component analysis”条目；复杂度陈述采用论文的 spiked-tensor normalization 与 fixed-boson 渐近条件。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch15-learning-spectral/tensor-pca
• 内容遵循 CC BY-NC-SA 4.0 许可协议