第 11 章 查询复杂度 代码演示

本章研究 oracle 模型中量子算法的通用设计工具:对抗矩阵与 span program 给出最优 Boolean 查询算法,半定规划发现顺序搜索的最佳小规模模块,Johnson 图量子行走解决碰撞与子集性质。每课同时追踪 setup、update、check 与数据结构成本,避免把查询优势误写成无条件时间优势。

本章 3 个演示,每个演示独立成页:实现要点、完整源码与运行结果。

Demo 1:碰撞 BHT

双图 —— N=8 标记命中 + log-log 查询数对比

Demo 1:碰撞 BHT

→ 实现要点与完整源码

Demo 2:元素唯一性

双图 —— toy 数组 + O(N) vs O(N^{2/3}) + Johnson 平衡

Demo 2:元素唯一性

→ 实现要点与完整源码

Demo 3:矩阵秩

3 子图 —— 4×4 高斯消元 + 量子查询复杂度

Demo 3:矩阵秩

→ 实现要点与完整源码