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

给定 entry oracle 访问的 $n\times m$ 矩阵 $A$，要判断它的秩是否至少为 $r$。最朴素的办法是读出全部 $nm$ 个 entry 再做高斯消去，代价是 $nm$ 次查询；本教程要讲清的是：在矩阵稀疏、且非零奇异值不太小的条件下，量子 span program 算法能把查询次数降下来。但加速并非只由维数决定——伪逆的范数控制 witness 的大小，输入向量的加载方式控制每次反射的成本。换句话说，同样的 $n,m,r$，算法快慢可以差出许多个数量级，差距来自矩阵的**数值条件**与**访问方式**。

秩是线性代数里最基本的不变量之一：方程组解是否唯一、矩阵是否可逆、子空间的维数计数，第一步几乎都是问秩。在黑盒（查询）模型里研究秩判定，因此成为"黑盒线性代数"的代表问题。它也是一面很好的镜子，能照出量子查询算法的一条通用经验：**承诺（promise）与输入结构决定了加速是否存在，而不是问题名字里有没有"矩阵"二字**。

本教程的主线是 Belovs 的 span program 算法（见文末参考文献，Zoo 编号 150）。我们把整个推导拆成四层，层层递进：

1. 把"秩至少 $r$"这个代数条件翻译成"存在 $r$ 个线性独立方向"，再翻译成外代数中"存在非零的 $r$ 重楔积"——这是 span program 能吃的语言（第 3 节）；
2. 用伪逆（Moore–Penrose pseudoinverse）写出正 witness，并实际算出它的成本是前 $r$ 个非零奇异值倒数的均方根 $L$（第 3 节）；
3. 把 Reichardt 的双反射算法套在这个 span program 上，得到查询复杂度 $O(\sqrt{r(n-r+1)}\,L\,T)$，并逐因子解释每一项的来源（第 4 节）；
4. 与 determinant 的 $\Omega(n^2)$ 量子下界对照，弄清上界在哪些参数区域真正有用、为什么与下界不矛盾（第 5 节）。

沿途我们会给出完整的推导：经典基线为什么是 $\Theta(nm)$（含一个可手算的对手论证）、为什么浮点模型必须带奇异值 gap 承诺、组合因子 $\sqrt{r(n-r+1)}$ 在 $r$ 取何值时最坏（一次求导就能算出）、以及两个可以手算到底的小例子。

**前置知识**：本站第 3 章的 [Grover 算法](../ch03-algo-basics/grover.md)（反射、振幅放大、$\sqrt N$ 加速）与[相位估计](../ch03-algo-basics/phase-estimation.md)；同章的 [Boolean 公式求值：Span Program、对抗界与双反射算法](formula-evaluation-span-programs.md)（span program 的定义、正负 witness、witness size 与双反射算法，本教程第 3.3 节只做复习，不重新推导）；第 6 章 [HHL 算法](../ch06-scientific-computing/hhl-algorithm-tutorial.md)中关于条件数的讨论（对照 $L$ 的角色）。线性代数方面只需要 SVD 的基本性质，我们会在用到处证明。

:::{admonition} 本课知识点
:class: tip

1. **[黑盒模型与秩判定问题](#query-model-rank-problem)**——能写出 entry oracle 的作用式并陈述秩判定问题，区分查询复杂度与时间复杂度的记账。
2. **[秩的奇异值刻画](#rank-singular-value)**——能证明秩恰为非零奇异值的个数，并把 $\operatorname{rank}(A)\ge r$ 改写为谱条件 $\sigma_r>0$。
3. **[奇异值 gap 承诺的必要性](#gap-promise)**——能用 $1\times1$ 定点实例证明浮点模型下无承诺则秩判定不可解，并写出 yes/no 实例的承诺形式。
4. **[条件数型因子 L](#condition-number-factor)**——能由奇异值计算 $L$、证明夹逼 $\frac{1}{\sigma_1}\le L\le\frac{1}{\sigma_r}$，并说明 $L$ 与经典条件数 $\kappa$ 的关系。
5. **[经典查询下界](#classical-lower-bound-matrix-rank)**——能构造只差一个 entry 的矩阵对证明确定性算法最坏需 $nm$ 次查询，并说明 $r=1$ 的判定就是 $\mathrm{OR}_{nm}$。
6. **[外代数刻画与 witness 估计](#exterior-algebra-witness)**——能手算 $2\times2$ 楔积、证明"楔积为零当且仅当线性相关"，并推导正 witness 成本 $rL^2$ 与负 witness 因子 $n-r+1$ 的来源。
7. **[复杂度公式逐因子解读](#complexity-formula-factors)**——能解释 $Q=O\big(\sqrt{r(n-r+1)}\,L\,T\big)$ 中每个因子的出处，比较 dense 与 sparse oracle 的 $T$，并求出组合因子最坏的阈值 $r^\ast=\frac{n+1}{2}$。
8. **[下界对照与任务边界](#determinant-lower-bound)**——能解释 determinant 的 $\Omega(n^2)$ 下界为何与上界不矛盾、列出上界有用的三个区域，并比较"判定秩、输出列 witness、输出 SVD"三档任务的输出规模。

:::

## 1. 问题、模型与数值稳定性

(query-model-rank-problem)=
### 1.1 黑盒模型中的秩判定

算法不能直接"看见"矩阵 $A\in\mathbb F^{n\times m}$（$\mathbb F$ 是实数域、有理数域或某个有限域，视模型而定），而只能通过**查询 oracle** 逐个访问 entry。以最常用的形式写下这个 oracle：

$$
O_A\colon |i,j,b\rangle\;\mapsto\;|i,j,b+A_{ij}\rangle,
\qquad i\in[n],\; j\in[m],
$$

其中 $b$ 取值于约定的数域（整数情形取整数；浮点情形取定点表示）。一次对 $O_A$ 的调用计为**一次查询**；查询次数是本教程的主复杂度指标。实现 oracle、管理索引寄存器、做算术的门开销则记入**时间复杂度**，与本章导言的记账方式一致：查询优势不自动等于时间优势，后文会反复用到这个区分。

要解决的判定问题是：

> **秩判定问题**：给定参数 $r\le\min(n,m)$（若 $r>\min(n,m)$ 答案平凡为"否"），判断是否 $\operatorname{rank}(A)\ge r$。

为什么限制 $r\le\min(n,m)$？因为 $n\times m$ 矩阵的秩不超过行数与列数中较小者；超过它的阈值无需任何查询即可回答。为方便引用，先把全文的符号集中列出，每个符号在正文首次出现处还会重新定义：

- $n,m$：矩阵的行数、列数；$r$：待判定的秩阈值；
- $a_1,\ldots,a_m\in\mathbb F^n$：$A$ 的列向量，即 $Ae_j=a_j$；
- $\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_{\min(n,m)}\ge0$：$A$ 的奇异值（递减排列）；
- $\gamma$：奇异值 gap 承诺的下界；
- $L$：前 $r$ 个非零奇异值倒数的均方根（第 1.4 节定义）；
- $T$：相干地加载/反射一个矩阵向量所需的查询成本（第 4 节定义）。

(rank-singular-value)=
### 1.2 秩与奇异值：判定条件的等价改写

在实数域上，奇异值分解（SVD）把 $A$ 写成

$$
A=\sum_{j=1}^{\min(n,m)}\sigma_j\,u_j v_j^{\mathsf T},
\qquad
\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_{\min(n,m)}\ge0,
$$

其中 $\{u_j\}\subset\mathbb R^n$、$\{v_j\}\subset\mathbb R^m$ 是各自空间中的正交归一向量组。秩判定之所以能数值化，靠的是下面这个标准事实；我们把证明完整写出，因为它同时给出了后文反复使用的两个恒等式。

**Lemma 1**. $\operatorname{rank}(A)=\#\{j:\sigma_j>0\}$，即秩恰是非零奇异值的个数。因此 $\operatorname{rank}(A)\ge r$ 当且仅当 $\sigma_r>0$。

**证明**. 分两步夹住列空间。

第一步（列空间 $\subseteq$ 前 $r'$ 个 $u_j$ 的张成，$r'=\#\{j:\sigma_j>0\}$）。对任意 $x\in\mathbb R^m$，把 $x$ 按基 $\{v_j\}$ 展开 $x=\sum_j c_j v_j$（正交归一基，$c_j=v_j^{\mathsf T}x$），代入 SVD：

$$
Ax=\sum_{j}\sigma_j u_j\, v_j^{\mathsf T}\Big(\sum_l c_l v_l\Big)
=\sum_{j}\sigma_j c_j\, u_j,
$$

其中第二个等号用了 $\{v_j\}$ 的正交归一性：$v_j^{\mathsf T}v_l=0$（$j\ne l$）、$v_j^{\mathsf T}v_j=1$。于是 $Ax$ 是 $u_j$ 的线性组合，且 $\sigma_j=0$ 的项自动消失，故列空间 $\subseteq\operatorname{span}\{u_j:\sigma_j>0\}$。

第二步（反向包含）。对每个 $\sigma_j>0$ 的 $j$，直接算 $Av_j$：

$$
Av_j=\sum_l\sigma_l u_l\, v_l^{\mathsf T}v_j=\sigma_j u_j
\quad\Longrightarrow\quad
u_j=\frac{1}{\sigma_j}Av_j,
$$

即每个这样的 $u_j$ 都是 $A$ 作用在某向量上的像，落在列空间中。两步合起来，列空间 $=\operatorname{span}\{u_j:\sigma_j>0\}$；这些 $u_j$ 两两正交故线性无关，维数恰为非零奇异值个数。

最后，由于奇异值按递减排列，"$\sigma_r>0$"等价于"至少 $r$ 个奇异值为正"，即 $\operatorname{rank}(A)\ge r$。Q.E.D.

这个引理把秩判定变成了一个**谱条件**：阈值 $r$ 卡在 $\sigma_r$ 上。于是所有数值上的麻烦都集中到一个点上——$\sigma_r$ 是不是恰好为零。

(gap-promise)=
### 1.3 为什么必须有 gap 承诺

在精确算术模型（entry 是整数、有理数，或有限域元素，所有运算无舍入）中，"等于零"有代数意义，秩是精确定义的不变量，不需要任何额外承诺。麻烦出在浮点模型：奇异值连续依赖于 entry，$\sigma_r$ 可以任意接近零而不等于零，此时"秩至少 $r$"与"秩至多 $r-1$"在数值上无法区分。我们用一个最小的例子把这件事说透。

**Lemma 2**. 设 oracle 对每个 entry 只返回 $p$ 位定点的近似值。那么任何算法（不限查询次数）都无法以误差 $\le\frac13$ 判定 $1\times1$ 矩阵 $A=(x)$ 是否满足 $\operatorname{rank}\ge1$，除非承诺区分的两个实例之间有至少一个最小刻度的间隔。

**证明**. 取两个实例 $x=0$ 与 $x=\delta$，其中 $0<\delta<2^{-p-1}$（小于半个最小刻度）。oracle 对两个实例返回同一个舍入值，因此无论算法查询多少次、做什么后处理，它在两个实例上看到的应答序列（作为随机变量）有完全相同的分布，从而最终输出的分布也完全相同。设该分布输出"秩 $\ge1$"的概率为 $q$。在实例 $x=0$（答案为否）上错误概率为 $q$，在实例 $x=\delta$（答案为是）上错误概率为 $1-q$。两者之和为 $1$，故至少一个是 $\ge\frac12>\frac13$。Q.E.D.

把对角矩阵 $\operatorname{diag}(1,\ldots,1,\delta,0,\ldots,0)$（$\delta$ 在第 $r$ 个对角位）代入同一论证，就得到一般 $r$ 的版本。结论是：浮点模型下的秩判定必须携带**承诺**。本教程采用原文的承诺形式：

$$
\text{yes 实例：}\ \sigma_r\ge\gamma>0,\ \sigma_{r+1}=0；
\qquad
\text{no 实例：}\ \sigma_r=0，
$$

读作：要么第 $r$ 个奇异值有下界 $\gamma$ 且第 $r+1$ 个严格为零（此时秩恰为 $r$，答案"是"），要么 $\sigma_r$ 严格为零（秩至多 $r-1$，答案"否"）。算法只需对满足承诺的输入正确。若不想把"yes 实例的秩恰好为 $r$"限制得这么死，可以把 "$=0$" 放宽为一个数值秩型的双边承诺（$\sigma_r\ge\gamma$ 对 $\sigma_{r+1}\le$ 小量），判定的对象相应变成**数值秩**；本教程为叙述简单采用上面的单边版本，推导完全类似。

这个承诺不是量子算法特有的让步：经典数值线性代数里"数值秩"的概念（把小于容差的奇异值当作零）面对的是同一个现象。后文第 6 节的小例子会显示，$\sigma_r$ 接近 $\gamma$ 时查询与精度成本如何随之增长。

(condition-number-factor)=
### 1.4 条件数型因子 $L$

承诺解决的是"可判定性"，还剩"难度"。同样满足 $\sigma_r\ge\gamma$ 的两个 yes 实例，可以一个良态、一个病态，算法在后者上慢得多。量化这个差距的量就是本教程的第二个主角。设输入是 yes 实例，把前 $r$ 个（即最大的 $r$ 个）非零奇异值的倒数均方根记为

$$
L=\left(\frac1r\sum_{j=1}^r\sigma_j^{-2}\right)^{1/2}
=\sqrt{\frac{\sigma_1^{-2}+\cdots+\sigma_r^{-2}}{r}}.
$$

$L$ 是条件数型因子：矩阵越接近降秩（某个 $\sigma_j$ 越小），witness 系数越大，算法越慢。第 3.5 节会实际算出：正 witness 的伪逆系数平方和恰是 $\sum_{j=1}^r\sigma_j^{-2}=rL^2$，所以 $L$ 不是随便定义的"病态度"，而是 witness 成本的自然开方。

先给出 $L$ 的两条基本估计，后文估计复杂度时会用到。

**Lemma 3**. 设 $\sigma_1\ge\cdots\ge\sigma_r>0$，则

$$
\frac{1}{\sigma_1}\;\le\;L\;\le\;\frac{1}{\sigma_r}.
$$

左边的等号成立当且仅当 $\sigma_1=\cdots=\sigma_r$；此外总有 $L\ge\frac{1}{\sqrt r\,\sigma_r}$。

**证明**. 由递减排列，$\sigma_1^{-2}\le\sigma_2^{-2}\le\cdots\le\sigma_r^{-2}$，即 $r$ 个被平均的数都落在区间 $[\sigma_1^{-2},\sigma_r^{-2}]$ 内。平均值夹在最小值与最大值之间：

$$
\sigma_1^{-2}\;\le\;\frac1r\sum_{j=1}^r\sigma_j^{-2}\;\le\;\sigma_r^{-2},
$$

开方即得两条不等式。左边取等当且仅当每个被平均的数都等于平均值，即全部 $\sigma_j$ 相等。最后，把平均值与其中最大的一项比较：

$$
\frac1r\sum_{j=1}^r\sigma_j^{-2}\;\ge\;\frac1r\,\sigma_r^{-2},
$$

开方得 $L\ge\frac{1}{\sqrt r\,\sigma_r}$。Q.E.D.

两个极端情形把 $L$ 的取值范围填满：

- **全部奇异值相等**（$\sigma_1=\cdots=\sigma_r=\sigma$）：$L=\frac1\sigma$，取到上界。归一化 $\sigma_1=1$ 且良态时 $L\approx1$。
- **只有第 $r$ 个奇异值小**（$\sigma_1=\cdots=\sigma_{r-1}\gg\sigma_r$）：求和被 $\sigma_r^{-2}$ 主导，$L\approx\frac{1}{\sqrt r\,\sigma_r}$，取到下界量级。

与经典条件数 $\kappa=\sigma_1/\sigma_r$ 对照：把矩阵归一化到 $\sigma_1=1$ 后，$\kappa=1/\sigma_r$，于是 $L$ 永远夹在 $\kappa/\sqrt r$ 与 $\kappa$ 之间——它是 $\kappa$ 的"均方根软化版"。用平方和而不是最大值来度量病态，不是风格偏好，而是 witness 成本的欧氏范数结构决定的（见第 3.5 节）。

## 2. 经典基线：读取几乎全部 entry 躲不掉

量子算法要有意义，先得知道经典算法卡在哪里。这一节给出两条互补的基线：确定性算法最坏情形必须读满 $nm$ 个 entry（对手构造）；即使允许随机性，最简单的阈值 $r=1$ 也需要 $\Theta(nm)$ 次查询（隐藏位置论证）。第二条顺便告诉我们量子侧的地板：$r=1$ 时 Grover 给 $\Theta(\sqrt{nm})$，而且这是最优的。

(classical-lower-bound-matrix-rank)=
### 2.1 一个 entry 就能翻转答案

**Lemma 4**. 任何用少于 $nm$ 次查询的确定性算法，都存在一对只在**一个** entry 上不同的输入矩阵，使得这对矩阵的秩判定答案不同。因此确定性算法最坏情形必须查询全部 $nm$ 个 entry。

**证明**. 先构造一对"关键差异"矩阵。设 $2\le r\le\min(n,m)$，定义 $n\times m$ 矩阵

$$
A(x)\colon\quad A_{11}=x,\qquad A_{jj}=1\ (j=2,\ldots,r),\qquad\text{其余 entry}=0 .
$$

$A(x)$ 除第一行第一列外是对角结构。当 $x=0$ 时非零列只有 $r-1$ 个标准基向量 $e_2,\ldots,e_r$，线性无关，故 $\operatorname{rank}(A(0))=r-1<r$；当 $x=1$ 时非零列是 $e_1,\ldots,e_r$ 共 $r$ 个，$\operatorname{rank}(A(1))=r$。两个矩阵只在 $(1,1)$ 位置不同。

现在设算法做了 $t<nm$ 次查询（这里的 $t$ 是经典算法的查询计数，与第 4 节的加载成本 $T$ 无关），必有某个位置 $p=(i,j)$ 从未被查询。把上述构造做行置换与列置换，把"关键位" $(1,1)$ 挪到 $p$：行/列置换不改变秩（置换只是重排行与列的顺序，非零的 $r\times r$ 子式还是非零），于是得到两个只在 $p$ 上不同的矩阵，秩分别在阈值两侧。算法对这两个矩阵的 oracle 应答历史完全相同，必然输出同一答案，至少在其中一个上出错。Q.E.D.

这个论证的要点值得记下来：**秩对单个 entry 是敏感的**。一个没有读到的 entry，可能恰好是把秩从 $r-1$ 抬到 $r$ 的那块拼图。第 5 节会看到，量子下界 $\Omega(n^2)$ 的直觉正是同一现象在量子情形的严格化。

### 2.2 $r=1$ 就是 OR：随机算法的下界

允许随机性能不能绕开敏感性？对最简单的阈值 $r=1$，答案是干脆的否定，而且证明只用初等概率。

观察到 $r=1$ 的判定条件可以完全消去线性代数：

$$
\operatorname{rank}(A)\ge1
\quad\Longleftrightarrow\quad
A\ne0
\quad\Longleftrightarrow\quad
\bigvee_{i\in[n],\,j\in[m]}\big[A_{ij}\ne0\big],
$$

即 $nm$ 个"entry 非零"事件的 OR。这正是 [Grover 算法](../ch03-algo-basics/grover.md)一节里反复研究的无结构搜索问题 $\mathrm{OR}_{nm}$。

**Lemma 5**. 判定 $r=1$ 的任意随机算法若以误差 $\le\frac13$ 正确，期望查询次数 $t\ge\frac23\,nm$。

**证明**. 考虑一个随机化的输入分布：均匀随机选位置 $P\in[n]\times[m]$，令矩阵 $A^{(P)}$ 在 $P$ 处取 $1$、其余全部为 $0$；另设全零矩阵 $A^{(\varnothing)}$。两者都是合法输入（秩分别为 $1$ 与 $0$），答案相反。

固定算法的全部内部随机性后，算法是一个自适应的查询策略；但无论策略如何自适应，它总共只查询 $t$ 个位置，而 $P$ 与算法的随机性独立且均匀分布，所以

$$
\Pr[\text{算法查询到 }P]\;\le\;\frac{t}{nm}.
$$

（每一次查询至多"试探"一个位置；$t$ 次查询覆盖均匀随机点的概率至多是 $t/nm$。）关键在于条件"未查询到 $P$"时会发生什么：算法在 $A^{(P)}$ 上得到的应答**全部为 $0$**，与它在 $A^{(\varnothing)}$ 上的应答逐步相同，因此两种情形下算法的后续行为（包括最终输出分布）没有差别。于是

$$
\Pr\big[\text{算法在 }A^{(P)}\text{ 上输出"秩}\ge1\text{"}\big]
\;\le\;\frac{t}{nm}+\Big(1-\frac{t}{nm}\Big)\cdot q,
$$

其中 $q$ 是算法面对"全零视图"时输出"是"的概率。$A^{(\varnothing)}$ 是答案为"否"的实例，误差 $\le\frac13$ 要求 $q\le\frac13$；$A^{(P)}$ 是答案为"是"的实例，要求上式 $\ge\frac23$。联立：

$$
\frac23\;\le\;\frac{t}{nm}+\frac13
\quad\Longrightarrow\quad
t\;\ge\;\frac23\,nm. \qquad\text{Q.E.D.}
$$

量子一侧，$\mathrm{OR}_{nm}$ 的查询复杂度是 $\Theta(\sqrt{nm})$：上界是 Grover 搜索，下界是标准的对抗/多项式论证（见 [Grover 算法](../ch03-algo-basics/grover.md)）。于是自然要问：**把阈值从 $r=1$ 推到一般的 $r$，量子的平方级优势还保得住吗？保住的代价是什么？** 这正是 span program 要回答的问题，也是本教程余下部分的主题。

### 2.3 历史脉络

把本教程用到的三条历史线索按时间排好，方便对号入座：

- **Span program 作为通用算法设计工具**。Reichardt（参考文献，Zoo 编号 149）证明 span program 的 witness size 与一般对抗界（general adversary bound）互为对偶，并给出以 $O(W(P))$ 次查询运行的双反射算法。这一框架的完整讲解在本站同章的 [Boolean 公式求值](formula-evaluation-span-programs.md)；本教程直接把它当黑盒用。
- **秩问题的 span program 算法**。Belovs（Zoo 编号 150）把秩判定写成一个"高层的"（high-level）span program：把加载一列输入向量视为原语，在由子空间/外代数层级组成的向量空间里设计目标向量，从而对秩判定给出 $O(\sqrt{r(n-r+1)}\,L\,T)$ 型的查询上界——第 3、4 节的全部内容就是拆解这个公式。
- **没有承诺就没有加速**。Dörn 与 Thierauf（Zoo 编号 151）证明无承诺的一般 determinant 判定有 $\Omega(n^2)$ 级量子查询下界，与读满所有 entry 同阶。它划出了本文上界的适用边界，第 5 节专门讨论它与上界为何不矛盾。

## 3. 从"存在独立方向"到 Span Program

(exterior-algebra-witness)=
### 3.1 外代数刻画：楔积与 minor

把列向量记为 $a_1,\ldots,a_m\in\mathbb F^n$。秩至少 $r$ 的最直白说法是：**列空间中含有 $r$ 个线性独立的方向**。要做量子算法，我们需要一个把这些方向"打包成一个向量"的代数装置，这就是外代数（exterior algebra）。这里只引入够用的最小版本。

对 $r$ 个向量 $v_1,\ldots,v_r\in\mathbb F^n$，定义**楔积（wedge product）** $v_1\wedge\cdots\wedge v_r$ 为满足以下两条规则的形式对象：

- **多线性**：对每个因子分别是线性的；
- **反对称**：交换任意两个因子整体变号；特别地，某两个因子相同时楔积为零。

所有 $r$ 重楔积张成一个有限维向量空间，记 $\Lambda^r(\mathbb F^n)$，它有天然基

$$
\{\,e_{i_1}\wedge\cdots\wedge e_{i_r}\ :\ 1\le i_1<\cdots<i_r\le n\,\},
\qquad
\dim\Lambda^r(\mathbb F^n)=\binom nr .
$$

先手算一个最小的例子，把抽象定义落到实处。设 $n=r=2$，$a_1=\alpha e_1+\beta e_2$，$a_2=\gamma e_1+\delta e_2$。按多线性展开四项：

$$
a_1\wedge a_2
=\alpha\gamma\,\underbrace{e_1\wedge e_1}_{=0}
+\alpha\delta\,e_1\wedge e_2
+\beta\gamma\,\underbrace{e_2\wedge e_1}_{=-\,e_1\wedge e_2}
+\beta\delta\,\underbrace{e_2\wedge e_2}_{=0}
=(\alpha\delta-\beta\gamma)\,e_1\wedge e_2 .
$$

括号里正是 $2\times2$ 行列式。这不是巧合：一般地，把 $v_1\wedge\cdots\wedge v_r$ 按上面的基展开，各坐标恰是这 $r$ 个列向量在所有行子集上的 $r\times r$ 子行列式（minor）。

**Lemma 6**. $v_1\wedge\cdots\wedge v_r=0$ 当且仅当 $v_1,\ldots,v_r$ 线性相关。

**证明**.（$\Leftarrow$）设线性相关，则某个向量落在其余向量的张成中；不妨设 $v_r=\sum_{j<r}c_j v_j$（重排顺序不改变"是否线性相关"，且至多改变楔积的符号）。代入并用多线性展开：

$$
v_1\wedge\cdots\wedge v_{r-1}\wedge v_r
=\sum_{j=1}^{r-1}c_j\;
v_1\wedge\cdots\wedge v_{r-1}\wedge v_j .
$$

右边每一项中 $v_j$ 出现了两次（一次在 $v_1,\ldots,v_{r-1}$ 里，一次在末位），由反对称性每一项都为零，故整个楔积为零。

（$\Rightarrow$）证逆否命题。设 $v_1,\ldots,v_r$ 线性无关，由基扩充定理（Steinitz 交换引理）可把它们扩充为 $\mathbb F^n$ 的一组基 $v_1,\ldots,v_n$。此时 $r$ 重楔积 $v_1\wedge\cdots\wedge v_r$ 关于基 $\{v_{i_1}\wedge\cdots\wedge v_{i_r}\}$ 的坐标中，自身位置是 $1$，故它非零。Q.E.D.

把引理用在矩阵的列上，立即得到秩的组合刻画。

**推论**. 下列等价：

$$
\operatorname{rank}(A)\ge r
\quad\Longleftrightarrow\quad
\exists\,1\le j_1<\cdots<j_r\le m:\ a_{j_1}\wedge\cdots\wedge a_{j_r}\ne0
\quad\Longleftrightarrow\quad
\exists\ r\times r\ \text{minor}\ne0 .
$$

**证明**. 第一个等价："$\operatorname{rank}\ge r$"即"存在 $r$ 个线性无关的列"，由 Lemma 6 即"存在非零的 $r$ 重楔积"。第二个等价：由楔积按基展开的坐标恰为各 minor（见上面的手算），楔积非零当且仅当某个坐标即某个 minor 非零。Q.E.D.

顺手检查一个极端：$r=1$ 时 $\Lambda^1(\mathbb F^n)=\mathbb F^n$，"某个 $1$ 重楔积非零"就是"某个列非零"，再展开到 entry 就是第 2.2 节的 $\mathrm{OR}_{nm}$。外代数刻画是 OR 的自然推广：从"存在一个非零 entry"到"存在一组非零 minor"。

### 3.2 朴素 Grover 为什么浪费

推论把秩判定变成了"对 $\binom mr$ 个对象做存在性判断"，最直接的想法是对所有 $r$ 元列子集做 Grover 搜索。这条路可行但浪费严重，原因有三层：

1. **单个候选不便宜**。判断一个固定子集 $\{j_1,\ldots,j_r\}$ 的 minor 是否非零，需要先读出这个 $r\times r$ 子矩阵的全部 $r^2$ 个 entry，再做行列式计算——每个候选本身就是 $r^2$ 次查询的子程序，而不是一次 oracle 调用。
2. **重叠严重**。两个只差一列的子集共享 $r-1$ 列，读过的 entry 与中间计算无法在"把每个 minor 当独立黑盒 predicate"的搜索里复用；$\binom mr$ 个候选覆盖的 entry 总量远小于 $\binom mr\cdot r^2$，独立估值等于把同样的数据读了许多遍。
3. **predicate 不是黑盒**。Grover 需要"判定候选是否标记"的反射；对 minor 而言这个反射本身要靠数据构造，等于把难度转移而不是消去。

Span program 的价值正在于绕开逐个枚举：它把"存在 $r$ 个独立方向"作为一个**整体的线性代数条件**编码进一个反射算子里，让振幅在"独立方向数目"这个自由度上相干地流动，而不是在 $\binom mr$ 个候选上盲目试错。

### 3.3 Span program 与双反射算法：快速复习

本小节把同章 [Boolean 公式求值](formula-evaluation-span-programs.md)中详细推导过的框架压缩成一段回顾，只保留本教程要用的结论。

一个 **span program** $P$ 由一个内积空间 $\mathcal H$、一个目标向量 $|\tau\rangle\in\mathcal H$、以及一族按输入条件"可用/不可用"的输入向量 $\{|v_{j}\rangle\}\subset\mathcal H$ 组成。程序接受输入，当且仅当目标落在可用向量的张成中：$|\tau\rangle\in\operatorname{span}\{\text{可用向量}\}$。两个量控制它的算法性能：

- **正 witness**（接受输入）：系数 $|w\rangle$ 把目标写成可用向量的线性组合，其代价是系数的平方和 $\|w\|^2$。对每个接受输入取最优系数，再对最难的接受输入取最大，得 $\operatorname{wsize}_1(P)$。
- **负 witness**（拒绝输入）：一个与所有可用向量正交、却与目标有非零内积的"分离超平面"向量 $|\omega\rangle$，其代价 $\|A^\dagger\omega\|^2$ 度量它泄漏到不可用向量上的多少。同样取最难拒绝输入的最大值，得 $\operatorname{wsize}_0(P)$。

**witness size** 取两者的几何平均：$W(P)=\sqrt{\operatorname{wsize}_0(P)\cdot\operatorname{wsize}_1(P)}$。Reichardt 的双反射算法（参考文献，Zoo 编号 149）断言：以两个反射——一个只依赖 $P$ 的结构、一个依赖输入的可用性——构造酉算子，配合相位估计，就能以

$$
O\!\big(W(P)\big)
$$

次"实现输入相关反射"的查询正确判定。同章教程用 $\mathrm{OR}_n$ 验证过这条定理：$W=\sqrt n$ 对应 Grover 的 $\sqrt n$ 次迭代。本教程的用法是：**先为秩判定构造一个 witness size 可控的 span program，复杂度分析就变成了对 witness 的线性代数估计**。

有一个新的技术问题：秩判定的输入不是 Boolean 位，而是 $nm$ 个数值 entry。把每个 entry 当作一个"文字"直接做 entry 层面的 span program 固然可以，但 Belovs 选择了另一条更透明的两层路线，见下节。

### 3.4 Belovs 的 high-level span program

**把"加载一个输入向量 $a_j$"视为原语。** 想象先拥有一个更强的向量级 oracle $O_{\mathrm{vec}}$：它能把第 $j$ 列 $a_j\in\mathbb F^n$ 作为一个整体相干地装载/反射。在这个更高的抽象层上设计 span program：

- **状态空间**取为由子空间/外代数层级组成的复合向量空间。原型是直和 $\mathcal H=\mathcal H_0\oplus\mathcal H_1\oplus\cdots\oplus\mathcal H_r$，第 $k$ 层 $\mathcal H_k$ 承载"当前已楔起 $k$ 个独立方向"的自由度（以 $\Lambda^k(\mathbb F^n)$ 为模型，维数 $\binom nk$）。
- **加载一列**是层级间的转移：把 $a_j$ 楔入当前态（$k\to k+1$）或用 $a_j$ 对当前态做缩并（$k\to k-1$）。
- **目标向量**$|\tau\rangle$ 放在顶层 $\mathcal H_r$，对应"支起一个 $r$ 维独立方向"。

（这里给出的是功能刻画；层级与反射的精确线性代数实现见 Belovs 的原文，见文末参考文献。）

在这个框架下，正负 witness 的形态如下，这是全教程最核心的两句直觉：

- **yes 输入（$\operatorname{rank}\ge r$）的正 witness**：选择一组能扩展到 $r$ 维的方向，并用伪逆 $A^+$ 的系数把目标写成可用向量的线性组合。直觉：伪逆恰好回答"用多小的系数能用列向量合成一个给定目标"，第 3.5 节会把系数大小算出来。
- **no 输入（$\operatorname{rank}\le r-1$）的负 witness**：位于列空间的正交补中，是一个把目标与所有可用向量分开的超平面，证明所有 $r$ 维目标都无法被生成。直觉：秩亏了，列空间外有整整 $n-r+1$ 维的"空旷区"可以安放分离超平面。

将这个 high-level span program 的输入向量进一步展开为 entry 查询的普通 span program 后，Reichardt 双反射算法完成判定。成本的记账也相应分两层：

$$
\text{总查询数}
\;=\;
\underbrace{O\big(W(P)\big)}_{\text{双反射算法调用向量级反射的次数}}
\;\times\;
\underbrace{T}_{\text{每次向量级反射的 entry 查询成本}} .
$$

这就是最终复杂度公式呈现乘法结构的原因：组合结构与数值条件进入 $W(P)$，访问方式进入 $T$。接下来两小节分别估计 $W(P)$ 的两个因子。

### 3.5 正 witness 的伪逆系数：$rL^2$ 的推导

本小节做全文最重要的一次计算：**正 witness 的伪逆系数平方和是 $\sum_{j=1}^r\sigma_j^{-2}=rL^2$**。为此先把伪逆需要的三条性质完整推导出来。

设 $A$ 是 yes 实例，$\operatorname{rank}(A)=r^\ast\ge r$；为书写简单取承诺中最整齐的情形 $r^\ast=r$（更大的秩只会让前 $r$ 个奇异值更靠前，不改变估计的方向）。写 SVD：

$$
A=\sum_{j=1}^{r}\sigma_j\,u_j v_j^{\mathsf T},
\qquad
\sigma_1\ge\cdots\ge\sigma_r\ge\gamma>0 .
$$

**Moore–Penrose 伪逆**经 SVD 定义为

$$
A^+=\sum_{j=1}^{r}\frac{1}{\sigma_j}\,v_j u_j^{\mathsf T}
\qquad (m\times n\ \text{矩阵}).
$$

**性质一（两个投影恒等式）**. $AA^+$ 是到列空间 $\operatorname{span}\{u_1,\ldots,u_r\}$ 的正交投影，$A^+A$ 是到行空间的正交投影。

**验证**. 直接相乘并用 $\{v_j\}$、$\{u_j\}$ 的正交归一性（$v_j^{\mathsf T}v_l=\delta_{jl}$，$u_j^{\mathsf T}u_l=\delta_{jl}$）：

$$
AA^+=\sum_{j,l\le r}\sigma_j\cdot\frac{1}{\sigma_l}\;u_j\,(v_j^{\mathsf T}v_l)\,u_l^{\mathsf T}
=\sum_{j=1}^{r}u_j u_j^{\mathsf T},
$$

最后一个表达式恰是到 $\operatorname{span}\{u_1,\ldots,u_r\}$ 的正交投影（在这组正交归一基上逐分量投影再相加）。同理 $A^+A=\sum_j v_jv_j^{\mathsf T}$。$\blacksquare$

**性质二（最小范数解）**. 设 $b\in\operatorname{range}(A)$，则 $x^\ast=A^+b$ 满足 $Ax^\ast=b$；且对任何满足 $Ax=b$ 的 $x$ 有 $\|x\|\ge\|x^\ast\|$，等号当且仅当 $x=x^\ast$。

**证明**. 先证 $x^\ast$ 是解：$Ax^\ast=(AA^+)b=b$，因为 $b$ 已在列空间中，被投影 $AA^+$ 保持不动（性质一）。

再证解集的结构。设 $Ax=b$，则 $A(x-x^\ast)=0$，即 $x-x^\ast\in\ker A$。计算核空间：由 SVD，$Av_i=\sigma_i u_i$（Lemma 1 第二步），故 $\sigma_i=0$ 的 $v_i$（即 $i>r$，若 $\min(n,m)>r$）张成核的一部分；又 $\dim\ker A=m-r$ 恰好等于这些 $v_i$ 的个数，所以

$$
\ker A=\operatorname{span}\{v_i:\ i>r\},
\qquad
\operatorname{range}(A^+)=\operatorname{span}\{v_j:\ j\le r\},
$$

两者在正交归一系 $\{v_1,\ldots,v_{\min(n,m)}\}$ 下显然互相正交。于是任意解可写为 $x=x^\ast+z$，$z\in\ker A$ 且 $z\perp x^\ast$，由勾股定理

$$
\|x\|^2=\|x^\ast\|^2+\|z\|^2\;\ge\;\|x^\ast\|^2,
$$

等号当且仅当 $z=0$。Q.E.D.

最小范数性质说明：**在把目标写成"列向量作用的组合"的所有方式中，伪逆给出的系数是欧氏范数最小的**——正 witness 要的就是它（witness 成本是系数平方和，span program 的正 witness 定义允许任取系数，最优取法即伪逆）。

**Proposition 7**. 把目标方向取为列空间的正交基 $u_1,\ldots,u_r$，则伪逆系数的平方和为

$$
\sum_{j=1}^{r}\big\|A^+u_j\big\|^2=\sum_{j=1}^{r}\sigma_j^{-2}=rL^2 .
$$

**证明**. 对每个 $j$，用 $\{u_l\}$ 的正交归一性直接计算 $A^+u_j$：

$$
A^+u_j=\sum_{l=1}^{r}\frac{1}{\sigma_l}\,v_l\,(u_l^{\mathsf T}u_j)=\frac{1}{\sigma_j}\,v_j ,
$$

故 $\|A^+u_j\|^2=\sigma_j^{-2}\,\|v_j\|^2=\sigma_j^{-2}$（$v_j$ 是单位向量）。对 $j=1,\ldots,r$ 求和，再用 $L$ 的定义移项：

$$
\sum_{j=1}^{r}\sigma_j^{-2}=r\cdot\frac1r\sum_{j=1}^r\sigma_j^{-2}=rL^2 . \qquad\text{Q.E.D.}
$$

这就把第 1.4 节的断言"正 witness 使用伪逆，因而复杂度含 $L$"落实成了逐项计算。也顺便解释了为什么度量病态用的是**倒数均方根**而不是最大倒数：witness 成本天生是平方和结构（欧氏范数的平方），把 $\sigma_1^{-2},\ldots,\sigma_r^{-2}$ 加起来再除 $r$、开方，正是 $L$。

把 Proposition 7 与 Lemma 3 合并阅读：正 witness 成本 $rL^2$ 夹在 $r/\sigma_1^2$ 与 $r/\sigma_r^2$ 之间；病态（某个 $\sigma_j$ 接近 $\gamma$）时它被 $r/\gamma^2$ 控制，良态归一化时约为 $r$。

### 3.6 负 witness 与组合因子

现在看 no 侧。设输入是 no 实例，$\operatorname{rank}(A)\le r-1$，列空间 $V=\operatorname{span}\{a_1,\ldots,a_m\}$ 的维数至多 $r-1$，于是正交补

$$
V^\perp=\{\,z\in\mathbb R^n:\ \langle z,a_j\rangle=0\ \forall j\,\}
$$

的维数至少 $n-(r-1)=n-r+1$（子空间正交补的维数公式：$\dim V+\dim V^\perp=n$）。任取 $V^\perp$ 中的单位向量 $z$，它与**所有**可用向量（所有列）正交，这正是负 witness"分离超平面"的原型：它够不到目标向量（目标在顶层，与列空间无关），却把可用向量全部隔开。

对成本的贡献（定性）：负 witness 需要在层级结构中"封锁"所有 $r$ 维目标，可用的自由度是正交补的维数 $n-r+1$；直观上 wsize$_0$ 的组合部分按 $n-r+1$ 的量级增长。把它与正 witness 的 $rL^2$ 按第 3.3 节的几何平均合并：

$$
W(P)\;\sim\;\sqrt{\,(\text{正 witness：}rL^2)\times(\text{负 witness：}\sim n-r+1)\,}
\;=\;\sqrt{r\,(n-r+1)}\;\cdot\;L ,
$$

（这里"$\sim$"表示量级上的对应；精确常数与层级构造的细节见 Belovs 原文。）两个因子的分工一目了然：

- $\sqrt r$ 来自**正侧**：要同时支起 $r$ 个独立方向，伪逆系数对 $r$ 个目标方向各贡献一份；
- $\sqrt{n-r+1}$ 来自**负侧**：秩亏得越少（$r$ 越接近 $n$），正交补越小，负 witness 越便宜；而 $r$ 小时正交补大，负 witness 贵。

原文把 $\sqrt{r(n-r+1)}$ 称为**组合层级**因子——它只依赖维数组合 $(n,m,r)$，与矩阵的数值条件无关；数值条件全部被 $L$ 吸收。第 4.4 节会把这个因子当作 $r$ 的函数来优化。

## 4. 查询复杂度公式逐项解读

(complexity-formula-factors)=
### 4.1 总公式与乘法结构

Zoo 所收录的上界可写为

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

按第 3.4 节的两层记账，这个乘积的三个因子各有出处：

- $\sqrt{r(n-r+1)}$：span program 的**组合层级**因子，来自 witness size 的几何平均中与数值无关的部分（第 3.6 节）；
- $L$：**数值条件**因子，来自正 witness 的伪逆系数（Proposition 7）；
- $T$：**相干加载/反射一个矩阵向量**（一列）的查询成本，即把向量级 oracle 的一次调用展开成 entry 查询的代价。

注意各因子独立取最坏：$Q$ 是对满足承诺的所有输入的上界，$L$ 按 $1/\gamma$ 控制，$T$ 按访问模型确定。下面两小节分别算出两种访问模型下的 $T$。

### 4.2 Dense entry oracle：$T=O(\sqrt{nm})$

对一般 dense 矩阵，只有第 1.1 节的 entry oracle 可用。向量级反射作用在"列索引 $\oplus$ 列内容"的联合寄存器上：列索引寄存器有 $m$ 个取值；给定列后，该列的归一化向量态有 $n$ 个振幅分量，一般幅值互不相同、不可先验地描述。用 entry oracle 相干地实现这个反射，等价于在全部 $nm$ 个振幅自由度上做一次 Grover 型的振幅装载：从均匀初始分布出发，把振幅转移到由矩阵数据决定的目标分布，最坏情形下二者的重叠只有 $O(1/\sqrt{nm})$ 量级，用[振幅放大](../ch03-algo-basics/grover.md)把它抬到常数需要 $O(\sqrt{nm})$ 次反射调用。于是

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

（这是该模型下一般态制备的标准成本量级；精确常数与实现细节有关，不影响本教程的定性结论。）注意这个 $T$ 与第 2.2 节的 Grover 界出自同一种"平方根"机制——$nm$ 个未知自由度上的搜索/装载，量子付出平方根代价。

### 4.3 Sparse oracle：$T=O(k\log(n+m))$，以及一个重要警告

若矩阵结构已知稀疏——每行、每列最多 $k$ 个非零 entry——并且我们拥有一个 **sparse oracle**：给定列 $j$，它能列出该列的全部非零位置与值（邻接表式访问），那么装载第 $j$ 列的归一化向量态只需读出至多 $k$ 个"位置—值"对。每个位置索引 $i\in[n]$ 或 $j\in[m]$ 需要 $O(\log n)$、$O(\log m)$ 位寄存器操作，合计每个非零元 $O(\log(n+m))$ 位的开销，共 $k$ 个非零元：

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

行、列两方向的稀疏性约束共同保证反射的两侧（列选择与列内容）成本都由 $k$ 控制。

**警告（模型依赖，务必保留）**：后者使用的 oracle 比逐 entry 查询更强；若只有 entry oracle，寻找一列中的 $k$ 个非零位置本身也需要搜索，不能免费采用 sparse 上界。事实上，在只有 entry oracle 时，"定位一列的非零元"就是一次多目标搜索：用多解 Grover 的量级是 $\sqrt{n/k}$（$k=1$ 时退化为熟悉的 $\sqrt n$），远大于 $k\log(n+m)$。换句话说，"矩阵稀疏"这个**性质**与"有稀疏访问的 **oracle**"是两回事：前者是输入的数学性质，后者是计算模型的一部分。声明加速时必须同时声明模型——这也是本章导言强调查询/时间/数据结构成本分开记账的原因之一。

### 4.4 组合因子的最坏位置：一次参数平衡

复杂度表达式里的组合因子 $\sqrt{r(n-r+1)}$ 随阈值 $r$ 变化，问"哪个 $r$ 最贵"是一次标准的参数平衡。把

$$
f(r)=r\,(n-r+1)
$$

当作 $r$ 的（形式上连续的）函数求导：

$$
f'(r)=(n-r+1)+r\cdot(-1)=n+1-2r .
$$

令 $f'(r)=0$ 解出

$$
r^\ast=\frac{n+1}{2},
\qquad
f(r^\ast)=\frac{n+1}{2}\cdot\Big(n-\frac{n+1}{2}+1\Big)=\frac{(n+1)^2}{4},
\qquad
\sqrt{f(r^\ast)}=\frac{n+1}{2},
$$

其中第二个等号用了 $n-\frac{n+1}{2}+1=\frac{n+1}{2}$。$f$ 是开口向下的二次函数，故 $r^\ast$ 是最大值点；实际取最接近 $\frac{n+1}{2}$ 的整数即可。再看两端：

$$
f(1)=1\cdot n=n,\ \text{故}\ \sqrt{f(1)}=\sqrt n;\qquad
f(n)=n\cdot1=n,\ \text{故}\ \sqrt{f(n)}=\sqrt n .
$$

整理成一张量级表：

$$
\begin{array}{c|ccc}
r & 1 & \approx\frac{n+1}{2} & n\\ \hline
\sqrt{r(n-r+1)} & \sqrt n & \approx\frac{n+1}{2} & \sqrt n
\end{array}
$$

中间比两端贵约 $\frac{n+1}{2\sqrt n}\approx\frac{\sqrt n}{2}$ 倍。这解释了原文所说的"目标秩 $r$ 远离使组合因子最坏的位置"：判满秩（$r=n$）或判"至少一维"（$r=1$）在组合上最便宜，判"大约半满秩"最贵。负 witness 的直觉（第 3.6 节）与此完全吻合：$r$ 小则正交补 $n-r+1$ 大、负 witness 贵；$r$ 大则要支起的方向多、正 witness 贵；两头相乘在中间达到峰值。

**一个量级演示**（数字仅为算术演示，常数与对数底不影响结论）。取 $n=m=100$、$k=3$、良态 $L\approx1$：

- sparse oracle：$\log_2(n+m)=\log_2 200\approx7.6$，最坏阈值 $r\approx50$ 给 $\sqrt{50\cdot51}\approx50.5$，合计 $Q\approx50.5\times1\times3\times7.6\approx1.2\times10^3$，对比经典 $nm=10^4$，约一个数量级的节省；
- 同参数下 dense oracle：$T=\sqrt{nm}=100$，$Q\approx50.5\times100\approx5.1\times10^3$，只省两倍——访问模型的差别被乘法结构直接放大；
- 若阈值取 $r=1$（即"矩阵是否非零"），组合因子降到 $\sqrt{100}=10$，sparse 情形 $Q\approx2.3\times10^2$，回到 Grover 量级。

## 5. Determinant 特例：上界与下界为何不矛盾

### 5.1 $\det A=0$ 就是秩亏

对方阵（$n=m$），判断

$$
\det A=0
$$

等价于判断秩是否小于 $n$。这一等价可以直接从第 3.1 节的外代数刻画读出，不必另起炉灶：取 $r=n$，$\Lambda^n(\mathbb F^n)$ 是一维空间，基向量是 $e_1\wedge\cdots\wedge e_n$，而

$$
a_1\wedge\cdots\wedge a_n=\det(A)\;e_1\wedge\cdots\wedge e_n ,
$$

（$n=2$ 的手算版本已在第 3.1 节算过：系数恰是 $\alpha\delta-\beta\gamma$。）由 Lemma 6，楔积非零当且仅当 $n$ 列线性无关，即 $\det A\ne0\iff\operatorname{rank}(A)=n$。于是 determinant 判定是秩判定在 $r=n$ 处的特例，第 4.4 节的表还告诉我们它的组合因子是最便宜的 $\sqrt n$ 一档。

(determinant-lower-bound)=
### 5.2 $\Omega(n^2)$ 下界与三个有利区域

但这个特例有一个著名的否定性结果：**无承诺的一般 determinant query problem 有 $\Omega(n^2)$ 级量子下界**（Dörn–Thierauf，Zoo 编号 151），与读取所有 $n^2$ 个 entry 同阶——上界是平凡的"全读"，因此量级上是 $\Theta(n^2)$，不存在普适的 entry-query 加速。下界的直觉与第 2.1 节的经典对手构造同源：一个未读的 entry 就可能单独决定矩阵是否奇异（把第 2.1 节的 $A(x)$ 构造取 $r=n$ 即是一例），量子算法的相干查询无法逃避这种敏感性；其严格证明采用查询复杂度的标准下界技术（多项式方法/对抗界），细节见原文。

这与第 4 节的上界矛盾吗？不矛盾。上界公式里除了维数因子外还有两个"逃逸阀门"——$L$ 与 $T$——而 determinant 下界的实例恰好把两个阀门同时拧到最坏：

1. **矩阵 dense 且只有 entry oracle**：$T=O(\sqrt{nm})=O(n)$，加载无便宜可占；
2. **病态、恰好接近奇异**：$\gamma\to0$ 使 $L=O(1/\gamma)\to\infty$，任何以 $\gamma$ 为界的估计都失效；
3. 下界允许的是**最坏实例**，而上界的有用区域需要同时避开这些最坏情形。

逐区域检查后，span-program 上界真正有用的区域是：

1. **矩阵稀疏且 sparse oracle 可用**：$T$ 从 $O(\sqrt{nm})$ 降到 $O(k\log(n+m))$；
2. **目标秩 $r$ 远离使组合因子最坏的位置**：$r$ 接近 $1$ 或 $n$ 时 $\sqrt{r(n-r+1)}$ 只有 $\sqrt n$ 量级，而非 $\approx n/2$（第 4.4 节）；
3. **非零奇异值有下界，使 $L$ 不大**：承诺 $\sigma_r\ge\gamma$ 且 $\gamma$ 不是灾难性地小，$L\le1/\gamma$ 有界（Lemma 3）。

三个区域分别压制公式中的一个因子；下界实例则可以同时是 dense、病态、恰好接近奇异的，因此被排除在所有区域之外。"加速来自条件与结构承诺"这句总结，在这三个区域的对号入座里得到了完全具体的含义。

## 6. 数值小例子

### 6.1 对角矩阵 $\operatorname{diag}(1,1,\epsilon,0)$

令

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

（取 $\epsilon>0$ 是为了让奇异值不必写绝对值；$\epsilon<0$ 时符号可吸收进 SVD 的右奇异向量，不影响任何计算。）

**奇异值**。$A^{\mathsf T}A=\operatorname{diag}(1,1,\epsilon^2,0)$ 是对角矩阵，特征值就是对角元 $1,1,\epsilon^2,0$；奇异值是 $A^{\mathsf T}A$ 特征值的平方根的递减排列：

$$
\sigma_1=1,\qquad \sigma_2=1,\qquad \sigma_3=\epsilon,\qquad \sigma_4=0 .
$$

**秩**。非零奇异值有 $3$ 个（$\epsilon\ne0$），由 Lemma 1，$\operatorname{rank}(A)=3$。

**测试 $r=3$**（yes 实例，承诺 $\sigma_3=\epsilon\ge\gamma$，$\sigma_4=0$ 自动成立）。按定义展开：

$$
L=\left(\frac{\sigma_1^{-2}+\sigma_2^{-2}+\sigma_3^{-2}}{3}\right)^{1/2}
=\left(\frac{1+1+\epsilon^{-2}}{3}\right)^{1/2}
=\sqrt{\frac{2+\epsilon^{-2}}{3}} .
$$

当 $\epsilon\to0$ 时 $\epsilon^{-2}$ 项主导分子，故渐近地

$$
L\;\sim\;\frac{1}{\sqrt3\,\epsilon} .
$$

顺手用 Lemma 3 验证夹逼：应有 $L\le1/\sigma_3=1/\epsilon$。验证：

$$
\frac{2+\epsilon^{-2}}{3}\le\epsilon^{-2}
\iff 2+\epsilon^{-2}\le3\epsilon^{-2}
\iff 2\le2\epsilon^{-2}
\iff \epsilon^2\le1 ,
$$

对 $0<\epsilon\le1$ 成立；下界 $L\ge1/\sigma_1=1$ 也显然满足。即使矩阵只有 **3 个非零 entry**，$\epsilon$ 很小时查询/精度成本仍随 $1/\epsilon$ 增大——代入第 4.1 节，$Q=O(\sqrt{3\cdot2}\;L\;T)$，$L\sim1/(\sqrt3\,\epsilon)$ 把整个复杂度拖着走。这与第 1.3 节的精度论证一致：区分 $\epsilon=0$ 与 $\epsilon\ge\gamma$ 需要 $O(\log(1/\gamma))$ 位的数值分辨率。**这是数值线性代数中的稳定性现象，不是量子算法设计缺陷**——经典算法面对同一矩阵同样要为接近奇异的 $\sigma_3$ 付出精度代价（对照"数值秩"的容差处理）。

**若只测试 $r=2$**，按定义使用最大的两个奇异值 $\sigma_1=\sigma_2=1$：

$$
L=\left(\frac{1+1}{2}\right)^{1/2}=1 .
$$

同一个矩阵、同一个 oracle，阈值从 $3$ 改到 $2$，条件因子从 $\sim1/(\sqrt3\,\epsilon)$ 掉到 $1$：**秩阈值承诺会实质改变复杂度**。直观地，判"秩 $\ge2$"只需要前两个方向的信息，$\epsilon$ 所在的第三个方向根本不进入 witness；这也再次印证第 3.5 节的公式——$L$ 只对前 $r$ 个奇异值求和。

### 6.2 $2\times2$ 矩阵的完整 witness 计算

把第 3.5、3.6 节的两类 witness 在一个能算到底的例子上走一遍。取

$$
A=\operatorname{diag}(1,\epsilon)\quad(n=m=2,\ r=2,\ 0<\epsilon) .
$$

选对角矩阵是因为它的奇异向量恰是标准基，便于手算；一般矩阵需先做 SVD。

**楔积与 minor（第 3.1 节的链条）**。列向量 $a_1=e_1$，$a_2=\epsilon e_2$，

$$
a_1\wedge a_2=e_1\wedge(\epsilon e_2)=\epsilon\,(e_1\wedge e_2) .
$$

$\epsilon\ne0$ 时非零，由 Lemma 6 两列线性无关，$\operatorname{rank}=2$，唯一的 $2\times2$ minor（即 $\det A=\epsilon$）非零，判定答案"是"。

**正 witness（yes 侧）**。奇异值为 $\sigma_1=1,\sigma_2=\epsilon$，左奇异向量 $u_1=e_1,u_2=e_2$。伪逆按 SVD 定义（对可逆方阵就是逆）：

$$
A^+=\operatorname{diag}(1,\epsilon^{-1}) .
$$

对两个目标方向分别计算伪逆系数：

$$
A^+u_1=A^+e_1=e_1,\qquad \|A^+u_1\|^2=1=\sigma_1^{-2};
$$

$$
A^+u_2=A^+e_2=\epsilon^{-1}e_2,\qquad \|A^+u_2\|^2=\epsilon^{-2}=\sigma_2^{-2}.
$$

平方和

$$
1+\epsilon^{-2}=\sigma_1^{-2}+\sigma_2^{-2}=2L^2,
\qquad
L=\left(\frac{1+\epsilon^{-2}}{2}\right)^{1/2}\;\sim\;\frac{1}{\sqrt2\,\epsilon}\ (\epsilon\to0) ,
$$

与 Proposition 7 的逐项计算严丝合缝。也可以直接换一组目标验证"伪逆最小范数"：比如把目标取成 $b=u_1+u_2$（未归一化），则 $A^+b=e_1+\epsilon^{-1}e_2$ 是 $Ax=b$ 的解中范数最小者（性质二），任何其他解都多出一个核方向的分量——本例 $A$ 满秩、核为零，解唯一，退化情形下（$\epsilon=0$）核才出现。

**负 witness（no 侧）**。取 $\epsilon=0$，即 $A_0=\operatorname{diag}(1,0)$，$\operatorname{rank}(A_0)=1\le r-1$，测试 $r=2$ 是 no 实例。列空间 $V=\operatorname{span}\{e_1\}$，维数 $1$；正交补

$$
V^\perp=\operatorname{span}\{e_2\},\qquad \dim V^\perp=2-1=1=n-r+1 ,
$$

（$n-r+1=2-2+1=1$，与第 3.6 节的维数计数一致。）取 $z=e_2$：$\langle z,a_1\rangle=\langle e_2,e_1\rangle=0$、$\langle z,a_2\rangle=\langle e_2,0\rangle=0$，$z$ 与全部可用向量正交，是一张合格的分离超平面。它够不到任何需要"第二个方向"的目标——这个 $1$ 维的空旷区正是"秩亏一"的全部几何。

**代入复杂度**。$r=n=2$ 时组合因子 $\sqrt{2(2-2+1)}=\sqrt2$。sparse oracle（此例 $k=1$）给 $T=O(\log 4)=O(1)$，总查询 $O(\sqrt2\,L\,T)=O(L)\sim O(1/\epsilon)$；$\epsilon$ 固定时为常数次查询，而经典算法必须读满 $nm=4$ 个 entry 才能确定秩（第 2.1 节）。麻雀虽小，公式的每个因子都在。

### 6.3 稳定性的解读

两个例子指向同一件事：复杂度公式里 $L$ 的位置，就是数值线性代数里"条件数"的位置。接近降秩的矩阵无论对经典还是量子算法都难——经典体现在迭代求解的收敛步数或消去的数值爆炸，量子体现在 witness 系数（伪逆范数）与所需的相位分辨率。把这类成本归为"稳定性成本"而不是"算法缺陷"，有助于正确设置预期：承诺 $\gamma$ 应当来自问题本身（例如物理模型给出尺度下界），而不是为了让量子算法好看而人为塞进模型。

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

### 7.1 对 $r$ 的二分与递增

判定是"是/否"，实际任务常常是求出秩这个整数。可对不同 $r$ 做二分或递增判定来找最大可接受阈值，但有两个不能省的附加成本：

**每次都需要相应的奇异值 gap**。第 $r$ 层的判定需要该层的承诺（$\sigma_r\ge\gamma$ 对 $\sigma_r=0$）。若矩阵的谱在中间某处连续地衰减（没有明显的数值间隙），中间阈值既不满足 yes 侧也不满足 no 侧的承诺，判定器对它没有保证——这正是第 1.3 节"数值秩"概念的用武之地：把阈值两侧的容差显式写进承诺。

**总成本由最难阈值主导**。设精确秩为 $\rho$。递增策略（$r=1,2,\ldots,\rho$ 依次判定，第一次回答"否"即停）的总查询为

$$
\sum_{r=1}^{\rho}O\!\big(\sqrt{r(n-r+1)}\;L_r\;T\big)
\;\le\;
\rho\cdot\max_{1\le r\le\rho}O\!\big(\sqrt{r(n-r+1)}\;L_r\;T\big),
$$

上界由最难的那个阈值（通常是 $r$ 最接近 $\frac{n+1}{2}$、且 $L_r$ 最大者）乘以调用次数给出。二分策略只需 $O(\log n)$ 次判定，但二分路径上的中间阈值同样必须各自满足 gap 承诺。无论哪种策略，"主导阈值"的三个因子与第 4 节相同——求精确秩没有引入新的复杂度机制，只是把判定器当作子程序多次调用。

### 7.2 输出独立列集合：self-reduction

若还要输出一组具体的 $r$ 个线性无关列（一个 witness），可在判定 oracle 上做 **self-reduction**。维护已选列集 $S$（初始为空），对每个候选列 $j$ 调用判定器测试 $\operatorname{rank}(A_{S\cup\{j\}})\ge|S|+1$ 是否成立：成立则把 $j$ 加入 $S$，否则跳过。正确性的论证很短：

- **跳过无害**：若测试不成立，则 $a_j\in\operatorname{span}\{a_l:l\in S\}$（否则 $S\cup\{j\}$ 的秩超过 $|S|$），丢弃它不损失任何秩；
- **终止正确**：过程结束时每个未被选入的列都在 $\operatorname{span}(S)$ 中，故 $|S|=\operatorname{rank}(A)$（交换引理保证贪心选择总能扩展到极大无关组）。

调用次数至多 $m$ 次（线性因子）；用分组测试或对候选区间做二分的变体可以把额外因子降到对数。输出的 witness 本身只有 $r$ 个列索引，写出来花 $O(r\log m)$ 位，不构成瓶颈。

### 7.3 判定秩不等于输出 SVD

最后划清输出规模的边界："少查询判定秩"不等于输出 SVD。完整的 SVD 包含 $U,\Sigma,V$ 三个矩阵，共 $\Theta(nm)$ 个经典 entry 的输出规模，**任何**算法（量子与否）写出它们都要 $\Omega(nm)$ 时间——输出本身成了下界。因此本教程的查询优势只在"输出一个整数（秩）或少量 witness（列索引集）"这类轻量输出上才有意义；想把 SVD 整个搬出来，复杂度叙事必须切换到时间模型并重新核算（包括第 4 节所有 oracle 的实现成本）。这与本章导言"避免把查询优势误写成无条件时间优势"的告诫是同一件事的两个侧面。

## 8. 本课小结

- 秩阈值可由线性独立/外代数 span program 表示：$\operatorname{rank}\ge r$ 等价于存在非零的 $r$ 重楔积，等价于存在非零 $r\times r$ minor。
- 正 witness 使用伪逆，因而复杂度含非零奇异值倒数均方根 $L$；伪逆的最小范数性质保证它就是最优系数。
- Dense 与 sparse 上界依赖不同 oracle；稀疏性本身不能替代稀疏访问。
- 一般 determinant 问题无查询加速，优势来自条件与结构承诺（稀疏访问、阈值位置、奇异值 gap 三个区域）。
- 组合因子 $\sqrt{r(n-r+1)}$ 在 $r=\frac{n+1}{2}$ 处最坏（约 $n/2$），在 $r=1$ 或 $r=n$ 处最便宜（$\sqrt n$）。
- 判定秩、输出独立列 witness、输出完整 SVD 是输出规模递增的三档任务；查询优势只属于前两档。

## 练习题

**练习 1【黑盒模型与秩判定问题】**（→ [1.1 节](#query-model-rank-problem)）

1. 写出 entry oracle $O_A$ 对基态 $|i,j,b\rangle$ 的作用式，并说明"一次查询"与"实现 oracle 及算术的门开销"在记账上的区别。
2. 设某算法用 $O(\sqrt{nm})$ 次查询判定 $r=1$，而每次查询需 $O(\log(nm))$ 个门实现索引与算术。分别写出它的查询复杂度与时间复杂度，并说明两者为何可能相差多项式因子。

**练习 2【秩的奇异值刻画】**（→ [1.2 节](#rank-singular-value)）

1. 求 $A=\operatorname{diag}(3,4,0)$ 的奇异值与秩，并验证"秩恰为非零奇异值的个数"。
2. 复述 Lemma 1 证明中"列空间 $\subseteq\operatorname{span}\{u_j:\sigma_j>0\}$"与反向包含两步各用到 SVD 的哪条性质，再把结论改写为 $\operatorname{rank}(A)\ge r\iff\sigma_r>0$。

**练习 3【奇异值 gap 承诺的必要性】**（→ [1.3 节](#gap-promise)）

1. 写出本教程采用的 yes/no 实例承诺形式，并说明 yes 实例的秩恰为 $r$、no 实例的秩至多 $r-1$。
2. 设 oracle 只返回 $p$ 位定点近似。仿照 Lemma 2，取实例 $x=0$ 与 $x=\delta$（$0<\delta<2^{-p-1}$），证明任何算法判定 $1\times1$ 矩阵是否满足 $\operatorname{rank}\ge1$ 的误差必 $\ge\frac12$。

> 提示：两个实例上 oracle 的应答分布完全相同，故输出分布相同，两个错误概率之和为 $1$。

**练习 4【条件数型因子 L】**（→ [1.4 节](#condition-number-factor)）

1. 设 $\sigma_1=2$、$\sigma_2=1$，按定义计算 $L$，并验证 Lemma 3 的夹逼 $\frac{1}{\sigma_1}\le L\le\frac{1}{\sigma_r}$。
2. 对 $\operatorname{diag}(1,\epsilon,0)$（$\epsilon>0$）分别计算 $r=1,2$ 的 $L$，并解释为什么 $r=1$ 的答案与 $\epsilon$ 无关。
3. 证明 Lemma 3 的夹逼 $\frac{1}{\sigma_1}\le L\le\frac{1}{\sigma_r}$ 及加强下界 $L\ge\frac{1}{\sqrt r\,\sigma_r}$，并说明左边取等的条件。

> 提示：$r$ 个被平均的数都落在 $[\sigma_1^{-2},\sigma_r^{-2}]$ 内，且平均值不小于最大一项的 $1/r$。

**练习 5【经典查询下界】**（→ [2.1 节](#classical-lower-bound-matrix-rank)）

1. 对 $A_{11}=x$、$A_{jj}=1$（$j=2,\ldots,r$）、其余 entry 为 $0$ 的矩阵 $A(x)$，分别求 $x=0$ 与 $x=1$ 时的秩，并指出两个矩阵在几个 entry 上不同。
2. 把"$r=1$ 的秩判定就是 $\mathrm{OR}_{nm}$"写成等价链 $\operatorname{rank}(A)\ge1\iff A\ne0\iff\bigvee_{i,j}[A_{ij}\ne0]$，并解释 Lemma 5 中 $\Pr[\text{算法查询到 }P]\le\frac{t}{nm}$ 一步为何对自适应的随机算法也成立。

> 提示：$P$ 与算法的随机性独立且均匀分布，$t$ 次查询至多试探 $t$ 个位置。

**练习 6【外代数刻画与 witness 估计】**（→ [3.1 节](#exterior-algebra-witness)）

1. 设 $a_1=\alpha e_1+\beta e_2$、$a_2=\gamma e_1+\delta e_2$，按多线性与反对称性展开 $a_1\wedge a_2$，并指出结果与 $2\times2$ 行列式的关系。
2. 证明 $\operatorname{rank}\ge r$ 等价于某个 $r$ 重楔积非零。
3. 完整证明 Moore–Penrose 伪逆的最小范数性质（第 3.5 节性质二），并据此说明：当目标方向取左奇异向量 $u_j$ 时，正 witness 的贡献恰为 $\sigma_j^{-2}$；再讨论把目标换成标准基 $e_i$ 时贡献如何变化（是否仍为 $\sum_j\sigma_j^{-2}$？）。

> 提示：第 2 题把 Lemma 6 的两个方向分别用于"存在性"与"全称性"。

**练习 7【复杂度公式逐因子解读】**（→ [4.1 节](#complexity-formula-factors)）

1. 写出总查询复杂度 $Q=O\big(\sqrt{r(n-r+1)}\,L\,T\big)$，并说明三个因子分别来自 witness size 的哪一侧、哪一层记账。
2. 证明 $f(r)=r(n-r+1)$ 在 $r=\frac{n+1}{2}$ 处取最大值，并计算 $r=1$、$r=\frac{n+1}{2}$、$r=n$ 三处 $\sqrt{f(r)}$ 的值与最大最小之比。
3. 比较 entry oracle 与 sparse-list oracle 能提供的信息：给出一个矩阵族，使得两种 oracle 下的 $T$ 相差多项式倍；再说明用 entry oracle 模拟一次 sparse-list 查询（定位一列的非零元）需要多少量级的查询。

> 提示：第 3 题注意"定位一列的 $k$ 个非零元"是一次多目标搜索，量级 $\sqrt{n/k}$。

**练习 8【下界对照与任务边界】**（→ [5.2 节](#determinant-lower-bound)）

1. 说明对方阵判定 $\det A=0$ 等价于 $r=n$ 的秩判定，并从第 4.4 节的量级表读出它的组合因子。
2. 列出 determinant 下界实例把上界公式中的哪两个因子拧到最坏，并解释上界真正有用的三个区域分别压制公式中的哪个因子。
3. 解释为何求精确秩的整数输出不需要输出全部奇异向量；据此论证"输出 SVD 需要 $\Omega(nm)$ 时间"。

> 提示：SVD 要写出 $U,\Sigma,V$ 三个矩阵，输出本身就有 $\Theta(nm)$ 个 entry。

## 参考文献

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