Demo 1：碰撞 BHT

第 11 章 查询复杂度 · 本章演示 · 代码演示总索引

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

对应教程：第 11 章 查询复杂度 中相关小节 · 依赖安装：pip install "unified-quantum[visualization,simulation]"

实现要点

核心：在 N=8 的二对一承诺函数 f=[0,0,1,1,2,2,3,3] 上演示 Brassard-Hoyer-Tapp 抽样表 + Grover 算法的 r = N^(1/3) 平衡点。画三幅图: (左) hash 函数结构 + 抽样表 + "另一半"原像标记 (中) 经典生日攻击 sqrt(N) vs 量子 BHT N^(1/3) 查询数 log-log 对比 (右) N=8 实际跑 Grover: 命中 marked 状态的概率分布

完整源码

demos/ch11-query-complexity/01_collision_bht.py

"""
ch11 演示 1：碰撞问题查询复杂度对比 + BHT 量子算法小实例

对应教程：chenzhaoyun.com/quantum-tutorial/ch11-query-complexity/collision-element-distinctness.html
核心：在 N=8 的二对一承诺函数 f=[0,0,1,1,2,2,3,3] 上演示 Brassard-Hoyer-Tapp
     抽样表 + Grover 算法的 r = N^(1/3) 平衡点。画三幅图:
       (左) hash 函数结构 + 抽样表 + "另一半"原像标记
       (中) 经典生日攻击 sqrt(N) vs 量子 BHT N^(1/3) 查询数 log-log 对比
       (右) N=8 实际跑 Grover: 命中 marked 状态的概率分布

依赖：pip install unified-quantum[visualization]
运行：python demos/ch11-query-complexity/01_collision_bht.py
"""
from pathlib import Path

import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
import numpy as np

from uniqc import Circuit, submit_task, wait_for_result

OUT = Path(__file__).parent
SHOTS = 2000
N_DOMAIN = 8
HASH_TABLE = np.array([0, 0, 1, 1, 2, 2, 3, 3], dtype=int)


def mark_state(c: Circuit, ms: int, n_qubits: int = 3) -> None:
    """对 n-qubit 寄存器的 |ms> 加相位翻转 (ms 用 little-endian 二进制)."""
    bits = [(ms >> (n_qubits - 1 - b)) & 1 for b in range(n_qubits)]
    for q in range(n_qubits):
        if bits[q] == 0:
            c.x(q)
    c.h(n_qubits - 1)
    c.toffoli(0, 1, n_qubits - 1)
    c.h(n_qubits - 1)
    for q in range(n_qubits):
        if bits[q] == 0:
            c.x(q)


def diffusion(c: Circuit, n_qubits: int = 3) -> None:
    for q in range(n_qubits):
        c.h(q); c.x(q)
    c.h(n_qubits - 1)
    c.toffoli(0, 1, n_qubits - 1)
    c.h(n_qubits - 1)
    for q in range(n_qubits):
        c.x(q); c.h(q)


def find_partners(sample: list[int]) -> list[int]:
    """给定抽样 index, 返回表外 '另一半' 原像 (sorted, dedup)."""
    s_set = set(sample)
    marked = []
    for i in sample:
        partner = int(np.where(HASH_TABLE == HASH_TABLE[i])[0][
            np.where(HASH_TABLE == HASH_TABLE[i])[0] != i][0])
        if partner not in s_set:
            marked.append(partner)
    return sorted(set(marked))


def run_grover(marked: list[int], iters: int = 2) -> dict:
    c = Circuit()
    for q in range(3):
        c.h(q)
    for _ in range(iters):
        for ms in marked:
            mark_state(c, ms)
        diffusion(c)
    for q in range(3):
        c.measure(q)
    r = wait_for_result(submit_task(circuit=c, backend="dummy:local:simulator", shots=SHOTS))
    return dict(r.counts)


print("ch11-query-complexity demo 1: collision problem + BHT")
print(f"  domain N = {N_DOMAIN},  hash f = {HASH_TABLE.tolist()} (two-to-one),  shots = {SHOTS}")

# === 复杂度对比表 ===
N_LIST = [8, 27, 64, 216, 1000, 8000, 27000, 100000, 1000000]
classical_queries = [int(np.ceil(np.sqrt(2 * np.log(2) * n))) for n in N_LIST]
quantum_queries = [2 * int(round(n ** (1.0 / 3.0))) for n in N_LIST]
logN = np.log10(N_LIST)
logC, logQ = np.log10(classical_queries), np.log10(quantum_queries)

# === N=8 上跑实际 Grover ===
sample_indices = [0, 2]
sample_outputs = [int(HASH_TABLE[i]) for i in sample_indices]
marked_states = find_partners(sample_indices)
grover_counts = run_grover(marked_states, iters=2)
total = sum(grover_counts.values())
mark_total = sum(v for k, v in grover_counts.items() if int(k, 2) in marked_states)
n_labels = [f"{i:03b}" for i in range(N_DOMAIN)]
grover_probs = np.array([grover_counts.get(lbl, 0) / total * 100 for lbl in n_labels])

# === 画图 ===
fig, axes = plt.subplots(1, 3, figsize=(16.0, 5.0))
partner_map = {i: [j for j in range(N_DOMAIN) if j != i and HASH_TABLE[j] == HASH_TABLE[i]][0]
               for i in range(N_DOMAIN)}

# (左) hash 结构
ax = axes[0]
colors = ["#1f77b4" if i not in sample_indices else "#ffd700" for i in range(N_DOMAIN)]
bars = ax.bar(np.arange(N_DOMAIN), HASH_TABLE, color=colors, edgecolor="black")
for i, b in enumerate(bars):
    star = "*" if i in sample_indices else ""
    ax.text(b.get_x() + b.get_width() / 2, b.get_height() + 0.06,
            f"f({i})={HASH_TABLE[i]}\npart={partner_map[i]}{star}",
            ha="center", va="bottom", fontsize=7)
ax.set_xticks(np.arange(N_DOMAIN))
ax.set_xticklabels([f"in {i}" for i in range(N_DOMAIN)], fontsize=8)
ax.set_xlabel("input index")
ax.set_ylabel("hash value")
ax.set_title(f"two-to-one hash f  (gold = sampled)\n"
             f"sample = {sample_indices}  outputs = {sample_outputs}")
ax.set_ylim(0, HASH_TABLE.max() + 0.6)
ax.grid(axis="y", alpha=0.3)

# (中) 经典 vs 量子 log-log
ax = axes[1]
ax.plot(logN, logC, "o-", color="#d62728", lw=2, ms=7, label=r"classical birthday $O(\sqrt{N})$")
ax.plot(logN, logQ, "s-", color="#1f77b4", lw=2, ms=7, label=r"quantum BHT $O(N^{1/3})$")
ref = np.array([logN[0], logN[-1]])
ax.plot(ref, 0.5 * ref + logC[0] - 0.5 * logN[0], "--", color="#d62728", alpha=0.4, label="slope 1/2")
ax.plot(ref, (1.0 / 3.0) * ref + logQ[0] - (1.0 / 3.0) * logN[0], "--", color="#1f77b4", alpha=0.4, label="slope 1/3")
for x, yc, yq in zip(logN, logC, logQ):
    ax.annotate(f"{10**yc:.0f}", (x, yc), textcoords="offset points", xytext=(0, 6),
                ha="center", fontsize=6.5, color="#d62728")
    ax.annotate(f"{10**yq:.0f}", (x, yq), textcoords="offset points", xytext=(0, -12),
                ha="center", fontsize=6.5, color="#1f77b4")
ax.set_xlabel(r"$\log_{10} N$")
ax.set_ylabel(r"$\log_{10}$ # queries")
ax.set_title("query complexity: classical vs quantum\n"
             r"$Q_{\mathrm{cl}} = O(\sqrt{N})$  vs  $Q_{\mathrm{qu}} = O(N^{1/3})$")
ax.legend(loc="upper left", fontsize=8)
ax.grid(alpha=0.3)

# (右) Grover 分布
ax = axes[2]
colors = ["#2ca02c" if i in marked_states else "#9467bd" for i in range(N_DOMAIN)]
bars = ax.bar(np.arange(N_DOMAIN), grover_probs, color=colors, edgecolor="black")
for i, b in enumerate(bars):
    if grover_probs[i] > 0.5:
        ax.text(b.get_x() + b.get_width() / 2, b.get_height() + 1.0,
                f"{grover_probs[i]:.1f}%", ha="center", va="bottom", fontsize=8, fontweight="bold")
ax.set_xticks(np.arange(N_DOMAIN))
ax.set_xticklabels(n_labels, fontsize=9)
ax.axhline(100.0 / N_DOMAIN, color="gray", ls=":", lw=1.5, label=f"uniform {100/N_DOMAIN:.1f}%")
ax.set_xlabel("Grover measurement |xyz>")
ax.set_ylabel("probability (%)")
ax.set_title(f"BHT Grover (sampled r={len(sample_indices)}, "
             f"marked = {marked_states})\n"
             fr"$P(\mathrm{{mark}}) = {mark_total/total*100:.1f}$%")
ax.legend(loc="upper right", fontsize=8)
ax.set_ylim(0, max(50, grover_probs.max() + 8))
ax.grid(axis="y", alpha=0.3)

fig.suptitle("ch11 demo 1: collision problem — BHT sampling + Grover beats classical birthday",
             y=1.01, fontsize=12)
plt.tight_layout()
out_path = OUT / "01_collision_bht.png"
plt.savefig(out_path, dpi=120, bbox_inches="tight")
plt.close()

print(f"  sample table: {sample_indices} -> f-values {sample_outputs}")
print(f"  marked 'other halves' (Grover targets): {marked_states}")
print(f"  Grover P(marked) measured = {mark_total/total:.3f} "
      f"(uniform = {1.0/N_DOMAIN:.3f}, "
      f"speedup = {(mark_total/total)/(1.0/N_DOMAIN):.2f}x)")
print(f"  complexity scaling:")
for n, c, q in zip(N_LIST, classical_queries, quantum_queries):
    print(f"    N = {n:>7d}  Q_classical = {c:>5d}  Q_quantum = {q:>4d}  speedup = {c/max(q,1):>4.1f}x")
print(f"  saved: {out_path}")

运行结果

运行方式

# 仓库根目录执行；输出 PNG 到 demos/ch11-query-complexity/01_collision_bht.png，关键统计到 stdout
.venv/bin/python3 demos/ch11-query-complexity/01_collision_bht.py

---

← 本章演示 · ↑ 代码演示总索引 · ⌂ 教程门户