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

> 主站教程：[chenzhaoyun.com/quantum-tutorial/ch11-query-complexity/](https://chenzhaoyun.com/quantum-tutorial/ch11-query-complexity/)

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

**3 个 demo（点击查看）**：

### 1. 01 Collision Bht

![01_collision_bht.png](01_collision_bht.png)

**碰撞问题 BHT-Grover N=8 二对一哈希 + 经典 N^{1/2} vs 量子 N^{1/3} log-log 查询数对比**

```bash
python demos/ch11-query-complexity/01_collision_bht.py
```

### 2. 02 Element Distinctness

![02_element_distinctness.png](02_element_distinctness.png)

**玩具数组 [3,1,4,1,5,9,2,6] 元素唯一性 + Johnson 平衡 + O(N) vs O(N^{2/3}) 对比**

```bash
python demos/ch11-query-complexity/02_element_distinctness.py
```

### 3. 03 Matrix Rank

![03_matrix_rank.png](03_matrix_rank.png)

**4×4 二值矩阵 rank=3 高斯消元 + Belovs 量子查询复杂度 + 16 entry RX(π·A[i,j]) oracle 验证**

```bash
python demos/ch11-query-complexity/03_matrix_rank.py
```

---

[← 演示总索引](../index.md) · [→ 主页](../../tutorial/index.md)