量子矩阵秩判定：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. 解释为何精确秩整数输出不需要输出全部奇异向量。

参考文献