第11章 查询复杂度、Span Program 与性质测试¶
本章研究 oracle 模型中量子算法的通用设计工具：对抗矩阵与 span program 给出最优 Boolean 查询算法，半定规划发现顺序搜索的最佳小规模模块，Johnson 图量子行走解决碰撞与子集性质。每课同时追踪 setup、update、check 与数据结构成本，避免把查询优势误写成无条件时间优势。
- Boolean 公式求值：Span Program、对抗界与双反射算法
- 量子顺序搜索：半定规划模块与常数因子优势
- 碰撞与元素唯一性：从抽样加 Grover 到 Johnson 图量子行走
- 量子模式匹配：确定性采样、Grover 与平均情形 Hidden Shift
- 通配符搜索：Pretty-Good Measurement 每轮学习 \(\Theta(\sqrt n)\) 位
- 分布统计差异测试：量子计数、碰撞概率与 \(L_1\) 距离
- 量子假币问题：随机分盘、奇偶 oracle 与四次方加速
- 量子矩阵秩判定：Span Program、奇异值条件与稀疏加载
- 半环矩阵乘法：Grover 基线、阈值 Boolean 化与输出敏感算法
- 一般子集寻找：Johnson 图量子行走的 \(N^{k/(k+1)}\) 模板
- Junta 测试与 Gapped Group Testing：从变量影响到对抗界