量子矩阵秩判定：Span Program、奇异值条件与稀疏加载¶
给定 entry oracle 访问的 \(n\times m\) 矩阵 \(A\)，要判断它的秩是否至少为 \(r\)。最朴素的办法是读出全部 \(nm\) 个 entry 再做高斯消去，代价是 \(nm\) 次查询；本教程要讲清的是：在矩阵稀疏、且非零奇异值不太小的条件下，量子 span program 算法能把查询次数降下来。但加速并非只由维数决定——伪逆的范数控制 witness 的大小，输入向量的加载方式控制每次反射的成本。换句话说，同样的 \(n,m,r\)，算法快慢可以差出许多个数量级，差距来自矩阵的数值条件与访问方式。
秩是线性代数里最基本的不变量之一：方程组解是否唯一、矩阵是否可逆、子空间的维数计数，第一步几乎都是问秩。在黑盒（查询）模型里研究秩判定，因此成为"黑盒线性代数"的代表问题。它也是一面很好的镜子，能照出量子查询算法的一条通用经验：承诺（promise）与输入结构决定了加速是否存在，而不是问题名字里有没有"矩阵"二字。
本教程的主线是 Belovs 的 span program 算法（见文末参考文献，Zoo 编号 150）。我们把整个推导拆成四层，层层递进：
把"秩至少 \(r\)"这个代数条件翻译成"存在 \(r\) 个线性独立方向"，再翻译成外代数中"存在非零的 \(r\) 重楔积"——这是 span program 能吃的语言（第 3 节）；
用伪逆（Moore–Penrose pseudoinverse）写出正 witness，并实际算出它的成本是前 \(r\) 个非零奇异值倒数的均方根 \(L\)（第 3 节）；
把 Reichardt 的双反射算法套在这个 span program 上，得到查询复杂度 \(O(\sqrt{r(n-r+1)}\,L\,T)\)，并逐因子解释每一项的来源（第 4 节）；
与 determinant 的 \(\Omega(n^2)\) 量子下界对照，弄清上界在哪些参数区域真正有用、为什么与下界不矛盾（第 5 节）。
沿途我们会给出完整的推导：经典基线为什么是 \(\Theta(nm)\)（含一个可手算的对手论证）、为什么浮点模型必须带奇异值 gap 承诺、组合因子 \(\sqrt{r(n-r+1)}\) 在 \(r\) 取何值时最坏（一次求导就能算出）、以及两个可以手算到底的小例子。
前置知识：本站第 3 章的 Grover 算法（反射、振幅放大、\(\sqrt N\) 加速）与相位估计；同章的 Boolean 公式求值：Span Program、对抗界与双反射算法（span program 的定义、正负 witness、witness size 与双反射算法，本教程第 3.3 节只做复习，不重新推导）；第 6 章 HHL 算法中关于条件数的讨论（对照 \(L\) 的角色）。线性代数方面只需要 SVD 的基本性质，我们会在用到处证明。
本课知识点
黑盒模型与秩判定问题——能写出 entry oracle 的作用式并陈述秩判定问题，区分查询复杂度与时间复杂度的记账。
秩的奇异值刻画——能证明秩恰为非零奇异值的个数，并把 \(\operatorname{rank}(A)\ge r\) 改写为谱条件 \(\sigma_r>0\)。
奇异值 gap 承诺的必要性——能用 \(1\times1\) 定点实例证明浮点模型下无承诺则秩判定不可解，并写出 yes/no 实例的承诺形式。
条件数型因子 L——能由奇异值计算 \(L\)、证明夹逼 \(\frac{1}{\sigma_1}\le L\le\frac{1}{\sigma_r}\)，并说明 \(L\) 与经典条件数 \(\kappa\) 的关系。
经典查询下界——能构造只差一个 entry 的矩阵对证明确定性算法最坏需 \(nm\) 次查询，并说明 \(r=1\) 的判定就是 \(\mathrm{OR}_{nm}\)。
外代数刻画与 witness 估计——能手算 \(2\times2\) 楔积、证明"楔积为零当且仅当线性相关"，并推导正 witness 成本 \(rL^2\) 与负 witness 因子 \(n-r+1\) 的来源。
复杂度公式逐因子解读——能解释 \(Q=O\big(\sqrt{r(n-r+1)}\,L\,T\big)\) 中每个因子的出处，比较 dense 与 sparse oracle 的 \(T\)，并求出组合因子最坏的阈值 \(r^\ast=\frac{n+1}{2}\)。
下界对照与任务边界——能解释 determinant 的 \(\Omega(n^2)\) 下界为何与上界不矛盾、列出上界有用的三个区域，并比较"判定秩、输出列 witness、输出 SVD"三档任务的输出规模。
1. 问题、模型与数值稳定性¶
1.1 黑盒模型中的秩判定¶
算法不能直接"看见"矩阵 \(A\in\mathbb F^{n\times m}\)（\(\mathbb F\) 是实数域、有理数域或某个有限域，视模型而定），而只能通过查询 oracle 逐个访问 entry。以最常用的形式写下这个 oracle：
其中 \(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 节定义）。
1.2 秩与奇异值：判定条件的等价改写¶
在实数域上，奇异值分解（SVD）把 \(A\) 写成
其中 \(\{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：
其中第二个等号用了 \(\{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\)：
即每个这样的 \(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\) 是不是恰好为零。
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\) 的版本。结论是：浮点模型下的秩判定必须携带承诺。本教程采用原文的承诺形式：
读作：要么第 \(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\) 是条件数型因子：矩阵越接近降秩（某个 \(\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\)，则
左边的等号成立当且仅当 \(\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_j\) 相等。最后，把平均值与其中最大的一项比较：
开方得 \(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})\)，而且这是最优的。
2.1 一个 entry 就能翻转答案¶
Lemma 4. 任何用少于 \(nm\) 次查询的确定性算法，都存在一对只在一个 entry 上不同的输入矩阵，使得这对矩阵的秩判定答案不同。因此确定性算法最坏情形必须查询全部 \(nm\) 个 entry。
证明. 先构造一对"关键差异"矩阵。设 \(2\le r\le\min(n,m)\)，定义 \(n\times m\) 矩阵
\(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\) 的判定条件可以完全消去线性代数：
即 \(nm\) 个"entry 非零"事件的 OR。这正是 Grover 算法一节里反复研究的无结构搜索问题 \(\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\) 与算法的随机性独立且均匀分布，所以
（每一次查询至多"试探"一个位置；\(t\) 次查询覆盖均匀随机点的概率至多是 \(t/nm\)。）关键在于条件"未查询到 \(P\)"时会发生什么：算法在 \(A^{(P)}\) 上得到的应答全部为 \(0\)，与它在 \(A^{(\varnothing)}\) 上的应答逐步相同，因此两种情形下算法的后续行为（包括最终输出分布）没有差别。于是
其中 \(q\) 是算法面对"全零视图"时输出"是"的概率。\(A^{(\varnothing)}\) 是答案为"否"的实例，误差 \(\le\frac13\) 要求 \(q\le\frac13\)；\(A^{(P)}\) 是答案为"是"的实例，要求上式 \(\ge\frac23\)。联立：
量子一侧，\(\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)}\,L\,T)\) 型的查询上界——第 3、4 节的全部内容就是拆解这个公式。
没有承诺就没有加速。Dörn 与 Thierauf（Zoo 编号 151）证明无承诺的一般 determinant 判定有 \(\Omega(n^2)\) 级量子查询下界，与读满所有 entry 同阶。它划出了本文上界的适用边界，第 5 节专门讨论它与上界为何不矛盾。
3. 从"存在独立方向"到 Span Program¶
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)\)，它有天然基
先手算一个最小的例子，把抽象定义落到实处。设 \(n=r=2\)，\(a_1=\alpha e_1+\beta e_2\)，\(a_2=\gamma e_1+\delta 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_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}\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 搜索。这条路可行但浪费严重，原因有三层：
单个候选不便宜。判断一个固定子集 \(\{j_1,\ldots,j_r\}\) 的 minor 是否非零，需要先读出这个 \(r\times r\) 子矩阵的全部 \(r^2\) 个 entry，再做行列式计算——每个候选本身就是 \(r^2\) 次查询的子程序，而不是一次 oracle 调用。
重叠严重。两个只差一列的子集共享 \(r-1\) 列，读过的 entry 与中间计算无法在"把每个 minor 当独立黑盒 predicate"的搜索里复用；\(\binom mr\) 个候选覆盖的 entry 总量远小于 \(\binom mr\cdot r^2\)，独立估值等于把同样的数据读了许多遍。
predicate 不是黑盒。Grover 需要"判定候选是否标记"的反射；对 minor 而言这个反射本身要靠数据构造，等于把难度转移而不是消去。
Span program 的价值正在于绕开逐个枚举：它把"存在 \(r\) 个独立方向"作为一个整体的线性代数条件编码进一个反射算子里，让振幅在"独立方向数目"这个自由度上相干地流动，而不是在 \(\binom mr\) 个候选上盲目试错。
3.3 Span program 与双反射算法：快速复习¶
本小节把同章 Boolean 公式求值中详细推导过的框架压缩成一段回顾，只保留本教程要用的结论。
一个 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\) 的结构、一个依赖输入的可用性——构造酉算子，配合相位估计，就能以
次"实现输入相关反射"的查询正确判定。同章教程用 \(\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 双反射算法完成判定。成本的记账也相应分两层：
这就是最终复杂度公式呈现乘法结构的原因：组合结构与数值条件进入 \(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：
Moore–Penrose 伪逆经 SVD 定义为
性质一（两个投影恒等式）. \(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}\)）：
最后一个表达式恰是到 \(\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\) 的个数，所以
两者在正交归一系 \(\{v_1,\ldots,v_{\min(n,m)}\}\) 下显然互相正交。于是任意解可写为 \(x=x^\ast+z\)，\(z\in\ker A\) 且 \(z\perp x^\ast\)，由勾股定理
等号当且仅当 \(z=0\)。Q.E.D.
最小范数性质说明：在把目标写成"列向量作用的组合"的所有方式中，伪逆给出的系数是欧氏范数最小的——正 witness 要的就是它（witness 成本是系数平方和，span program 的正 witness 定义允许任取系数，最优取法即伪逆）。
Proposition 7. 把目标方向取为列空间的正交基 \(u_1,\ldots,u_r\)，则伪逆系数的平方和为
证明. 对每个 \(j\)，用 \(\{u_l\}\) 的正交归一性直接计算 \(A^+u_j\)：
故 \(\|A^+u_j\|^2=\sigma_j^{-2}\,\|v_j\|^2=\sigma_j^{-2}\)（\(v_j\) 是单位向量）。对 \(j=1,\ldots,r\) 求和，再用 \(L\) 的定义移项：
这就把第 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\)，于是正交补
的维数至少 \(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 节的几何平均合并：
（这里"\(\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 所收录的上界可写为
按第 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\) 与第 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\) 个非零元：
行、列两方向的稀疏性约束共同保证反射的两侧（列选择与列内容）成本都由 \(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\) 最贵"是一次标准的参数平衡。把
当作 \(r\) 的（形式上连续的）函数求导：
令 \(f'(r)=0\) 解出
其中第二个等号用了 \(n-\frac{n+1}{2}+1=\frac{n+1}{2}\)。\(f\) 是开口向下的二次函数，故 \(r^\ast\) 是最大值点；实际取最接近 \(\frac{n+1}{2}\) 的整数即可。再看两端：
整理成一张量级表：
中间比两端贵约 \(\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\)），判断
等价于判断秩是否小于 \(n\)。这一等价可以直接从第 3.1 节的外代数刻画读出，不必另起炉灶：取 \(r=n\)，\(\Lambda^n(\mathbb F^n)\) 是一维空间，基向量是 \(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\) 一档。
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 下界的实例恰好把两个阀门同时拧到最坏：
矩阵 dense 且只有 entry oracle：\(T=O(\sqrt{nm})=O(n)\)，加载无便宜可占；
病态、恰好接近奇异：\(\gamma\to0\) 使 \(L=O(1/\gamma)\to\infty\)，任何以 \(\gamma\) 为界的估计都失效；
下界允许的是最坏实例，而上界的有用区域需要同时避开这些最坏情形。
逐区域检查后，span-program 上界真正有用的区域是：
矩阵稀疏且 sparse oracle 可用：\(T\) 从 \(O(\sqrt{nm})\) 降到 \(O(k\log(n+m))\)；
目标秩 \(r\) 远离使组合因子最坏的位置：\(r\) 接近 \(1\) 或 \(n\) 时 \(\sqrt{r(n-r+1)}\) 只有 \(\sqrt n\) 量级，而非 \(\approx n/2\)（第 4.4 节）；
非零奇异值有下界，使 \(L\) 不大：承诺 \(\sigma_r\ge\gamma\) 且 \(\gamma\) 不是灾难性地小，\(L\le1/\gamma\) 有界（Lemma 3）。
三个区域分别压制公式中的一个因子；下界实例则可以同时是 dense、病态、恰好接近奇异的，因此被排除在所有区域之外。"加速来自条件与结构承诺"这句总结，在这三个区域的对号入座里得到了完全具体的含义。
6. 数值小例子¶
6.1 对角矩阵 \(\operatorname{diag}(1,1,\epsilon,0)\)¶
令
（取 \(\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\) 特征值的平方根的递减排列：
秩。非零奇异值有 \(3\) 个（\(\epsilon\ne0\)），由 Lemma 1，\(\operatorname{rank}(A)=3\)。
测试 \(r=3\)（yes 实例，承诺 \(\sigma_3=\epsilon\ge\gamma\)，\(\sigma_4=0\) 自动成立）。按定义展开：
当 \(\epsilon\to0\) 时 \(\epsilon^{-2}\) 项主导分子，故渐近地
顺手用 Lemma 3 验证夹逼：应有 \(L\le1/\sigma_3=1/\epsilon\)。验证：
对 \(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\)：
同一个矩阵、同一个 oracle，阈值从 \(3\) 改到 \(2\)，条件因子从 \(\sim1/(\sqrt3\,\epsilon)\) 掉到 \(1\)：秩阈值承诺会实质改变复杂度。直观地，判"秩 \(\ge2\)"只需要前两个方向的信息，\(\epsilon\) 所在的第三个方向根本不进入 witness；这也再次印证第 3.5 节的公式——\(L\) 只对前 \(r\) 个奇异值求和。
6.2 \(2\times2\) 矩阵的完整 witness 计算¶
把第 3.5、3.6 节的两类 witness 在一个能算到底的例子上走一遍。取
选对角矩阵是因为它的奇异向量恰是标准基，便于手算；一般矩阵需先做 SVD。
楔积与 minor（第 3.1 节的链条）。列向量 \(a_1=e_1\)，\(a_2=\epsilon 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 定义（对可逆方阵就是逆）：
对两个目标方向分别计算伪逆系数：
平方和
与 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\)；正交补
（\(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\) 依次判定，第一次回答"否"即停）的总查询为
上界由最难的那个阈值（通常是 \(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 节）
写出 entry oracle \(O_A\) 对基态 \(|i,j,b\rangle\) 的作用式，并说明"一次查询"与"实现 oracle 及算术的门开销"在记账上的区别。
设某算法用 \(O(\sqrt{nm})\) 次查询判定 \(r=1\)，而每次查询需 \(O(\log(nm))\) 个门实现索引与算术。分别写出它的查询复杂度与时间复杂度，并说明两者为何可能相差多项式因子。
练习 2【秩的奇异值刻画】（→ 1.2 节）
求 \(A=\operatorname{diag}(3,4,0)\) 的奇异值与秩，并验证"秩恰为非零奇异值的个数"。
复述 Lemma 1 证明中"列空间 \(\subseteq\operatorname{span}\{u_j:\sigma_j>0\}\)"与反向包含两步各用到 SVD 的哪条性质，再把结论改写为 \(\operatorname{rank}(A)\ge r\iff\sigma_r>0\)。
练习 3【奇异值 gap 承诺的必要性】（→ 1.3 节）
写出本教程采用的 yes/no 实例承诺形式，并说明 yes 实例的秩恰为 \(r\)、no 实例的秩至多 \(r-1\)。
设 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 节）
设 \(\sigma_1=2\)、\(\sigma_2=1\)，按定义计算 \(L\)，并验证 Lemma 3 的夹逼 \(\frac{1}{\sigma_1}\le L\le\frac{1}{\sigma_r}\)。
对 \(\operatorname{diag}(1,\epsilon,0)\)（\(\epsilon>0\)）分别计算 \(r=1,2\) 的 \(L\)，并解释为什么 \(r=1\) 的答案与 \(\epsilon\) 无关。
证明 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 节）
对 \(A_{11}=x\)、\(A_{jj}=1\)（\(j=2,\ldots,r\)）、其余 entry 为 \(0\) 的矩阵 \(A(x)\)，分别求 \(x=0\) 与 \(x=1\) 时的秩，并指出两个矩阵在几个 entry 上不同。
把"\(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 节）
设 \(a_1=\alpha e_1+\beta e_2\)、\(a_2=\gamma e_1+\delta e_2\)，按多线性与反对称性展开 \(a_1\wedge a_2\)，并指出结果与 \(2\times2\) 行列式的关系。
证明 \(\operatorname{rank}\ge r\) 等价于某个 \(r\) 重楔积非零。
完整证明 Moore–Penrose 伪逆的最小范数性质（第 3.5 节性质二），并据此说明：当目标方向取左奇异向量 \(u_j\) 时，正 witness 的贡献恰为 \(\sigma_j^{-2}\)；再讨论把目标换成标准基 \(e_i\) 时贡献如何变化（是否仍为 \(\sum_j\sigma_j^{-2}\)？）。
提示：第 2 题把 Lemma 6 的两个方向分别用于"存在性"与"全称性"。
练习 7【复杂度公式逐因子解读】（→ 4.1 节）
写出总查询复杂度 \(Q=O\big(\sqrt{r(n-r+1)}\,L\,T\big)\)，并说明三个因子分别来自 witness size 的哪一侧、哪一层记账。
证明 \(f(r)=r(n-r+1)\) 在 \(r=\frac{n+1}{2}\) 处取最大值，并计算 \(r=1\)、\(r=\frac{n+1}{2}\)、\(r=n\) 三处 \(\sqrt{f(r)}\) 的值与最大最小之比。
比较 entry oracle 与 sparse-list oracle 能提供的信息：给出一个矩阵族，使得两种 oracle 下的 \(T\) 相差多项式倍；再说明用 entry oracle 模拟一次 sparse-list 查询（定位一列的非零元）需要多少量级的查询。
提示：第 3 题注意"定位一列的 \(k\) 个非零元"是一次多目标搜索，量级 \(\sqrt{n/k}\)。
练习 8【下界对照与任务边界】（→ 5.2 节）
说明对方阵判定 \(\det A=0\) 等价于 \(r=n\) 的秩判定，并从第 4.4 节的量级表读出它的组合因子。
列出 determinant 下界实例把上界公式中的哪两个因子拧到最坏，并解释上界真正有用的三个区域分别压制公式中的哪个因子。
解释为何求精确秩的整数输出不需要输出全部奇异向量；据此论证"输出 SVD 需要 \(\Omega(nm)\) 时间"。
提示：SVD 要写出 \(U,\Sigma,V\) 三个矩阵，输出本身就有 \(\Theta(nm)\) 个 entry。
参考文献¶
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。