# 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. 量子算法流水线

算法可概括为：

1. 在 fixed-boson sector 制备易实现的 initial state 或其随机 ensemble；
2. 用 tensor-access oracle 构造并模拟 $e^{-itH(T)}$；
3. 对 $H(T)$ 做 phase estimation，标记 signal-dominated spectral window；
4. 用 amplitude amplification 提升投影到该 window 的小振幅；
5. 测量一体 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、访问模型和比较对象。

1. 计算 $N=4,n_{\mathrm{bos}}=3$ 时 symmetric sector 的维数。
2. 验证 signal Hamiltonian 可写成 $b_v$ 的多项式。
3. 对 $p=2$ 推导一体 density matrix 的 principal eigenvector 与 $v$ 对齐。
4. 列出若 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](https://arxiv.org/abs/1907.12724)。
- 本文对应 Zoo 的 “Tensor principal component analysis” 条目；复杂度陈述采用论文的 spiked-tensor normalization 与 fixed-boson 渐近条件。