Demo 1：K3 量子行走

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

可视化：双图（轨迹+经典对照） —— 4 步位置概率演化

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

实现要点

核心：K3 (3-node complete graph) 也是 C3 (3-cycle)。一个 qubit 硬币 (q3) 加三个 一元编码位置 q2 q1 q0，节点 k 的"1"在 q[k]。每一步 = H(q3) 然后受控移位： coin=0 → INC (|001⟩→|010⟩→|100⟩→|001⟩)，coin=1 → DEC (逆序)。INC 与 DEC 都分解成两个 SWAP(q0,q1) 和 SWAP(q0,q2)，在 uniqc 中再用 CSWAP(q3,…) 做受控选择。和经典随机游走对比：量子游走呈现单向漂移（来自单向硬币的干涉）， 而经典游走在三节点环上保持振荡。

完整源码

demos/ch12-quantum-graphs/01_graph_walk.py

"""
ch12-quantum-graphs demo 1: discrete-time coined quantum walk on K3

对应教程：chenzhaoyun.com/quantum-tutorial/ch12-quantum-graphs/adjacency-matrix-properties.html
核心：K3 (3-node complete graph) 也是 C3 (3-cycle)。一个 qubit 硬币 (q3) 加三个
     一元编码位置 q2 q1 q0，节点 k 的"1"在 q[k]。每一步 = H(q3) 然后受控移位：
     coin=0 → INC (|001⟩→|010⟩→|100⟩→|001⟩)，coin=1 → DEC (逆序)。INC 与 DEC
     都分解成两个 SWAP(q0,q1) 和 SWAP(q0,q2)，在 uniqc 中再用 CSWAP(q3,…)
     做受控选择。和经典随机游走对比：量子游走呈现单向漂移（来自单向硬币的干涉），
     而经典游走在三节点环上保持振荡。

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

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
N_NODES = 3
N_QUBITS = 4  # q0 q1 q2 for unary position, q3 for coin

# uniqc bit-string for a 4-qubit circuit reads "q3 q2 q1 q0" (MSB first).
# Unary position: node k has qk = 1, so the "1" sits at bit-string index (3-k).
# The coin is q3 (bit-string index 0).
BS_TO_NODE = {}
for node in range(N_NODES):
    for coin in (0, 1):
        chars = ["0", "0", "0", "0"]
        chars[3 - node] = "1"   # position: q0 at idx 3, q1 at idx 2, q2 at idx 1
        chars[0] = str(coin)    # coin: q3 at idx 0
        BS_TO_NODE["".join(chars)] = node


def walk_circuit(num_steps: int) -> Circuit:
    """Discrete-time coined quantum walk on K3=C3 starting at node 0."""
    c = Circuit()
    c.x(0)                              # initial |001⟩ (node 0)
    for _ in range(num_steps):
        c.h(3)                          # coin toss
        # INC if coin=0 : X(3); CSWAP(3,0,1); CSWAP(3,0,2); X(3)
        c.x(3); c.cswap(3, 0, 1); c.cswap(3, 0, 2); c.x(3)
        # DEC if coin=1 : CSWAP(3,0,2); CSWAP(3,0,1)
        c.cswap(3, 0, 2); c.cswap(3, 0, 1)
    for q in range(N_QUBITS):
        c.measure(q)
    return c


def classical_random_walk(num_steps: int) -> np.ndarray:
    """P[node, t] for a classical random walk on C3 starting at node 0."""
    P = np.zeros((num_steps + 1, N_NODES))
    P[0, 0] = 1.0
    for t in range(1, num_steps + 1):
        P[t] = 0.0
        for prev in range(N_NODES):
            for nxt in [(prev + 1) % N_NODES, (prev - 1) % N_NODES]:
                P[t, nxt] += P[t - 1, prev] * 0.5
    return P


# === 1. Run quantum walk for steps 0..4 ===
print("ch12-quantum-graphs-demo-1: coined quantum walk on K3 = C3")
print(f"  qubits: {N_QUBITS} (3 unary position + 1 coin)")
print(f"  shots per circuit: {SHOTS}")

quant_probs = np.zeros((5, N_NODES))
for t in range(5):
    c = walk_circuit(t)
    r = wait_for_result(
        submit_task(circuit=c, backend="dummy:local:simulator", shots=SHOTS)
    )
    counts = r.counts
    total = sum(counts.values())
    for bs, cnt in counts.items():
        node = BS_TO_NODE.get(bs, -1)
        if node >= 0:
            quant_probs[t, node] += cnt / total
    print(f"  step {t}: " + ", ".join(
        f"P(node {n})={quant_probs[t, n]:.3f}" for n in range(N_NODES)
    ))

total_shots = SHOTS * 5

# === 2. Classical random walk comparison ===
class_probs = classical_random_walk(4)

# === 3. matplotlib 可视化 ===
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12.5, 5.0))

steps = np.arange(5)
node_colors = ["#1f77b4", "#d62728", "#2ca02c"]
node_labels = [f"node {n}" for n in range(N_NODES)]

# Left: quantum walk — probability of each node over 5 steps
for n in range(N_NODES):
    ax1.plot(steps, quant_probs[:, n], "-o", color=node_colors[n],
             lw=2.2, ms=8, label=node_labels[n])
ax1.axhline(1.0 / N_NODES, color="gray", ls=":", lw=1, alpha=0.6,
            label=f"uniform 1/{N_NODES}")
ax1.set_xticks(steps)
ax1.set_xticklabels([f"step {t}" for t in steps])
ax1.set_ylim(0, 1.05)
ax1.set_ylabel("position probability")
ax1.set_xlabel("walk step t")
ax1.set_title("discrete-time coined quantum walk on K3 (shots=600 per step)")
ax1.grid(alpha=0.3)
ax1.legend(loc="upper right", fontsize=9, framealpha=0.9)

# Right: classical vs quantum at each node, side-by-side bars
bar_w = 0.35
x = np.arange(N_NODES)
ax2.bar(x - bar_w / 2, quant_probs[4], bar_w, color="#1f77b4",
        ec="black", lw=0.5, label="quantum @ step 4")
ax2.bar(x + bar_w / 2, class_probs[4], bar_w, color="#ff7f0e",
        ec="black", lw=0.5, label="classical @ step 4")
for n in range(N_NODES):
    ax2.text(n - bar_w / 2, quant_probs[4, n] + 0.012,
             f"{quant_probs[4, n]:.2f}", ha="center", fontsize=8)
    ax2.text(n + bar_w / 2, class_probs[4, n] + 0.012,
             f"{class_probs[4, n]:.2f}", ha="center", fontsize=8)
ax2.set_xticks(x)
ax2.set_xticklabels(node_labels)
ax2.set_ylim(0, 0.75)
ax2.set_ylabel("probability")
ax2.set_title("classical vs quantum distribution after 4 steps")
ax2.grid(alpha=0.3, axis="y")
ax2.legend(loc="upper right", fontsize=9, framealpha=0.9)

# K3 graph inset (sketch)
inset = fig.add_axes([0.78, 0.55, 0.20, 0.35])
theta = np.array([90, 210, 330]) * np.pi / 180.0
xs, ys = 0.6 * np.cos(theta), 0.6 * np.sin(theta)
for i in range(3):
    for j in range(i + 1, 3):
        inset.plot([xs[i], xs[j]], [ys[i], ys[j]], "k-", lw=1.5)
for n, (x_, y_) in enumerate(zip(xs, ys)):
    fc = node_colors[n]
    inset.scatter(x_, y_, s=520, c=fc, ec="black", zorder=3)
    inset.text(x_, y_, str(n), ha="center", va="center", fontsize=11,
               fontweight="bold", color="white", zorder=4)
inset.set_xlim(-1.0, 1.0)
inset.set_ylim(-1.0, 1.0)
inset.set_aspect("equal")
inset.axis("off")
inset.set_title("graph K3", fontsize=9)

plt.suptitle("ch12-quantum-graphs demo 1: coined quantum walk on K3", y=1.02)
plt.tight_layout()
out_path = OUT / "01_graph_walk.png"
plt.savefig(out_path, dpi=120, bbox_inches="tight")
plt.close()

# === 4. stdout 关键统计 ===
print(f"\n  total shots across {5} step counts: {total_shots}")
print(f"  quantum walk position distribution at each step:")
for t in range(5):
    spread = np.max(quant_probs[t]) - np.min(quant_probs[t])
    print(f"    step {t}: max-min spread = {spread:.3f}")
print(f"  classical @ step 4: P = {np.round(class_probs[4], 3).tolist()}")
print(f"  quantum   @ step 4: P = {np.round(quant_probs[4], 3).tolist()}")
print(f"  l1 distance classical vs quantum @ step 4: "
      f"{np.abs(quant_probs[4] - class_probs[4]).sum():.3f}")
print(f"  quantum entropy @ step 4: "
      f"{-np.sum(quant_probs[4] * np.log(quant_probs[4] + 1e-12)):.3f}")
print(f"  PNG -> {out_path}")

运行结果

运行方式

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

---

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