Demo 2：元素唯一性

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

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

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

实现要点

核心：对玩具数组 arr = [3, 1, 4, 1, 5, 9, 2, 6] (idx=1,3 重复值 1) 演示 Ambainis 量子行走算法的 N^{2/3} 平衡点。画三幅图: (左) 数组可视化 + 标记重复对 (中) N=8..10^5 查询数对比: 经典 O(N) vs Grover sqrt(N) vs 量子 O(N^{2/3}) (右) Johnson 图参数平衡 (固定 N=1000): epsilon, delta, 总成本 vs r 并用 uniqc 跑 4 个 1-qubit oracle 验证 arr[idx] == 1 的检测能力。

完整源码

demos/ch11-query-complexity/02_element_distinctness.py

"""
ch11 演示 2：元素唯一性 Johnson 图量子行走平衡 + toy 实例量子探测

对应教程：chenzhaoyun.com/quantum-tutorial/ch11-query-complexity/collision-element-distinctness.html
核心：对玩具数组 arr = [3, 1, 4, 1, 5, 9, 2, 6] (idx=1,3 重复值 1)
     演示 Ambainis 量子行走算法的 N^{2/3} 平衡点。画三幅图:
       (左) 数组可视化 + 标记重复对
       (中) N=8..10^5 查询数对比: 经典 O(N) vs Grover sqrt(N) vs 量子 O(N^{2/3})
       (右) Johnson 图参数平衡 (固定 N=1000): epsilon, delta, 总成本 vs r
     并用 uniqc 跑 4 个 1-qubit oracle 验证 arr[idx] == 1 的检测能力。

依赖：pip install unified-quantum[visualization]
运行：python demos/ch11-query-complexity/02_element_distinctness.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 = 600  # 4 probes * 600 = 2400 total, < 3000 budget
ARR = np.array([3, 1, 4, 1, 5, 9, 2, 6], dtype=int)
N = len(ARR)


def find_duplicates_classical(arr: np.ndarray) -> tuple[list[tuple[int, int]], int]:
    queries, pairs = 0, []
    indexed = sorted(enumerate(arr), key=lambda x: x[1])
    for k in range(len(indexed) - 1):
        queries += 1
        if indexed[k][1] == indexed[k + 1][1]:
            pairs.append((indexed[k][0], indexed[k + 1][0]))
    return pairs, queries


def eps_ambainis(N: int, r: int) -> float:
    """唯一碰撞对的标记比例: epsilon = C(N-2,r-2)/C(N,r) = r(r-1)/(N(N-1))."""
    return r * (r - 1) / (N * (N - 1)) if r >= 2 else 0.0


def delta_johnson(N: int, r: int) -> float:
    return N / (r * (N - r)) if 0 < r < N else 0.0


def value_test_circuit(idx: int, value: int) -> Circuit:
    """1-qubit oracle: H |0>, RZ(theta_real - theta_test) |0>, H |0>, 测 P(0)."""
    c = Circuit()
    max_val = int(ARR.max())
    theta = 2 * np.pi * (float(ARR[idx]) - float(value)) / max_val
    c.h(0); c.rz(0, float(theta)); c.h(0)
    c.measure(0)
    return c


def measure_p0(circuit: Circuit) -> float:
    r = wait_for_result(submit_task(circuit=circuit, backend="dummy:local:simulator", shots=SHOTS))
    return float(r.probabilities.get("0", 0.0))


duplicates, classical_q = find_duplicates_classical(ARR)
N_list = [8, 27, 64, 216, 1000, 8000, 27000, 100000]
classical_curve = np.array([float(n) for n in N_list])
sqrt_curve = np.array([np.sqrt(n) for n in N_list])
quantum_curve = np.array([float(n) ** (2.0 / 3.0) * 2.0 for n in N_list])

N_FIXED = 1000
r_grid = np.arange(1, N_FIXED + 1, 5)
eps_curve = np.array([eps_ambainis(N_FIXED, int(r)) for r in r_grid])
del_curve = np.array([delta_johnson(N_FIXED, int(r)) for r in r_grid])
walk_steps = 1.0 / np.sqrt(np.maximum(eps_curve * del_curve, 1e-30))
total_cost = r_grid + walk_steps
opt_idx = int(np.argmin(total_cost))
opt_r = int(r_grid[opt_idx])

# === 量子 oracle 验证 ===
print("ch11-query-complexity demo 2: element distinctness (Johnson walk)")
print(f"  toy array (N = {N}):  {ARR.tolist()},  duplicate pairs = {duplicates},  shots = {SHOTS}")
p_correct_1 = measure_p0(value_test_circuit(1, 1))
p_correct_3 = measure_p0(value_test_circuit(3, 1))
p_wrong_0 = measure_p0(value_test_circuit(0, 1))
p_wrong_6 = measure_p0(value_test_circuit(6, 1))

fig, axes = plt.subplots(1, 3, figsize=(16.5, 5.2))

# (左) 数组 + 重复对
ax = axes[0]
dup_set = {d[0] for d in duplicates} | {d[1] for d in duplicates}
colors = ["#d62728" if i in dup_set else "#1f77b4" for i in range(N)]
bars = ax.bar(np.arange(N), ARR, color=colors, edgecolor="black", lw=0.8)
for i, b in enumerate(bars):
    ax.text(b.get_x() + b.get_width() / 2, b.get_height() + 0.15, f"{ARR[i]}",
            ha="center", va="bottom", fontsize=10, fontweight="bold")
for d in duplicates:
    ax.annotate("", xy=(d[0], ARR[d[0]] + 0.6), xytext=(d[1], ARR[d[1]] + 0.6),
                arrowprops=dict(arrowstyle="<->", color="#d62728", lw=2.0))
    ax.text(0.5 * (d[0] + d[1]), max(ARR[d[0]], ARR[d[1]]) + 1.1,
            f"DUPLICATE\nf({d[0]})=f({d[1]})={ARR[d[0]]}",
            ha="center", va="bottom", fontsize=9, color="#d62728", fontweight="bold")
ax.set_xticks(np.arange(N))
ax.set_xticklabels([f"idx {i}" for i in range(N)], fontsize=8)
ax.set_xlabel("array index")
ax.set_ylabel("stored value f(idx)")
ax.set_title(f"toy array with one duplicate pair\nclassical queries = N = {N} (sort + scan)")
ax.set_ylim(0, max(ARR) + 2.6)
ax.grid(axis="y", alpha=0.3)

# (中) 复杂度 log-log 对比
ax = axes[1]
ax.loglog(N_list, classical_curve, "o-", color="#d62728", lw=2, ms=8, label=r"classical $Q = O(N)$")
ax.loglog(N_list, sqrt_curve, "^-", color="#ff7f0e", lw=2, ms=7, label=r"Grover-style $O(\sqrt{N})$")
ax.loglog(N_list, quantum_curve, "s-", color="#1f77b4", lw=2, ms=8, label=r"Ambainis walk $O(N^{2/3})$")
for n, qc, qq in zip(N_list, classical_curve, quantum_curve):
    ax.annotate(f"{int(qc)}", (n, qc), textcoords="offset points", xytext=(4, 4),
                fontsize=7, color="#d62728")
    ax.annotate(f"{int(qq)}", (n, qq), textcoords="offset points", xytext=(4, -12),
                fontsize=7, color="#1f77b4")
ref_x = np.array([N_list[0], N_list[-1]], dtype=float)
ax.loglog(ref_x, ref_x, ":", color="#d62728", alpha=0.4)
ax.loglog(ref_x, ref_x ** (2.0 / 3.0) * 1.5, ":", color="#1f77b4", alpha=0.4)
ax.set_xlabel(r"domain size $N$")
ax.set_ylabel(r"# oracle queries")
ax.set_title("element distinctness: classical vs quantum\n"
             r"$\Theta(N)$ vs $\Theta(N^{2/3})$  (gain over Grover $\sqrt{N}$)")
ax.legend(loc="upper left", fontsize=9)
ax.grid(alpha=0.3, which="both")

# (右) Johnson trade-off
ax = axes[2]
ax.semilogy(r_grid, r_grid, "-", color="#2ca02c", lw=2, label=r"setup cost $S(r) = r$")
ax.semilogy(r_grid, walk_steps, "-", color="#9467bd", lw=2, label=r"walk cost $N / \sqrt{r}$")
ax.semilogy(r_grid, total_cost, "-", color="#1f77b4", lw=2.4, label=r"total $Q(r) = r + N/\sqrt{r}$")
ax.axvline(opt_r, color="#d62728", ls="--", lw=2,
           label=fr"optimal $r^* = N^{{2/3}} = {opt_r}$")
ax.plot(opt_r, total_cost[opt_idx], "*", color="#d62728", ms=18, mec="black",
        label=fr"min cost $\approx${total_cost[opt_idx]:.0f}")
ax.text(opt_r * 1.15, total_cost[opt_idx] * 1.4,
        fr"$\epsilon = {eps_curve[opt_idx]:.4f}$" + "\n"
        fr"$\delta = {del_curve[opt_idx]:.4f}$" + "\n"
        fr"$1/\sqrt{{\delta\epsilon}} = {walk_steps[opt_idx]:.0f}$",
        fontsize=8, color="#333")
ax.set_xlabel(r"subset size $r$")
ax.set_ylabel("query cost (log)")
ax.set_title(fr"Johnson $J(N={N_FIXED}, r)$ parameter balance"
             "\nmark prob + spectral gap determine walk steps")
ax.legend(loc="upper right", fontsize=8)
ax.set_xlim(0, N_FIXED // 2)
ax.grid(alpha=0.3, which="both")

fig.suptitle("ch11 demo 2: element distinctness — Ambainis Johnson graph quantum walk",
             y=1.01, fontsize=12)
plt.tight_layout()
out_path = OUT / "02_element_distinctness.png"
plt.savefig(out_path, dpi=120, bbox_inches="tight")
plt.close()

print(f"  optimal quantum r* for N=216: {int(round(216**(2/3)))},  "
      f"N=10^5: {int(round(100000**(2/3)))}")
print(f"  Johnson trade-off at N={N_FIXED}: r* = {opt_r},  "
      f"epsilon = {eps_curve[opt_idx]:.5f},  delta = {del_curve[opt_idx]:.5f},  "
      f"cost = {total_cost[opt_idx]:.0f}")
print(f"  oracle probes (uniqc) on duplicate pair:")
print(f"    P(0| f(1)==1) = {p_correct_1:.4f}  (should be ~1, value correct)")
print(f"    P(0| f(3)==1) = {p_correct_3:.4f}  (should be ~1, value correct)")
print(f"    P(0| f(0)==1) = {p_wrong_0:.4f}  (should be <1, arr[0]=3 != 1)")
print(f"    P(0| f(6)==1) = {p_wrong_6:.4f}  (should be <1, arr[6]=2 != 1)")
print(f"  complexity scaling:")
for n, qc, qq in zip(N_list, classical_curve, quantum_curve):
    print(f"    N = {n:>6d}   classical = {int(qc):>6d}   quantum = {int(qq):>5d}   speedup = {qc/qq:.1f}x")
print(f"  saved: {out_path}")

运行结果

运行方式

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

---

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