量子矩阵秩判定

给定 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)}LT)$，并逐因子解释每一项的来源（第 4 节）；
4. 与 determinant 的 $\Omega (n^2)$ 量子下界对照，弄清上界在哪些参数区域真正有用、为什么与下界不矛盾（第 5 节）。

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

前置知识：的 Grover 算法（反射、振幅放大、$\sqrt{N}$ 加速）与相位估计；同章的 Boolean 公式求值：Span Program、对抗界与双反射算法（span program 的定义、正负 witness、witness size 与双反射算法，本词条第 3.3 节只做复习，不重新推导）； HHL 算法中关于条件数的讨论（对照 $L$ 的角色）。线性代数方面只需要 SVD 的基本性质，我们会在用到处证明。

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

1.1 黑盒模型中的秩判定

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

$$O_A:|i,j,b⟩\mapsto |i,j,b+A_{ij}⟩,i\in [n],j\in [m],$$

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

要解决的判定问题是：

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

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

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

1.2 秩与奇异值：判定条件的等价改写

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

$$A=\sum _{j=1}^{\min (n,m)}{\sigma }_j{u}_j{v}_j^{\mathsf{T}},{\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_{\min (n,m)}\ge 0,$$

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

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

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

第一步（列空间 $\subseteq$ 前 $r^{\prime }$ 个 $u_j$ 的张成，$r^{\prime }=\#\{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}}\left(\sum _l{c}_l{v}_l\right)=\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 \mathrm{span}\{u_j:{\sigma }_j>0\}$。

第二步（反向包含）。对每个 ${\sigma }_j>0$ 的 $j$，直接算 $A{v}_j$：

$$A{v}_j=\sum _l{\sigma }_l{u}_l{v}_l^{\mathsf{T}}{v}_j={\sigma }_j{u}_j⟹u_j=\frac{1}{{\sigma }_j}A{v}_j,$$

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

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

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

1.3 为什么必须有 gap 承诺

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

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

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

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

$$\text{yes 实例：}{\sigma }_r\ge \gamma >0,{\sigma }_{r+1}=0；\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$ 时查询与精度成本如何随之增长。

1.4 条件数型因子 $L$

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

$$L={\left(\frac{1}{r}\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}=r{L}^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 \frac{1}{r}\sum _{j=1}^r{\sigma }_j^{-2}\le {\sigma }_r^{-2},$$

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

$$\frac{1}{r}\sum _{j=1}^r{\sigma }_j^{-2}\ge \frac{1}{r}{\sigma }_r^{-2},$$

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

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

• 全部奇异值相等（${\sigma }_1=\cdots ={\sigma }_r=\sigma$）：$L=\frac{1}{\sigma }$，取到上界。归一化 ${\sigma }_1=1$ 且良态时 $L\approx 1$。
• 只有第 $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})$，而且这是最优的。

2.1 一个 entry 就能翻转答案

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

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

$$A(x):A_{11}=x,A_{jj}=1(j=2,\dots ,r),\text{其余 entry}=0.$$

$A(x)$ 除第一行第一列外是对角结构。当 $x=0$ 时非零列只有 $r-1$ 个标准基向量 $e_2,\dots ,e_r$，线性无关，故 $\mathrm{rank}(A(0))=r-1<r$；当 $x=1$ 时非零列是 $e_1,\dots ,e_r$ 共 $r$ 个，$\mathrm{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$ 的判定条件可以完全消去线性代数：

$$\mathrm{rank}(A)\ge 1⟺A\ne 0⟺\underset{i\in [n],j\in [m]}{\bigvee }[A_{ij}\ne 0],$$

即 $nm$ 个”entry 非零”事件的 OR。这正是 Grover 算法一节里反复研究的无结构搜索问题 ${\mathrm{OR}}_{nm}$。

Lemma 5. 判定 $r=1$ 的任意随机算法若以误差 $\le \frac{1}{3}$ 正确，期望查询次数 $t\ge \frac{2}{3}nm$。

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

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

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

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

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

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

$$\frac{2}{3}\le \frac{t}{nm}+\frac{1}{3}⟹t\ge \frac{2}{3}nm.\text{Q.E.D.}$$

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

2.3 历史脉络

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

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

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

3.1 外代数刻画：楔积与 minor

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

对 $r$ 个向量 $v_1,\dots ,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\},\dim {\Lambda }^r({\mathbb{F}}^n)=\left(\genfrac{}{}{0ex}{}{n}{r}\right).$$

先手算一个最小的例子，把抽象定义落到实处。设 $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 \underset{=0}{\underbrace{e_1\wedge e_1}}+\alpha \delta e_1\wedge e_2+\beta \gamma \underset{=-e_1\wedge e_2}{\underbrace{e_2\wedge e_1}}+\beta \delta \underset{=0}{\underbrace{e_2\wedge e_2}}=(\alpha \delta -\beta \gamma )e_1\wedge e_2.$$

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

Lemma 6. $v_1\wedge \cdots \wedge v_r=0$ 当且仅当 $v_1,\dots ,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,\dots ,v_{r-1}$ 里，一次在末位），由反对称性每一项都为零，故整个楔积为零。

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

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

推论. 下列等价：

$$\mathrm{rank}(A)\ge r⟺\exists 1\le j_1<\cdots <j_r\le m:a_{j_1}\wedge \cdots \wedge a_{j_r}\ne 0⟺\exists r\times r\text{minor}\ne 0.$$

证明. 第一个等价："$\mathrm{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 为什么浪费

推论把秩判定变成了”对 $\left(\genfrac{}{}{0ex}{}{m}{r}\right)$ 个对象做存在性判断”，最直接的想法是对所有 $r$ 元列子集做 Grover 搜索。这条路可行但浪费严重，原因有三层：

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

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

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

本小节把同章 Boolean 公式求值中详细推导过的框架压缩成一段回顾，只保留本词条要用的结论。

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

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

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

$$O(W(P))$$

次”实现输入相关反射”的查询正确判定。同章教程用 ${\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)$ 为模型，维数 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$）。
• 加载一列是层级间的转移：把 $a_j$ 楔入当前态（$k\to k+1$）或用 $a_j$ 对当前态做缩并（$k\to k-1$）。
• 目标向量$|\tau ⟩$ 放在顶层 ${\mathcal{H}}_r$，对应”支起一个 $r$ 维独立方向”。

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

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

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

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

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

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

3.5 正 witness 的伪逆系数：$r{L}^2$ 的推导

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

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

$$A=\sum _{j=1}^r{\sigma }_j{u}_j{v}_j^{\mathsf{T}},{\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}}(m\times n\text{矩阵}).$$

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

验证. 直接相乘并用 $\{v_j\}$、$\{u_j\}$ 的正交归一性（$v_j^{\mathsf{T}}{v}_l={\delta }_{jl}$，$u_j^{\mathsf{T}}{u}_l={\delta }_{jl}$）：

$$A{A}^{+}=\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}},$$

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

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

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

再证解集的结构。设 $Ax=b$，则 $A(x-x^{\ast })=0$，即 $x-x^{\ast }\in \ker A$。计算核空间：由 SVD，$A{v}_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=\mathrm{span}\{v_i:i>r\},\mathrm{range}(A^{+})=\mathrm{span}\{v_j:j\le r\},$$

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

$$\Vert x{\Vert }^2=\Vert x^{\ast }{\Vert }^2+\Vert z{\Vert }^2\ge \Vert x^{\ast }{\Vert }^2,$$

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

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

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

$$\sum _{j=1}^r\Vert A^{+}{u}_j{\Vert }^2=\sum _{j=1}^r{\sigma }_j^{-2}=r{L}^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,$$

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

$$\sum _{j=1}^r{\sigma }_j^{-2}=r\cdot \frac{1}{r}\sum _{j=1}^r{\sigma }_j^{-2}=r{L}^2.\text{Q.E.D.}$$

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

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

3.6 负 witness 与组合因子

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

$$V^{\perp }=\{z\in {\mathbb{R}}^n:⟨z,a_j⟩=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 的 $r{L}^2$ 按第 3.3 节的几何平均合并：

$$W(P)\sim \sqrt{(\text{正 witness：}r{L}^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. 查询复杂度公式逐项解读

4.1 总公式与乘法结构

Zoo 所收录的上界可写为

$$Q=O\left(\sqrt{r(n-r+1)}LT\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})$ 量级，用振幅放大把它抬到常数需要 $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(k\log (n+m)).$$

行、列两方向的稀疏性约束共同保证反射的两侧（列选择与列内容）成本都由 $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^{\prime }(r)=(n-r+1)+r\cdot (-1)=n+1-2r.$$

令 $f^{\prime }(r)=0$ 解出

$$r^{\ast }=\frac{n+1}{2},f(r^{\ast })=\frac{n+1}{2}\cdot (n-\frac{n+1}{2}+1)=\frac{(n+1{)}^2}{4},\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};f(n)=n\cdot 1=n,\text{故}\sqrt{f(n)}=\sqrt{n}.$$

整理成一张量级表：

$$\begin{array}{cccc}r& 1& \approx \frac{n+1}{2}& n\\ \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\approx 1$：

• sparse oracle：${\log }_2(n+m)={\log }_{2}200\approx 7.6$，最坏阈值 $r\approx 50$ 给 $\sqrt{50\cdot 51}\approx 50.5$，合计 $Q\approx 50.5\times 1\times 3\times 7.6\approx 1.2\times 10^3$，对比经典 $nm=10^4$，约一个数量级的节省；
• 同参数下 dense oracle：$T=\sqrt{nm}=100$，$Q\approx 50.5\times 100\approx 5.1\times 10^3$，只省两倍——访问模型的差别被乘法结构直接放大；
• 若阈值取 $r=1$（即”矩阵是否非零”），组合因子降到 $\sqrt{100}=10$，sparse 情形 $Q\approx 2.3\times 10^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\ne 0⟺\mathrm{rank}(A)=n$。于是 determinant 判定是秩判定在 $r=n$ 处的特例，第 4.4 节的表还告诉我们它的组合因子是最便宜的 $\sqrt{n}$ 一档。

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 \to 0$ 使 $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\le 1/\gamma$ 有界（Lemma 3）。

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

6. 数值小例子

6.1 对角矩阵 $\mathrm{diag}(1,1,ϵ,0)$

令

$$A=\mathrm{diag}(1,1,ϵ,0),0<ϵ\ll 1.$$

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

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

$${\sigma }_1=1,{\sigma }_2=1,{\sigma }_3=ϵ,{\sigma }_4=0.$$

秩。非零奇异值有 $3$ 个（$ϵ\ne 0$），由 Lemma 1，$\mathrm{rank}(A)=3$。

测试 $r=3$（yes 实例，承诺 ${\sigma }_3=ϵ\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+{ϵ}^{-2}}{3}\right)}^{1/2}=\sqrt{\frac{2+{ϵ}^{-2}}{3}}.$$

当 $ϵ\to 0$ 时 ${ϵ}^{-2}$ 项主导分子，故渐近地

$$L\sim \frac{1}{\sqrt{3}ϵ}.$$

顺手用 Lemma 3 验证夹逼：应有 $L\le 1/{\sigma }_3=1/ϵ$。验证：

$$\frac{2+{ϵ}^{-2}}{3}\le {ϵ}^{-2}⟺2+{ϵ}^{-2}\le 3{ϵ}^{-2}⟺2\le 2{ϵ}^{-2}⟺{ϵ}^2\le 1,$$

对 $0<ϵ\le 1$ 成立；下界 $L\ge 1/{\sigma }_1=1$ 也显然满足。即使矩阵只有 3 个非零 entry，$ϵ$ 很小时查询/精度成本仍随 $1/ϵ$ 增大——代入第 4.1 节，$Q=O(\sqrt{3\cdot 2}LT)$，$L\sim 1/(\sqrt{3}ϵ)$ 把整个复杂度拖着走。这与第 1.3 节的精度论证一致：区分 $ϵ=0$ 与 $ϵ\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$，条件因子从 $\sim 1/(\sqrt{3}ϵ)$ 掉到 $1$：秩阈值承诺会实质改变复杂度。直观地，判”秩 $\ge 2$“只需要前两个方向的信息，$ϵ$ 所在的第三个方向根本不进入 witness；这也再次印证第 3.5 节的公式——$L$ 只对前 $r$ 个奇异值求和。

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

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

$$A=\mathrm{diag}(1,ϵ)(n=m=2,r=2,0<ϵ).$$

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

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

$$a_1\wedge a_2=e_1\wedge (ϵe_2)=ϵ(e_1\wedge e_2).$$

$ϵ\ne 0$ 时非零，由 Lemma 6 两列线性无关，$\mathrm{rank}=2$，唯一的 $2\times 2$ minor（即 $\det A=ϵ$）非零，判定答案”是”。

正 witness（yes 侧）。奇异值为 ${\sigma }_1=1,{\sigma }_2=ϵ$，左奇异向量 $u_1=e_1,u_2=e_2$。伪逆按 SVD 定义（对可逆方阵就是逆）：

$$A^{+}=\mathrm{diag}(1,{ϵ}^{-1}).$$

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

$$A^{+}{u}_1=A^{+}{e}_1=e_1,\Vert A^{+}{u}_1{\Vert }^2=1={\sigma }_1^{-2};$$ $$A^{+}{u}_2=A^{+}{e}_2={ϵ}^{-1}{e}_2,\Vert A^{+}{u}_2{\Vert }^2={ϵ}^{-2}={\sigma }_2^{-2}.$$

平方和

$$1+{ϵ}^{-2}={\sigma }_1^{-2}+{\sigma }_2^{-2}=2L^2,L={\left(\frac{1+{ϵ}^{-2}}{2}\right)}^{1/2}\sim \frac{1}{\sqrt{2}ϵ}(ϵ\to 0),$$

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

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

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

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

代入复杂度。$r=n=2$ 时组合因子 $\sqrt{2(2-2+1)}=\sqrt{2}$。sparse oracle（此例 $k=1$）给 $T=O(\log 4)=O(1)$，总查询 $O(\sqrt{2}LT)=O(L)\sim O(1/ϵ)$；$ϵ$ 固定时为常数次查询，而经典算法必须读满 $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,\dots ,\rho$ 依次判定，第一次回答”否”即停）的总查询为

$$\sum _{r=1}^{\rho }O\left(\sqrt{r(n-r+1)}{L}_{r}T\right)\le \rho \cdot \underset{1\le r\le \rho }{\max }O\left(\sqrt{r(n-r+1)}{L}_{r}T\right),$$

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

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

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

• 跳过无害：若测试不成立，则 $a_j\in \mathrm{span}\{a_l:l\in S\}$（否则 $S\cup \{j\}$ 的秩超过 $|S|$），丢弃它不损失任何秩；
• 终止正确：过程结束时每个未被选入的列都在 $\mathrm{span}(S)$ 中，故 $|S|=\mathrm{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 表示：$\mathrm{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. 证明 $\mathrm{rank}\ge r$ 等价于某个 $r$ 重 wedge 非零。（提示：把第 3.1 节 Lemma 6 的两个方向分别用于”存在性”与”全称性”。）
2. 对 $\mathrm{diag}(1,ϵ,0)$（$ϵ>0$）分别计算 $r=1,2$ 的 $L$，并解释为什么 $r=1$ 的答案与 $ϵ$ 无关。
3. 比较 entry oracle 与 sparse-list oracle 能提供的信息：给出一个矩阵族，使得两种 oracle 下的 $T$ 相差多项式倍；再说明用 entry oracle 模拟一次 sparse-list 查询（定位一列的非零元）需要多少量级的查询。
4. 解释为何精确秩的整数输出不需要输出全部奇异向量；据此论证”输出 SVD 需要 $\Omega (nm)$ 时间”。
5. 证明 $f(r)=r(n-r+1)$ 在 $r=\frac{n+1}{2}$ 处取最大值，并计算 $r=1,r=\frac{n+1}{2},r=n$ 三处 $\sqrt{f(r)}$ 的值与最大最小之比。
6. 完整证明 Moore–Penrose 伪逆的最小范数性质（第 3.5 节性质二），并据此说明：当目标方向取左奇异向量 $u_j$ 时，正 witness 的贡献恰为 ${\sigma }_j^{-2}$；再讨论把目标换成标准基 $e_i$ 时贡献如何变化（是否仍为 ${\sum }_j{\sigma }_j^{-2}$？）。

参考文献

• Zoo 编号 150：Aleksandrs Belovs, Span-Program-Based Quantum Algorithm for the Rank Problem.
• Zoo 编号 149：Ben Reichardt, Span Programs and Quantum Query Complexity.
• Zoo 编号 151：Sebastian Dörn 与 Thomas Thierauf, The Quantum Query Complexity of the Determinant, IPL 2009。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch11-query-complexity/matrix-rank
• 内容遵循 CC BY-NC-SA 4.0 许可协议