第 11 章 查询复杂度 代码演示¶
本章研究 oracle 模型中量子算法的通用设计工具:对抗矩阵与 span program 给出最优 Boolean 查询算法,半定规划发现顺序搜索的最佳小规模模块,Johnson 图量子行走解决碰撞与子集性质。每课同时追踪 setup、update、check 与数据结构成本,避免把查询优势误写成无条件时间优势。
本章 3 个演示,每个演示独立成页:实现要点、完整源码与运行结果。
Demo 1:碰撞 BHT¶
双图 —— N=8 标记命中 + log-log 查询数对比
Demo 2:元素唯一性¶
双图 —— toy 数组 + O(N) vs O(N^{2/3}) + Johnson 平衡
Demo 3:矩阵秩¶
3 子图 —— 4×4 高斯消元 + 量子查询复杂度


