# Tensor PCA：Spiked Tensor、Bosonic Hamiltonian 与四次方加速 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（四次方）的指数率改善。 本教程面向已学过本站第 1–8 章的读者。我们会用到 [相位估计](../ch03-algo-basics/phase-estimation.md)、[振幅放大](../ch03-algo-basics/amplitude-amplification.md) 与 [Hamiltonian simulation / block encoding](../ch05-hamiltonian-qsp/block-encoding-tutorial.md) 作为黑盒工具，引用时只做回顾、不再重新推导。 :::{admonition} 本课知识点 :class: tip 1. **[张量 PCA 的困难与统计–计算鸿沟](#tensor-pca-gap)**——能列出张量相对矩阵失去的谱性质与收敛保证，并解释统计–计算鸿沟如何把“信息论可恢复”与“经典多项式时间可恢复”区分开。 2. **[Spiked tensor 模型与弱恢复](#spiked-tensor-model)**——能写出观测模型 $T=\lambda v^{\otimes p}+G$、归一化约定 $\|v\|=\sqrt N$ 与弱恢复判据，并解释信号缩放 $\lambda=\alpha N^{-p/4}$ 为何刻画 flattening 谱方法的能力边界。 3. **[Flattening 经典谱方法及其代价](#flattening-spectral-cost)**——能把偶数阶对称张量摊成 $N^{p/2}\times N^{p/2}$ 矩阵并写出 spike 方向 $v^{\otimes p/2}$，计算其显式存储与乘法代价，并说明量子态为何能隐式表示同一空间。 4. **[Fock 空间与对称子空间](#fock-symmetric-sector)**——能用产生湮灭算符与占据数写出 Fock 基态，说明 fixed-boson sector 与对称子空间的等价，并用 stars and bars 推导维数 $D=\binom{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}$。 5. **[Hamiltonian 构造与玻色增强](#signal-hamiltonian-boost)**——能把张量系数组装成 number-preserving 的厄米算符 $H(T)$，推导信号项 $\lambda N^{p/2}(b_v^\dagger)^{p/2}(b_v)^{p/2}$，并解释玻色增强因子 $n_{\mathrm{bos}}^{p/2}$ 为何相干地放大弱信号。 6. **[量子算法流水线与读出](#pipeline-readout)**——能按顺序列出五步流水线并说明各步所用的量子工具，推导完全凝聚态的一体约化密度矩阵 $\Gamma=vv^{T}/N$，并说明其主特征向量如何给出 $v$ 的弱恢复估计。 7. **[四次方指数率与资源边界](#quartic-rate-resources)**——能指出两个平方根改善各自的来源，解释 $\log T_Q/\log T_C\to\frac14$ 比较的是指数率而非时间比值，并列出结论依赖的访问模型与资源假设。 8. **[$p=2$ 校验与手算小例子](#p2-sanity-check)**——能在 single-boson sector 验证 $p=2$ 时 $H(T)$ 与矩阵 $T$ 相同，并在 $N=2$、$n_{\mathrm{bos}}=2$ 的例子中手算凝聚态展开、信号能量与 $\Gamma$ 的读出。 ::: ## 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}, \qquad \langle u_i,u_j\rangle=\delta_{ij}, $$ 于是 $u_1$ 可以用 power iteration 求得：从随机向量 $x$ 出发反复计算 $x\leftarrow Mx/\|Mx\|$，只要 $|\mu_1|>|\mu_2|$ 且初态与 $u_1$ 不正交，就几何速度收敛。每次迭代是一次矩阵–向量乘法，稠密情形下代价 $O(N^2)$。这一切之所以简单，是因为矩阵有谱定理：特征向量张成整个空间，power iteration 只是在"放大最大特征方向的分量"。 ### 1.2 Spiked matrix 与相变现象 一个更有统计味道的问题是 **spiked matrix** 模型：观测矩阵是一个隐藏的秩一信号加上随机噪声， $$ M=\mu\, uu^{T}+W, $$ 其中 $\|u\|=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 节）能用，但要付出维度膨胀的代价。 然而，统计物理风格的随机模型告诉我们，困难与不可能之间有一条鸿沟，这正是本教程问题的舞台。 (tensor-pca-gap)= ### 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 的主场。 (spiked-tensor-model)= ## 2. Spiked tensor 模型 现在给出问题的形式化定义。考虑 order-$p$ 的 symmetric tensor（指标任意置换下不变的张量） $$ T=T_0=\lambda v^{\otimes p}+G, \qquad v\in\mathbb R^N, \qquad \|v\|=\sqrt N, $$ 其中各符号的含义是： - $v^{\otimes p}$ 是 $v$ 的 $p$ 次张量积，即 $(v^{\otimes p})_{i_1\ldots i_p}=v_{i_1}v_{i_2}\cdots v_{i_p}$； - $\|v\|=\sqrt N$ 是归一化约定：它使得 $v$ 的典型分量是 $O(1)$ 量级（例如 $v=(1,1,\ldots,1)$），从而 $v^{\otimes p}$ 的典型元素也是 $O(1)$，不同 $N$ 之间可以公平比较； - $G_{i_1\ldots i_p}$ 是适当归一化的 Gaussian noise（独立高斯元，方差按问题的缩放选好）； - $\lambda\ge 0$ 是 signal strength（信噪比旋钮）。 **恢复目标**不是逐项恢复 $v$（弱信号下这不可能），而是输出一个 estimator $\widehat v$，它与 $v$ 有非消失的归一化 overlap： $$ \frac{|\langle\widehat v,v\rangle|}{\|\widehat v\|\,\|v\|}\ge c>0, $$ 其中 $c$ 是与 $N$ 无关的常数。这叫**弱恢复 (weak recovery)**：只要输出方向与真方向有恒定相关性，就算成功——它远弱于 $\|\widehat v-v\|\to 0$ 的强恢复，但在统计上已经有意义（例如可以作为后续局部算法的初始化）。 **信号强度的缩放**。统计上与计算上可恢复的 threshold 不一定相同（第 1.4 节的鸿沟）。所讨论的量子算法关注 classical spectral regime 附近的弱信号区域，常写 $$ \lambda=\alpha N^{-p/4}, $$ 其中 $\alpha$ 是不随 $N$ 增长的参数。这个指数 $-p/4$ 不是随意的：在 $\|v\|=\sqrt N$ 的约定下，它正是 flattening 类谱方法"勉强还能工作"的信号尺度，因此把算法放在这个 scaling 下比较，比的是各方法在**各自能力边界附近**的表现。 ```{warning} 这里的 normalization 很重要；改变 $G$ 或 $v$ 的尺度会改变表面 threshold。文献中另一种常见约定是 $\|v\|=1$ 并把噪声方差写成 $1/N$ 级别，两种约定下阈值的具体数值看起来完全不同，但物理内容一致。比较不同工作的复杂度结论时，第一步永远是核对归一化。 ``` (flattening-spectral-cost)= ## 3. 为什么经典谱方法先想到 flattening 既然张量没有谱定理，经典谱方法的自然策略是把张量**摊回矩阵**。当 $p$ 为偶数，把前 $p/2$ 个 indices 合并为一个"大行指标"、后 $p/2$ 个合并为一个"大列指标"，得到矩阵 $$ M_{(i_1\ldots i_{p/2}),(i_{p/2+1}\ldots i_p)} =T_{i_1\ldots i_p}. $$ 这就是张量的一个 **flattening**（也叫 unfolding 或 matricization）。大行指标取遍 $N^{p/2}$ 种组合，所以 $M$ 的维数是 $N^{p/2}\times N^{p/2}$。关键观察是 spike 项摊成了秩一矩阵：由 $(v^{\otimes p})_{i_1\ldots i_p}=v_{i_1}\cdots v_{i_p}$ 可以分离变量， $$ \lambda\,v^{\otimes p} \;\xrightarrow{\ \text{flatten}\ }\; \lambda\,\big(v^{\otimes p/2}\big)\big(v^{\otimes p/2}\big)^{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 p2\log_2 N$ 个 qubit。下一个问题是如何把 $T$ 本身变成作用在该空间上的算符。 ## 4. 从张量到 bosonic Hamiltonian (fock-symmetric-sector)= ### 4.1 Fock 空间与产生湮灭算符 引入 $N$ 个 modes（模式）的 creation/annihilation operators $a_i^\dagger,a_i$，满足正则对易关系 (canonical commutation relations) $$ [a_i,a_j^\dagger]=\delta_{ij}, \qquad [a_i,a_j]=[a_i^\dagger,a_j^\dagger]=0. $$ 真空态 $|0\rangle$ 被所有湮灭算符消灭：$a_i|0\rangle=0$。一般的 Fock 基态由**占据数 (occupation numbers)** 标记： $$ |n_1,n_2,\ldots,n_N\rangle =\prod_{i=1}^{N}\frac{(a_i^\dagger)^{n_i}}{\sqrt{n_i!}}\,|0\rangle, \qquad n_i\in\{0,1,2,\ldots\}, $$ 表示第 $i$ 个模式上有 $n_i$ 个玻色子。分母 $\sqrt{n_i!}$ 是归一化因子，它来自对易关系的反复使用：$(a_i)^m(a_i^\dagger)^{n}|0\rangle=\frac{n!}{(n-m)!}(a_i^\dagger)^{n-m}|0\rangle$（当 $m\le n$）。 数算符 $\hat n_i=a_i^\dagger a_i$ 测量第 $i$ 个模式的占据数：$\hat n_i|n_1,\ldots,n_N\rangle=n_i|n_1,\ldots,n_N\rangle$。我们固定总 boson 数 $$ \sum_{i=1}^N a_i^\dagger a_i=n_{\mathrm{bos}}, $$ 即只在这个总粒子数算符的某个本征子空间——称为 **fixed-boson sector**——内工作。 ### 4.2 Fixed-boson sector 就是对称子空间 这个 sector 等价于 $n_{\mathrm{bos}}$ 个 $N$ 维 qudits 的 symmetric subspace（在任意置换下不变的张量积态构成的子空间）。等价关系是具体的：把占据数态 $|n_1,\ldots,n_N\rangle$ 对应到"第 $i$ 个 qudit 取值 $i$ 出现 $n_i$ 次"的对称化张量积态。 该 sector 的维数等于方程 $n_1+\cdots+n_N=n_{\mathrm{bos}}$ 的非负整数解个数，由 stars and bars（隔板法）计数为 $$ D=\binom{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}. $$ 推导一下：把 $n_{\mathrm{bos}}$ 个不可区分的"星"（玻色子）排成一行，用 $N-1$ 块"隔板"把它们分成 $N$ 组（允许空组），第 $i$ 组的星数就是 $n_i$。星与隔板共 $n_{\mathrm{bos}}+N-1$ 个位置，从中选出 $n_{\mathrm{bos}}$ 个放星（等价地，$N-1$ 个放隔板），方案数即 $\binom{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}$。每个方案唯一对应一个 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 正是"对称子空间维数随副本数多项式增长"的定量表达。 (signal-hamiltonian-boost)= ### 4.3 Hamiltonian 的构造 对偶数 $p$，用 tensor 系数定义 number-preserving 的 $p$-body interaction（略去 normalization 常数） $$ H(T)=\sum_{i_1,\ldots,i_p} T_{i_1\ldots i_p} a_{i_1}^\dagger\cdots a_{i_{p/2}}^\dagger 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)^\dagger=H(T)$。这是把它当作 Hamiltonian 来模拟的前提。 ### 4.4 信号项的化简：完整推导 若 $T=\lambda v^{\otimes p}$（暂时忽略噪声），则 $T_{i_1\ldots i_p}=\lambda v_{i_1}\cdots v_{i_p}$，求和完全分离变量： $$ H_{\mathrm{signal}} =\lambda\sum_{i_1,\ldots,i_p}v_{i_1}\cdots v_{i_p}\, a_{i_1}^\dagger\cdots a_{i_{p/2}}^\dagger a_{i_{p/2+1}}\cdots a_{i_p} =\lambda\left(\sum_{i}v_i a_i^\dagger\right)^{p/2}\left(\sum_{j}v_j a_j\right)^{p/2}. $$ 第二步成立的理由：所有产生算符彼此对易（$[a_i^\dagger,a_j^\dagger]=0$），所有湮灭算符彼此对易（$[a_i,a_j]=0$），所以 $\left(\sum_i v_i a_i^\dagger\right)^{p/2}$ 按多项式定理展开后逐项正是 $v_{i_1}\cdots v_{i_{p/2}}a_{i_1}^\dagger\cdots a_{i_{p/2}}^\dagger$，与上式的产生算符部分一一对应；湮灭部分同理。 现在定义归一化的**组合模式算符** $$ b_v^\dagger=\frac1{\sqrt N}\sum_i v_i a_i^\dagger, \qquad b_v=\frac1{\sqrt N}\sum_i v_i a_i. $$ 它确实是一个合法的玻色模式，即满足单模正则对易关系。验证： $$ [b_v,b_v^\dagger] =\frac1N\sum_{i,j}v_iv_j\,[a_i,a_j^\dagger] =\frac1N\sum_{i,j}v_iv_j\,\delta_{ij} =\frac1N\sum_i v_i^2 =\frac{\|v\|^2}{N}=1, $$ 其中第一步用了对易关系的双线性与 $[a_i,a_j^\dagger]=\delta_{ij}$，最后一步用了归一化约定 $\|v\|=\sqrt N$。这正是该约定的深层原因：它让 $v$ 方向上的组合模式成为标准的玻色模式。 于是 $\sum_i v_i a_i^\dagger=\sqrt N\,b_v^\dagger$，代入得 $$ H_{\mathrm{signal}}=\lambda\, N^{p/2}\,(b_v^\dagger)^{p/2}(b_v)^{p/2}. $$ 这是一个非常紧凑的结果：**整个 $N^p$ 项的信号张量，塌缩成了未知单模式 $v$ 上的一个算符单项式**。 ### 4.5 物理图像：凝聚放大弱信号 $(b_v^\dagger)^{p/2}(b_v)^{p/2}$ 这个算符做什么？把它作用在"全部 $n_{\mathrm{bos}}$ 个玻色子都占据模式 $v$"的凝聚态 $$ |v;n_{\mathrm{bos}}\rangle=\frac{(b_v^\dagger)^{n_{\mathrm{bos}}}}{\sqrt{n_{\mathrm{bos}}!}}\,|0\rangle $$ 上：湮灭算符部分先把 $p/2$ 个玻色子从模式 $v$ 上移除，产生算符部分再放回去。利用 $(b_v)^{m}(b_v^\dagger)^{n}|0\rangle=\frac{n!}{(n-m)!}(b_v^\dagger)^{n-m}|0\rangle$（第 4.1 节的公式，取 $m=p/2$、$n=n_{\mathrm{bos}}$），得到期望值 $$ \langle v;n_{\mathrm{bos}}|\,H_{\mathrm{signal}}\,|v;n_{\mathrm{bos}}\rangle =\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\Big(n_{\mathrm{bos}}-\frac p2+1\Big). $$ 当 $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 才有可分辨的目标。 (pipeline-readout)= ## 5. 量子算法流水线 有了 Hamiltonian，算法本身是第 3–8 章工具的标准组装。可概括为五步： 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 教程](../ch05-hamiltonian-qsp/block-encoding-tutorial.md)；这里的要点是模拟代价取决于 $H(T)$ 的访问模型与范数，而不是显式写出 $D$ 维矩阵。 3. **Phase estimation**：对 $e^{-itH(T)}$ 做 [相位估计](../ch03-algo-basics/phase-estimation.md)，把初态按 $H(T)$ 的能量本征值分解，标记 signal-dominated spectral window（能量绝对值足够大的窗口，即第 4.5 节由信号项拉开的谱区）。 4. **Amplitude amplification**：相位估计测量把态投影到该窗口的概率 $p_{\mathrm{hit}}$ 可能很小，用 [振幅放大](../ch03-algo-basics/amplitude-amplification.md) 把命中信号窗口的小振幅从"平均重复 $1/p_{\mathrm{hit}}$ 次"提升为"$1/\sqrt{p_{\mathrm{hit}}}$ 次"。 5. **读出**：对得到的态测量一体 reduced density matrix $$ \Gamma_{ij}=\frac{\langle a_i^\dagger a_j\rangle}{n_{\mathrm{bos}}}, $$ 其 principal eigenvector 估计 $v$。第 6 节解释为什么这个矩阵承载 $v$ 的信息。 最后一步有一个重要的成本提示：若要列出 $\widehat v$ 的全部 $N$ 个坐标，仍需 $\Omega(N)$ 级 classical output（本质上是对 $\Gamma$ 做 tomography 再经典对角化，见 [量子态层析教程](../ch07-quantum-info/quantum-state-tomography-tutorial.md)）；若下游任务只需要计算 $\widehat v$ 与某些给定向量的 overlap，则可以一直留在 quantum form，避免逐项读出。本章 [principal eigenvector](principal-eigenvector.md) 一篇对"量子态输出 vs 经典描述输出"的区分有更系统的讨论。 ## 6. 读出：一体约化密度矩阵 为什么 $\Gamma$ 的主特征向量是 $v$？对理想情形直接计算。设算法产出的态接近完全凝聚态 $|v;n_{\mathrm{bos}}\rangle$。先算单个湮灭算符的作用：由 $[a_j,b_v^\dagger]=\frac{1}{\sqrt N}\sum_i v_i[a_j,a_i^\dagger]=v_j/\sqrt N$（用对易关系与 $b_v^\dagger$ 的定义）以及求导式的对易恒等式 $[a_j,(b_v^\dagger)^n]=n\,\frac{v_j}{\sqrt N}(b_v^\dagger)^{n-1}$，得 $$ a_j\,|v;n_{\mathrm{bos}}\rangle =\frac{1}{\sqrt{n_{\mathrm{bos}}!}}\,[a_j,(b_v^\dagger)^{n_{\mathrm{bos}}}]|0\rangle =\sqrt{n_{\mathrm{bos}}}\,\frac{v_j}{\sqrt N}\,|v;n_{\mathrm{bos}}-1\rangle, $$ 其中第一步用了 $a_j|0\rangle=0$。于是 $$ \langle a_i^\dagger a_j\rangle =\langle a_i\,\psi\mid a_j\,\psi\rangle =n_{\mathrm{bos}}\,\frac{v_i v_j}{N}, $$ 即 $$ \Gamma=\frac{v v^{T}}{N}. $$ 这是一个秩一矩阵，其唯一的非零 eigenvalue 为 $\frac{v^Tv}{N}=1$，对应的 eigenvector 恰为 $v/\sqrt N$。**完全凝聚态的一体密度矩阵精确地以 $v$ 为主特征向量**；算法产出的态只要与凝聚态有高 overlap，$\Gamma$ 的主特征向量就与 $v$ 有非消失 overlap，满足第 2 节的弱恢复判据。 这里还藏着一个物理直觉：$\Gamma$ 是"单粒子可观测量"的期望矩阵。多体态本身可能很复杂，但如果玻色子显著地聚集在某个单粒子模式上，这个模式就会以主特征向量的形式在 $\Gamma$ 中暴露出来——这是玻色–爱因斯坦凝聚在密度矩阵层面的标准判据。量子算法做的正是"制备凝聚态、读取凝聚方向"。 (quartic-rate-resources)= ## 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}\longrightarrow\frac14, $$ 即 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$ 个元素（见练习 7）；若有结构化的数据访问（如 QRAM 式的块访问），代价模型才支撑得起加速声明。 - **$\|H(T)\|$、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 时代的候选应用。 (p2-sanity-check)= ## 9. $p=2$ 的 sanity check 把算法退回到 $p=2$ 是一个必要的健康检查：此时问题有已知答案（普通 PCA），量子构造必须复现它。 $p=2$ 时 $T=\lambda vv^T+G$ 是 spiked matrix，Hamiltonian 退化为 $$ H(T)=\sum_{ij}T_{ij}a_i^\dagger a_j. $$ 在 single-boson sector（$n_{\mathrm{bos}}=1$），取基 $|i\rangle:=a_i^\dagger|0\rangle$（$i=1,\ldots,N$，即"唯一玻色子在第 $i$ 个模式"）。计算 $H(T)$ 在此基下的矩阵元：由对易关系 $a_ja_k^\dagger=\delta_{jk}+a_k^\dagger a_j$， $$ H(T)|j\rangle =\sum_{ik}T_{ik}\,a_i^\dagger a_k a_j^\dagger|0\rangle =\sum_{ik}T_{ik}\,a_i^\dagger\big(\delta_{kj}+a_j^\dagger a_k\big)|0\rangle =\sum_i T_{ij}\,|i\rangle, $$ 最后一步用了 $a_k|0\rangle=0$（第二项消失）与 $\delta_{kj}$ 收起对 $k$ 的求和。于是 $$ \langle i|H(T)|j\rangle=T_{ij}: $$ **在 single-boson sector，$a_i^\dagger a_j$ 就是 $|i\rangle\langle 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)$（满足 $\|v\|=\sqrt2=\sqrt N$），并暂时令噪声 $G=0$、$\lambda=1$、$p=2$，即 $T=vv^T=\begin{pmatrix}1&1\\1&1\end{pmatrix}$。 **第一步：对称 sector 的维数与基。** 由 stars and bars， $$ D=\binom{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}=\binom{3}{2}=3, $$ 三个 Fock 基态为 $|2,0\rangle,|1,1\rangle,|0,2\rangle$。 **第二步：写出凝聚态。** 组合模式 $b_v^\dagger=\frac{1}{\sqrt2}(a_1^\dagger+a_2^\dagger)$，凝聚态为 $$ |v;2\rangle=\frac{(b_v^\dagger)^2}{\sqrt{2!}}|0\rangle =\frac{1}{2\sqrt2}\big((a_1^\dagger)^2+2a_1^\dagger a_2^\dagger+(a_2^\dagger)^2\big)|0\rangle. $$ 用归一化的占据数基 $|2,0\rangle=\frac{(a_1^\dagger)^2}{\sqrt2}|0\rangle$、$|1,1\rangle=a_1^\dagger a_2^\dagger|0\rangle$、$|0,2\rangle=\frac{(a_2^\dagger)^2}{\sqrt2}|0\rangle$ 改写： $$ |v;2\rangle=\frac12|2,0\rangle+\frac{1}{\sqrt2}|1,1\rangle+\frac12|0,2\rangle. $$ 检查归一化：$\frac14+\frac12+\frac14=1$。系数 $\left(\frac12,\frac{1}{\sqrt2},\frac12\right)$ 正是二项分布 $\binom{2}{k}/2^2$ 的平方根——**凝聚态在占据数基下是二项式叠加**，每个玻色子独立地以均等概率落在两个模式上。 **第三步：验证信号能量。** 由第 4.5 节的公式（$N=2$、$p=2$、$\lambda=1$、$n_{\mathrm{bos}}=2$）， $$ \langle v;2|H_{\mathrm{signal}}|v;2\rangle=\lambda N^{p/2}\frac{n_{\mathrm{bos}}!}{(n_{\mathrm{bos}}-1)!}=1\cdot2\cdot2=4. $$ 也可以直接验证：$p=2$ 时 $H_{\mathrm{signal}}=N\,b_v^\dagger b_v=2\,\hat n_v$，其中 $\hat n_v=b_v^\dagger b_v$ 是模式 $v$ 的数算符，而凝聚态是它的本征态（本征值 $n_{\mathrm{bos}}=2$），故期望值为 $2\times2=4$，一致。 **第四步：计算一体密度矩阵并读出 $v$。** 逐个矩阵元计算。对角元是平均占据数： $$ \langle a_1^\dagger a_1\rangle=2\cdot\tfrac14+1\cdot\tfrac12+0\cdot\tfrac14=1, \qquad \langle a_2^\dagger a_2\rangle=1\ \text{（同理）}. $$ 非对角元：$a_1^\dagger a_2|1,1\rangle=a_1^\dagger|1,0\rangle=\sqrt2\,|2,0\rangle$，且 $a_1^\dagger a_2|0,2\rangle=\sqrt2\,a_1^\dagger|0,1\rangle=\sqrt2\,|1,1\rangle$，所以 $$ a_1^\dagger a_2\,|v;2\rangle =\frac{1}{\sqrt2}\cdot\sqrt2\,|2,0\rangle+\frac12\cdot\sqrt2\,|1,1\rangle =|2,0\rangle+\frac{1}{\sqrt2}|1,1\rangle, $$ 与 $\langle v;2|=\frac12\langle2,0|+\frac{1}{\sqrt2}\langle1,1|+\frac12\langle0,2|$ 作内积得 $$ \langle a_1^\dagger a_2\rangle=\frac12\cdot1+\frac{1}{\sqrt2}\cdot\frac{1}{\sqrt2}=\frac12+\frac12=1. $$ 于是 $$ \Gamma=\frac{1}{n_{\mathrm{bos}}}\begin{pmatrix}1&1\\1&1\end{pmatrix} =\frac12\begin{pmatrix}1&1\\1&1\end{pmatrix} =\frac{vv^T}{N}, $$ 其特征值为 $1$ 与 $0$，principal eigenvector 为 $\frac{1}{\sqrt2}(1,1)=v/\sqrt N$。与第 6 节的一般公式 $\Gamma=vv^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=\binom{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}$）中的多体 Hamiltonian；信号项精确等于 $\lambda N^{p/2}(b_v^\dagger)^{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【张量 PCA 的困难与统计–计算鸿沟】**（→ [1.4 节](#tensor-pca-gap)） 1. 列出第 1.3 节总结的张量 PCA 的三条困难，并说明为什么任何高效算法都必须利用输入的统计结构。 2. 比较 spiked matrix 的 BBP 相变与 spiked tensor 的统计–计算鸿沟：两者的“谱方法失效边界”各精确到什么程度？鸿沟两侧的阈值分别由哪类算法刻画？ > 提示：从第 1.4 节列出的三类多项式时间经典算法出发。 **练习 2【Spiked tensor 模型与弱恢复】**（→ [第 2 节](#spiked-tensor-model)） 1. 设 $p=4$、$\lambda=\alpha N^{-p/4}$。取 $N=10^4$、$\alpha=1$，计算 $\lambda$；若希望 $\lambda$ 保持在 $10^{-2}$，$\alpha$ 应取多少？ 2. 写出弱恢复判据，并说明它与 $\|\widehat v-v\|\to 0$ 的强恢复有何差别、为什么弱恢复的输出仍可作为后续局部算法的初始化。 3. 解释为什么比较不同文献的阈值结论时“第一步永远是核对归一化”，并说明 $\|v\|=\sqrt N$ 与 $\|v\|=1$ 两种约定下表面阈值为何看起来不同。 **练习 3【Flattening 经典谱方法及其代价】**（→ [第 3 节](#flattening-spectral-cost)） 1. 取 $p=4$、$N=10$：写出 flattening 矩阵的维数、显式存储所需的元素个数，以及 spike 方向所在的向量空间。 2. 从 $(v^{\otimes p})_{i_1\ldots i_p}=v_{i_1}\cdots v_{i_p}$ 出发，证明 spike 项摊平后是秩一矩阵 $\lambda\,(v^{\otimes p/2})(v^{\otimes p/2})^{T}$，并解释经典算法为何必须为 $N^{p/2}$ 维空间显式买单，而 $\frac p2\log_2 N$ 个 qubit 的量子态可以隐式表示它。 > 提示：乘积结构允许按前、后一半指标分离变量。 **练习 4【Fock 空间与对称子空间】**（→ [4.1 节](#fock-symmetric-sector)） 1. 由正则对易关系验证 $a\,(a^\dagger)^2|0\rangle=2\,a^\dagger|0\rangle$，并据此说明 Fock 基态中归一化因子 $\sqrt{n_i!}$ 的来源。 2. 取 $N=3$、$n_{\mathrm{bos}}=2$：列出全部占据数基态，并验证 $D=\binom{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}=6$。 3. 计算 $N=4,n_{\mathrm{bos}}=3$ 时 symmetric sector 的维数（用 stars and bars 公式），并列出一种把它映射到 qubit 对称子空间时需要多少个 qubit 的估算方式。 > 提示：比较 $\lceil\log_2 D\rceil$ 与 $n_{\mathrm{bos}}\log_2 N$ 两种估算。 **练习 5【Hamiltonian 构造与玻色增强】**（→ [4.3 节](#signal-hamiltonian-boost)） 1. 写出 $H(T)$ 的定义，并说明为什么每一项都保持总玻色子数（$[H(T),\sum_i\hat n_i]=0$）、为什么对称实张量保证 $H(T)$ 厄米。 2. 取 $n_{\mathrm{bos}}=4$、$p=4$、$\lambda=1$：用第 4.5 节的公式计算凝聚态上的信号能量，并指出其中的玻色增强因子。 3. 验证 signal Hamiltonian 可写成 $b_v$ 的多项式：从 $H_{\mathrm{signal}}=\lambda(\sum_i v_i a_i^\dagger)^{p/2}(\sum_j v_j a_j)^{p/2}$ 出发，明确指出每一步用了哪条对易关系，并说明 $p$ 为奇数时这个构造在哪里失效。 > 提示：多项式定理的展开只需要同类算符彼此对易。 **练习 6【量子算法流水线与读出】**（→ [第 5 节](#pipeline-readout)） 1. 按顺序列出量子算法的五个步骤，各用一句话说明作用，并指出哪一步把命中信号窗口的平均重复次数从 $1/p_{\mathrm{hit}}$ 降到 $1/\sqrt{p_{\mathrm{hit}}}$。 2. 写出一体约化密度矩阵 $\Gamma_{ij}$ 的定义，并解释为什么列出 $\widehat v$ 的全部 $N$ 个坐标需要 $\Omega(N)$ 级经典输出、什么情况下可以一直留在量子形式。 3. 对 $p=2$ 推导一体 density matrix 的 principal eigenvector 与 $v$ 对齐（沿第 6 节的路线，补全 $[a_j,(b_v^\dagger)^n]=n\frac{v_j}{\sqrt N}(b_v^\dagger)^{n-1}$ 的归纳证明）。 > 提示：归纳步骤用 $[A,BC]=[A,B]C+B[A,C]$ 与 $[a_j,b_v^\dagger]=v_j/\sqrt N$。 **练习 7【四次方指数率与资源边界】**（→ [第 7 节](#quartic-rate-resources)） 1. 指出两次平方根改善分别来自流水线的哪一步，并说明 $\log T_Q/\log T_C\to\frac14$ 比较的对象为什么是指数率而不是运行时间的比值。 2. 设 $T_C=\exp(A)$、$T_Q=\exp(A/4)$。验证 $\log T_Q/\log T_C=1/4$，并取 $A=40$ 算出 $T_C$ 与 $T_Q$ 的量级；用此例向同学解释为什么“指数率改善为四分之一”不等于“快四倍”，以及为什么该结论不排斥存在更强的经典算法。 3. 列出若 tensor 以普通磁盘数组给出，oracle 构造会增加的成本：构造 block encoding 前需要多少次元素读取？这对第 7 节的加速声明意味着什么？ > 提示：用 $\log_{10}e^{A}=A/\ln 10\approx A/2.3$ 估计数量级。 **练习 8【$p=2$ 校验与手算小例子】**（→ [第 9 节](#p2-sanity-check)） 1. 在 $p=2$、$n_{\mathrm{bos}}=1$ 的 single-boson sector 中取基 $|i\rangle=a_i^\dagger|0\rangle$，复现 $\langle i|H(T)|j\rangle=T_{ij}$ 的推导，并说明此时算法退化为普通 PCA。 2. 对第 10 节的例子（$N=2$、$v=(1,1)$）取 $n_{\mathrm{bos}}=3$，写出凝聚态在占据数基下的展开，并验证 $\langle a_1^\dagger a_1\rangle=\frac32$、$\Gamma=\frac{vv^T}{2}$。 > 提示：系数是 $\binom{3}{k}/2^3$ 的平方根。 ## 参考文献与 Zoo 覆盖 - Zoo 编号 424：Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray, Xin Wang, S. Chakraborty 与 S. Lloyd, [Quantum algorithms for the tensor principal component problem](https://arxiv.org/abs/1907.12724)。 - 本文对应 Zoo 的 “Tensor principal component analysis” 条目；复杂度陈述采用论文的 spiked-tensor normalization 与 fixed-boson 渐近条件。