Demo 3：隐藏位移

第 10 章 隐藏结构与群算法 · 本章演示 · 代码演示总索引

可视化：双图 —— 7-qubit van Dam 量子算法 + 经典/量子查询数对比

对应教程：第 10 章 隐藏结构与群算法 中相关小节 · 依赖安装：pip install "unified-quantum[visualization,simulation]"

实现要点

问题（Z_2^3 上的隐藏位移）：f_0(x)=x, f_1(x)=x ⊕ s，s=101 未知。 Bernstein-Hadamard（van Dam）：

1. 准备 |+⟩_sel ⊗ |+⟩^3_data ⊗ |0⟩^3_anc

2. 受控查询 anc ⊕= data ⊕ (sel · s)

3. H on sel + H^⊗3 on data → 测得 (y, b) with b = y·s (mod 2)

4. 收集 n 个样本 + F_2 高斯消元恢复 s

经典查询复杂度 Θ(2^{n/2})（生日碰撞） vs 量子 O(n)。

完整源码

demos/ch10-hidden-structures/03_hidden_shift.py

"""
ch10 演示 3：隐藏位移（hidden shift）的 Bernstein-Hadamard 量子算法

对应教程：chenzhaoyun.com/quantum-tutorial/ch10-hidden-structures/hidden-shift.html
依赖：pip install unified-quantum[visualization]
运行：python demos/ch10-hidden-structures/03_hidden_shift.py

问题（Z_2^3 上的隐藏位移）：f_0(x)=x, f_1(x)=x ⊕ s，s=101 未知。
Bernstein-Hadamard（van Dam）：
  1. 准备 |+⟩_sel ⊗ |+⟩^3_data ⊗ |0⟩^3_anc
  2. 受控查询 anc ⊕= data ⊕ (sel · s)
  3. H on sel + H^⊗3 on data → 测得 (y, b) with b = y·s (mod 2)
  4. 收集 n 个样本 + F_2 高斯消元恢复 s

经典查询复杂度 Θ(2^{n/2})（生日碰撞） vs 量子 O(n)。
"""
from uniqc import Circuit, submit_task, wait_for_result
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
import numpy as np
from pathlib import Path

OUT = Path(__file__).parent
N = 3
S = 0b101  # 隐藏位移 s = (1, 0, 1)
SHOTS = 2000
N_RUNS = 8


def build_hs_circuit(s: int, n: int) -> Circuit:
    """anc[j] = data[j] XOR (sel AND s[j]) via 2-step CNOT 序列。"""
    c = Circuit()
    sel, data, anc = 0, list(range(1, n + 1)), list(range(n + 1, 2 * n + 1))
    c.h(sel)
    for q in data:
        c.h(q)
    for j in range(n):
        c.cnot(data[j], anc[j])  # anc[j] ^= data[j]
    for j in range(n):
        if (s >> j) & 1:
            c.cnot(sel, anc[j])  # anc[j] ^= sel
    c.h(sel)
    for q in data:
        c.h(q)
    c.measure(sel)
    for q in data:
        c.measure(q)
    return c


def gauss_elim_f2(matrix: np.ndarray) -> np.ndarray:
    """F_2 高斯消元，返回增广矩阵的行最简形。"""
    A = matrix.copy().astype(np.uint8)
    n_rows, n_cols = A.shape
    pivot_row = 0
    for col in range(n_cols):
        pr = -1
        for r in range(pivot_row, n_rows):
            if A[r, col] == 1:
                pr = r
                break
        if pr == -1:
            continue
        A[[pivot_row, pr]] = A[[pr, pivot_row]]
        for r in range(n_rows):
            if r != pivot_row and A[r, col] == 1:
                A[r] ^= A[pivot_row]
        pivot_row += 1
    return A


def recover_s_from_samples(samples_y, samples_b, n):
    """从 {(y_i, b_i)} 用 F_2 高斯消元恢复 s，满足 y_i · s = b_i。"""
    if len(samples_y) == 0:
        return 0
    rows = [[(y >> i) & 1 for i in range(n)] + [int(b)]
            for y, b in zip(samples_y, samples_b)]
    rref = gauss_elim_f2(np.array(rows, dtype=np.uint8))
    pivot_rows, non_pivot_cols = {}, []
    for col in range(n):
        for r in range(rref.shape[0]):
            if rref[r, col] == 1 and all(rref[r, cc] == 0 for cc in range(col)):
                pivot_rows[col] = r
                break
        else:
            non_pivot_cols.append(col)
    s_vec = np.zeros(n, dtype=np.uint8)
    if not non_pivot_cols:
        for pc, pr in pivot_rows.items():
            s_vec[pc] = rref[pr, n]
    else:
        fc = non_pivot_cols[-1]
        s_vec[fc] = 1
        for pc, pr in pivot_rows.items():
            s_vec[pc] = (rref[pr, fc] + rref[pr, n]) % 2
    return sum(int(s_vec[i]) << i for i in range(n))


# === 1. 跑 N_RUNS 次电路，收集 (y, b) 样本 ===
circuit = build_hs_circuit(S, N)
print(f"circuit qubits: {circuit.qubit_num}, depth: {circuit.depth}")

samples_y, samples_b = [], []
rng = np.random.default_rng(seed=2024)
for run in range(N_RUNS):
    counts = wait_for_result(
        submit_task(circuit=circuit, backend="dummy:local:simulator", shots=SHOTS)
    ).counts
    # 7 qubits: key = [q6..q0]; sel=key[-1], data(q3,q2,q1)=key[3:6]
    joint = {}
    for bs, cnt in counts.items():
        key = (bs[3:6], int(bs[-1]))
        joint[key] = joint.get(key, 0) + cnt
    max_cnt = max(joint.values())
    chosen = rng.choice([k for k, v in joint.items() if v == max_cnt])
    samples_y.append(int(chosen[0], 2))
    samples_b.append(int(chosen[1]))

samples_y = np.array(samples_y, dtype=np.uint8)
samples_b = np.array(samples_b, dtype=np.uint8)
s_recovered = recover_s_from_samples(samples_y, samples_b, N)

# === 2. matplotlib 可视化（2 子图：测量散点 + 复杂度对比） ===
ns = list(range(3, 14))
classical_q = [2 ** (n / 2) for n in ns]
quantum_q = [n / 0.288 for n in ns]

fig, axes = plt.subplots(1, 2, figsize=(13, 5))

# 左图：测得的 (y, b) 样本与真实约束
ax = axes[0]
y_unique = np.arange(2 ** N)
ax.scatter(samples_y, samples_b, s=120, c="#1f77b4", edgecolor="black", zorder=3,
           label=f"measured (y, b), {N_RUNS} runs")
for y in y_unique:
    b_true = bin(y & S).count("1") % 2
    ax.scatter(y, b_true, s=30, c="#d62728", marker="x", alpha=0.5,
               zorder=2, label="true constraint b = y·s" if y == 0 else None)
ax.set_xticks(y_unique)
ax.set_xticklabels([f"{y:0{N}b}" for y in y_unique], fontsize=9)
ax.set_yticks([0, 1])
ax.set_xlabel("Data register y")
ax.set_ylabel("Selection bit b")
ax.set_title(
    f"Van Dam Bernstein-Hadamard for hidden shift\n"
    f"s = {S:0{N}b}  →  recovered s = {s_recovered:0{N}b} (match = {s_recovered == S})",
    fontsize=10,
)
ax.set_ylim(-0.4, 1.4)
ax.grid(axis="y", alpha=0.3)
ax.legend(loc="upper right", fontsize=9)

# 右图：经典 vs 量子查询复杂度
ax = axes[1]
ax.semilogy(ns, classical_q, "o-", color="#d62728", lw=2, label=r"Classical: $\Theta(2^{n/2})$")
ax.semilogy(ns, quantum_q, "s-", color="#1f77b4", lw=2, label=r"Quantum: $O(n)$ queries")
ax.scatter([N], [2 ** (N / 2)], s=180, color="#d62728", marker="*", edgecolor="black",
           zorder=4, label=f"n={N} (demo)")
ax.scatter([N], [quantum_q[0]], s=180, color="#1f77b4", marker="*",
           edgecolor="black", zorder=4)
ax.set_xlabel("Hidden shift length n")
ax.set_ylabel("Oracle queries (log scale)")
ax.set_title(
    "Exponential separation:\nclassical birthday collision vs quantum Bernstein-Hadamard",
    fontsize=10,
)
ax.grid(True, which="both", alpha=0.3)
ax.legend(loc="upper left", fontsize=9)

fig.suptitle(
    f"Hidden shift problem on Z_2^{N}:  f_0(x)=x, f_1(x)=x ⊕ {S:0{N}b}  "
    f"({N_RUNS} circuit runs × {SHOTS} shots, dummy:local:simulator)",
    fontsize=11, y=1.02,
)
plt.tight_layout()
plt.savefig(OUT / "03_hidden_shift.png", dpi=120, bbox_inches="tight")
plt.close()

# === 3. stdout 关键统计 ===
print("ch10-hidden-structures demo 3: Hidden shift (van Dam Bernstein-Hadamard)")
print(f"  hidden shift s = {S:0{N}b} (binary)")
print(f"  samples collected ({N_RUNS} runs):")
for i, (y, b) in enumerate(zip(samples_y, samples_b)):
    print(f"    run {i}: y={y:0{N}b} ({y}), b={b}  →  y·s = {(y & S).bit_count() % 2} (should = {b})")
print(f"  recovered s = {s_recovered:0{N}b}  (true s = {S:0{N}b}, match = {s_recovered == S})")
print(f"  classical queries for n=3: 2^(n/2) ≈ {2**(N/2):.2f}; quantum: n = {N}")
print(f"  saved: {OUT / '03_hidden_shift.png'}")

运行结果

运行方式

# 仓库根目录执行；输出 PNG 到 demos/ch10-hidden-structures/03_hidden_shift.png，关键统计到 stdout
.venv/bin/python3 demos/ch10-hidden-structures/03_hidden_shift.py

---

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