Tensor PCA：Spiked Tensor、Bosonic Hamiltonian 与四次方加速¶

Matrix PCA 寻找最大 eigenvector；高阶 tensor 没有同样简单的 spectral theorem。Quantum tensor PCA 把 tensor entries 写成多体 bosonic Hamiltonian，用 Hamiltonian simulation、phase estimation 和 amplitude amplification 找到与隐藏 spike 对齐的低能/高能方向。在特定弱信号与资源模型下，它相对已知 classical spectral method 给出二次再二次、合计 quartic 的指数率改善。

1. Spiked tensor 模型¶

考虑 order-$p$ symmetric tensor

\[ T=T_0=\lambda v^{\otimes p}+G, \qquad v\in\mathbb R^N, \qquad \|v\|=\sqrt N, \]

其中 $G_{i_1\ldots i_p}$ 是适当归一化的 Gaussian noise，$\lambda$ 是 signal strength。目标不是逐项恢复 $v$，而是输出与 $v$ 有非消失 overlap 的 estimator $\widehat v$：

\[ \frac{|\langle\widehat v,v\rangle|}{\|\widehat v\|\,\|v\|}\ge c>0. \]

统计上与计算上可恢复的 threshold 不一定相同。所讨论算法关注 classical spectral regime 附近，常写

\[ \lambda=\alpha N^{-p/4}. \]

这里的 normalization 很重要；改变 $G$ 或 $v$ 的尺度会改变表面 threshold。

2. 为什么 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}. \]

$M$ 的维数是 $N^{p/2}\times N^{p/2}$，spike 方向是

\[ v^{\otimes p/2}. \]

Power iteration 或 eigensolver 可抓住最大 eigenvector，但显式保存这个矩阵需要 $N^p$ 级 entries；即使只在对称子空间工作，维数也随副本数快速增长。这正是量子 state space 可隐式表示的结构。

3. 从 tensor 到 bosonic Hamiltonian¶

引入 $N$ 个 modes 的 creation/annihilation operators $a_i^\dagger,a_i$，并固定总 boson 数

\[ \sum_{i=1}^N a_i^\dagger a_i=n_{\mathrm{bos}}. \]

这个 sector 等价于 $n_{\mathrm{bos}}$ 个 $N$ 维 qudits 的 symmetric subspace，维数

\[ D=\binom{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}. \]

对偶数 $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}. \]

若 $T=\lambda v^{\otimes p}$，令

\[ b_v^\dagger=\frac1{\sqrt N}\sum_i v_i a_i^\dagger, \]

则 signal Hamiltonian 含 $(b_v^\dagger)^{p/2}(b_v)^{p/2}$，偏好 bosons 聚集在未知 mode $v$ 上；noise 则形成随机多体背景。

4. 量子算法流水线¶

算法可概括为：

在 fixed-boson sector 制备易实现的 initial state 或其随机 ensemble；
用 tensor-access oracle 构造并模拟 $e^{-itH(T)}$；
对 $H(T)$ 做 phase estimation，标记 signal-dominated spectral window；
用 amplitude amplification 提升投影到该 window 的小振幅；
测量一体 reduced density matrix $$ \Gamma_{ij}=\langle a_i^\dagger a_j\rangle/n_{\mathrm{bos}}, $$ 其 principal eigenvector 估计 $v$。

最后一步若要列出全部 $N$ 个坐标，仍需 $\Omega(N)$ 级 classical output；若下游只需与给定向量的 overlap，则可留在 quantum form。

5. 两次平方根从哪里来¶

与 classical spectral procedure 对比时有两个 quadratic gain：

quantum Hamiltonian simulation 在 $D$ 维空间中不显式保存或逐项乘巨大矩阵；
amplitude amplification 把命中 signal subspace 的重复次数从 $1/p_{\mathrm{hit}}$ 降为 $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。这是对特定 classical spectral family 和 oracle model的结果，不是对所有 classical algorithms 的无条件 quartic lower bound。

6. 参数与资源边界¶

$n_{\mathrm{bos}}$ 是放大弱 spike 的旋钮。信号越弱，通常需更多 bosons；在分析中它随 $\lambda^{-1}$ polynomial 增长，而 runtime 对弱信号参数仍可能 exponential。实际资源还依赖：

tensor entry/block-encoding oracle 的实现；
$\|H(T)\|$、simulation time 与 phase-estimation precision；
signal spectral window 和 noise gap；
initial overlap 及 amplitude-amplification 次数；
读出 $v$ 所需的 copies/tomography。

因此“polynomial quantum space”不等于近期硬件可运行；fixed-boson encoding、深 Hamiltonian simulation 和 fault-tolerant phase estimation 都是强要求。

7. $p=2$ 的 sanity check¶

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

\[ H(T)=\sum_{ij}T_{ij}a_i^\dagger a_j. \]

在 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。

8. 小结与习题¶

Spiked tensor PCA 从 $T=\lambda v^{\otimes p}+G$ 恢复隐藏方向。
Tensor 被映射为 fixed-boson symmetric sector 中的多体 Hamiltonian。
Hamiltonian simulation 与 amplitude amplification 各贡献一次平方根改善。
Quartic 指数率结论依赖 Gaussian model、normalization、访问模型和比较对象。

计算 $N=4,n_{\mathrm{bos}}=3$ 时 symmetric sector 的维数。
验证 signal Hamiltonian 可写成 $b_v$ 的多项式。
对 $p=2$ 推导一体 density matrix 的 principal eigenvector 与 $v$ 对齐。
列出若 tensor 以普通磁盘数组给出，oracle 构造会增加的成本。

参考文献与 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 渐近条件。