Demo 3：Childs-Goldstone 空间搜索

第 12 章 量子图算法 · 本章演示 · 代码演示总索引

可视化：3 子图 —— C4 + γ=1/√2 + Rabi 振荡

对应教程：第 12 章 量子图算法 中相关小节 · 依赖安装：pip install "unified-quantum[visualization,simulation]"

实现要点

核心：4-环 C4 上做 Childs-Goldstone 连续时间空间搜索。Hamiltonian H = -γ A - |w⟩⟨w| 取 γ ≈ 1/√N = 1/2 (对 C_N 的渐近最优 γ 是 1/(2 sin(π/N))，对 N=4 ≈ 0.707)， 初态 |s⟩ = (1/2) Σ_i |i⟩ 是 A 的本征态（本征值 2）。H 把 |s⟩ 局限在 span{|s⟩, |w⟩} 的 2 维子空间里做 Rabi 振荡；振幅在 t ≈ π√N/2 时刻翻转到 |w⟩，P(target) 接近 1。相比之下，经典随机游走 P_t = T^t|s⟩ 需要 O(N)=4 步 才能把概率抬到 1/4 量级。这里画 P(target) vs t 的连续时间量子振荡曲线， 并叠加经典随机游走的概率作为参考；同时画 4 个节点振幅 |⟨i|ψ(t)⟩|² 的时间演化。

完整源码

demos/ch12-quantum-graphs/03_spatial_search.py

"""
ch12-quantum-graphs demo 3: Childs–Goldstone spatial search on the 4-cycle

对应教程：chenzhaoyun.com/quantum-tutorial/ch12-quantum-graphs/adjacency-matrix-properties.html
核心：4-环 C4 上做 Childs-Goldstone 连续时间空间搜索。Hamiltonian
       H = -γ A - |w⟩⟨w|
     取 γ ≈ 1/√N = 1/2 (对 C_N 的渐近最优 γ 是 1/(2 sin(π/N))，对 N=4 ≈ 0.707)，
     初态 |s⟩ = (1/2) Σ_i |i⟩ 是 A 的本征态（本征值 2）。H 把 |s⟩ 局限在
     span{|s⟩, |w⟩} 的 2 维子空间里做 Rabi 振荡；振幅在 t ≈ π√N/2 时刻翻转到
     |w⟩，P(target) 接近 1。相比之下，经典随机游走 P_t = T^t|s⟩ 需要 O(N)=4 步
     才能把概率抬到 1/4 量级。这里画 P(target) vs t 的连续时间量子振荡曲线，
     并叠加经典随机游走的概率作为参考；同时画 4 个节点振幅 |⟨i|ψ(t)⟩|² 的时间演化。

依赖：pip install unified-quantum[visualization]
运行：python demos/ch12-quantum-graphs/03_spatial_search.py
"""
from __future__ import annotations

from pathlib import Path

import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
import numpy as np
from scipy.linalg import expm

OUT = Path(__file__).parent
N = 4
TARGET = 0

# === 1. C4 adjacency matrix A ===
A = np.zeros((N, N))
for i in range(N):
    A[i, (i + 1) % N] = A[i, (i - 1) % N] = 1

# Eigenvalues of A for sanity check
evals_A = np.linalg.eigvalsh(A)
print("ch12-quantum-graphs-demo-3: Childs–Goldstone search on C4")
print(f"  C4 adjacency eigenvalues: {np.round(evals_A, 4).tolist()}  "
      "(expected: -2, 0, 0, 2)")

# === 2. Continuous-time spatial search Hamiltonian H = -γ A - |w⟩⟨w| ===
# Optimal γ for C_N: γ* = 1 / (2 sin(π/N)); for N=4 → γ* = 1/√2 ≈ 0.7071
GAMMA = 1.0 / np.sqrt(2.0)
T_QUANT_MAX = 10.0
N_QUANT_STEPS = 400
t_quant = np.linspace(0, T_QUANT_MAX, N_QUANT_STEPS)

W = np.zeros((N, N))
W[TARGET, TARGET] = 1.0
H = -GAMMA * A - W   # Childs–Goldstone Hamiltonian
# Initial state |s> = (1/√N) Σ |i>
s = np.ones(N) / np.sqrt(N)

target_probs_q = np.zeros(N_QUANT_STEPS)
all_node_probs_q = np.zeros((N_QUANT_STEPS, N))
for k, t in enumerate(t_quant):
    psi_t = expm(-1j * H * t) @ s
    probs = np.abs(psi_t) ** 2
    target_probs_q[k] = probs[TARGET]
    all_node_probs_q[k] = probs

# === 3. Classical random walk on C4 starting from uniform distribution ===
T_class = A / 2.0   # transition matrix (degree = 2 for every node)
p_class = np.ones(N) / N   # uniform start = (1/N, ..., 1/N); stationary for C4
T_CLASS_MAX = 30
target_probs_c = np.zeros(T_CLASS_MAX)
all_node_probs_c = np.zeros((T_CLASS_MAX, N))
for t in range(T_CLASS_MAX):
    target_probs_c[t] = p_class[TARGET]
    all_node_probs_c[t] = p_class
    p_class = T_class @ p_class

# === 4. Run a tiny uniqc sanity check on the uniform superposition |s> ===
try:
    from uniqc import Circuit, submit_task, wait_for_result
    c = Circuit()
    c.h(0); c.h(1)       # |s> = (|00>+|01>+|10>+|11>)/2 on q0, q1
    c.measure(0); c.measure(1)
    r = wait_for_result(
        submit_task(circuit=c, backend="dummy:local:simulator", shots=2000)
    )
    counts = r.counts
    total = sum(counts.values())
    expected = ["00", "01", "10", "11"]
    diffs = [abs(counts.get(bs, 0) / total - 0.25) for bs in expected]
    print(f"  uniqc sanity: |s> uniform prep, max deviation from 0.25 = "
          f"{max(diffs):.3f}")
except Exception as e:
    print(f"  uniqc sanity skipped: {e}")


# === 5. matplotlib 可视化 ===
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(13.0, 5.2))

# Left: P(target=node 0) vs time, continuous-time quantum vs classical random walk
ax1.plot(t_quant, target_probs_q, "-", color="#1f77b4", lw=2.0,
         label=fr"continuous-time search ($\gamma={GAMMA:.3f}$, $\hbar=1$)")
ax1.plot(np.arange(T_CLASS_MAX), target_probs_c, "o--", color="#ff7f0e",
         lw=1.6, ms=6, label=f"classical random walk ({T_CLASS_MAX} steps)")
# Mark the theoretically predicted search time T* = π√N/2
T_star = np.pi * np.sqrt(N) / 2.0
ax1.axvline(T_star, color="gray", ls=":", lw=1.0, alpha=0.7,
            label=fr"theory $T^*=\pi\sqrt{{N}}/2\approx{T_star:.2f}$")
ax1.axhline(1.0, color="#2ca02c", ls=":", lw=1.0, alpha=0.7,
            label=r"ideal $P=1$")
ax1.axhline(1.0 / N, color="#888888", ls=":", lw=1.0, alpha=0.7,
            label=fr"classical uniform $1/N={1.0/N:.3f}$")
ax1.set_xlabel(r"time $t$")
ax1.set_ylabel(r"$P(\mathrm{target} = \mathrm{node}\ 0)$")
ax1.set_ylim(-0.02, 1.08)
ax1.set_title("Childs–Goldstone search on C4: target probability vs time")
ax1.grid(alpha=0.3)
ax1.legend(loc="upper right", fontsize=8, framealpha=0.9)

# Right: heatmap of |⟨i|ψ(t)⟩|² for all 4 nodes over time
im = ax2.imshow(all_node_probs_q.T, aspect="auto", origin="lower",
                cmap="viridis", vmin=0.0, vmax=0.6,
                extent=[t_quant[0], t_quant[-1], -0.5, N - 0.5])
ax2.set_yticks(range(N))
ax2.set_yticklabels([f"node {n}" + (" (target)" if n == TARGET else "")
                      for n in range(N)])
ax2.set_xlabel(r"time $t$")
ax2.set_title(r"wave-packet $|\langle i|e^{-iHt}|s\rangle|^2$")
ax2.axvline(T_star, color="#ff6f61", ls="--", lw=1.4,
            label=fr"$T^*={T_star:.2f}$")
ax2.legend(loc="upper right", fontsize=8, framealpha=0.9)
cbar = plt.colorbar(im, ax=ax2)
cbar.set_label(r"probability at node $i$")

# C4 graph inset (square with target highlighted)
inset = fig.add_axes([0.04, 0.55, 0.16, 0.32])
inset.set_xlim(-1.3, 1.3)
inset.set_ylim(-1.3, 1.3)
inset.set_aspect("equal")
inset.axis("off")
theta = (np.arange(N) * 2 * np.pi / N + np.pi / 2)
xs, ys = np.cos(theta), np.sin(theta)
for i in range(N):
    j = (i + 1) % N
    inset.plot([xs[i], xs[j]], [ys[i], ys[j]], "k-", lw=1.6)
for n in range(N):
    fc = "#d62728" if n == TARGET else "#cccccc"
    ec = "black"
    inset.scatter(xs[n], ys[n], s=420, c=fc, ec=ec, lw=1.2, zorder=3)
    inset.text(xs[n], ys[n], str(n), ha="center", va="center",
               fontsize=11, fontweight="bold",
               color="white" if n != TARGET else "white", zorder=4)
inset.set_title("C4 with target node 0", fontsize=9)

plt.suptitle("ch12-quantum-graphs demo 3: Childs–Goldstone spatial search on C4",
             y=1.02)
plt.tight_layout()
out_path = OUT / "03_spatial_search.png"
plt.savefig(out_path, dpi=120, bbox_inches="tight")
plt.close()

# === 6. stdout 关键统计 ===
peak_idx = int(np.argmax(target_probs_q))
peak_t = float(t_quant[peak_idx])
print(f"\n  search parameters: N={N}, target=node {TARGET}, γ={GAMMA:.4f}")
print(f"  theory search time T* = π·√N/2 = {T_star:.3f}")
print(f"  observed P(target) peak = {target_probs_q[peak_idx]:.3f} at t={peak_t:.2f}")
print(f"  P(target) at classical uniform 1/N = {1.0/N:.3f}")
print(f"  P(target) at classical step {N} = {target_probs_c[N]:.3f}")
print(f"  P(target) at classical max ({T_CLASS_MAX} steps) = "
      f"{target_probs_c.max():.3f}")
print(f"  speedup at first peak: quantum t≈{peak_t:.2f} vs classical O(N)={N} steps")
print(f"  H eigvals (rad/s): {np.round(np.linalg.eigvalsh(H), 3).tolist()}")
print(f"  shots used in uniqc sanity: 2000")
print(f"  PNG -> {out_path}")

运行结果

运行方式

# 仓库根目录执行；输出 PNG 到 demos/ch12-quantum-graphs/03_spatial_search.png，关键统计到 stdout
.venv/bin/python3 demos/ch12-quantum-graphs/03_spatial_search.py

---

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