# 量子矩阵秩判定：Span Program、奇异值条件与稀疏加载

给定 entry oracle 访问 $n\times m$ 矩阵 $A$，要判断其秩是否至少为 $r$。枚举所有 entry 需 $nm$ 次查询；量子 span program 能在矩阵稀疏且非零奇异值不太小时减少查询。加速并非只由维数决定：伪逆范数控制 witness 大小，输入向量加载方式控制每次反射成本。

## 1. 问题、承诺与数值稳定性

设奇异值

$$
\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_{\min(n,m)}\ge0.
$$

秩至少 $r$ 当且仅当 $\sigma_r>0$。在 exact integer/finite-field oracle 中“零或非零”有代数意义；在浮点模型中必须承诺 gap

$$
\sigma_r\ge\gamma,\qquad
\sigma_{r+1}=0
$$

或改成数值秩。若允许 $\sigma_r$ 任意接近 0，任何有限精度算法都无法稳定区分。

把前 $r$ 个非零奇异值的倒数均方根记为

$$
L=\left(
\frac1r\sum_{j=1}^r\sigma_j^{-2}
\right)^{1/2}.
$$

$L$ 是条件数型因子：矩阵越接近降秩，witness 系数越大，算法越慢。

## 2. 从“存在独立方向”到 Span Program

把列向量记为 $a_1,\ldots,a_m\in\mathbb F^n$。秩至少 $r$ 等价于列空间含 $r$ 个线性独立方向，也等价于外代数中存在非零 wedge：

$$
a_{j_1}\wedge\cdots\wedge a_{j_r}\ne0.
$$

直接对所有 $\binom mr$ 个 minor 做 Grover 会浪费严重重叠。Belovs 的 high-level span program 把“加载一个输入向量 $a_j$”视为原语，并在由子空间/外代数层级组成的向量空间里设计目标：

- yes 输入的正 witness 选择一组能扩展到 $r$ 维的方向，并用 $A^+$（伪逆）系数把目标写成可用向量线性组合；
- no 输入的负 witness 位于列空间正交补，证明所有 $r$ 维目标都无法生成。

将 high-level 输入向量进一步展开为 entry-query 的普通 span program 后，Reichardt 双反射算法完成判定。正 witness 中的伪逆系数平方和产生

$$
\sum_{j=1}^r\sigma_j^{-2}=rL^2,
$$

组合层级则产生 $\sqrt{r(n-r+1)}$ 因子。

## 3. 查询复杂度公式如何解读

Zoo 所收录的上界可写为

$$
Q=O\!\left(
\sqrt{r(n-r+1)}\,L\,T
\right),
$$

其中 $T$ 是相干加载/反射一个矩阵向量的查询成本。

对一般 dense entry oracle，振幅加载一列需要在 $n$ 个 entry 上准备归一化态并处理列选择，给出

$$
T=O(\sqrt{nm}).
$$

若每行每列最多 $k$ 个非零 entry，并有 sparse oracle 在给定列时列出非零位置和值，则

$$
T=O(k\log(n+m)).
$$

注意后者使用的 oracle 比逐 entry 查询更强；若只有 entry oracle，寻找一列中的 $k$ 个非零位置本身也需要搜索，不能免费采用 sparse 上界。

## 4. Singular / determinant 特例

对方阵，判断

$$
\det A=0
$$

等价于秩是否小于 $n$。无承诺的一般 determinant query problem 有 $\Omega(n^2)$ 级量子下界，与读取所有 entry 同阶，因此不存在普适 entry-query 加速。

Span-program 上界有用的区域是：

1. 矩阵稀疏且 sparse oracle 可用；
2. 目标秩 $r$ 远离使组合因子最坏的位置；
3. 非零奇异值有下界，使 $L$ 不大。

这不与 determinant 下界矛盾，因为下界允许 dense、病态、恰好接近奇异的最坏实例。

## 5. 例子：对角矩阵

令

$$
A=\operatorname{diag}(1,1,\epsilon,0).
$$

秩为 3（$\epsilon\ne0$）。测试 $r=3$ 时

$$
L=\sqrt{\frac{1+1+\epsilon^{-2}}3}
\sim\frac1{\sqrt3|\epsilon|}.
$$

即使矩阵只有 3 个非零 entry，$\epsilon$ 很小时查询/精度成本仍增大。这是数值线性代数中的稳定性，不是量子算法设计缺陷。

若只测试 $r=2$，使用最大两个奇异值，$L=1$，同一输入容易得多。秩阈值承诺会实质改变复杂度。

## 6. 从判定到求精确秩

可对不同 $r$ 做二分或递增判定来找最大可接受秩，但每次都需要相应奇异值 gap，且总成本由最难阈值主导。若还要输出独立列集合，可在判定 oracle 上做 self-reduction：尝试删除/加入列并保持秩阈值，额外付出对数或线性因子。

“少查询判定秩”也不等于输出 SVD；后者有 $\Theta(nm)$ 个经典 entry 的输出规模，必须明确只输出一个整数或少量 witness。

## 7. 小结与习题

- 秩阈值可由线性独立/外代数 span program 表示。
- 正 witness 使用伪逆，因而复杂度含非零奇异值倒数均方根 $L$。
- Dense 与 sparse 上界依赖不同 oracle；稀疏性本身不能替代稀疏访问。
- 一般 determinant 问题无查询加速，优势来自条件与结构承诺。

1. 证明 rank $\ge r$ 等价于某个 $r$ 重 wedge 非零。
2. 对 $\operatorname{diag}(1,\epsilon,0)$ 分别计算 $r=1,2$ 的 $L$。
3. 比较 entry oracle 与 sparse-list oracle 能提供的信息。
4. 解释为何精确秩整数输出不需要输出全部奇异向量。

## 参考文献

- Zoo 编号 150：Aleksandrs Belovs, [Span-Program-Based Quantum Algorithm for the Rank Problem](https://arxiv.org/abs/1103.0842).
- Zoo 编号 149：Ben Reichardt, [Span Programs and Quantum Query Complexity](https://arxiv.org/abs/0904.2759).
- Zoo 编号 151：Sebastian Dörn 与 Thomas Thierauf, *The Quantum Query Complexity of the Determinant*, IPL 2009。