Demo 3：Simon 算法

第 4 章 经典量子算法 · 本章演示 · 代码演示总索引

可视化：3 子图 —— 3-qubit 隐藏 s=110 经典高斯消元恢复

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

实现要点

Oracle 选取 f(x) = f(x XOR s), 满足: f(000)=f(110)=0, f(001)=f(111)=1, f(010)=f(100)=2, f(011)=f(101)=3. 构造此 oracle 仅需 3 个 CNOT (具体推导见教程), 1 次查询就能从 输入寄存器的量子 Fourier 采样得到线性方程 y . s = 0 (mod 2). 经典需要 O(n . 2^n) 次查询, Simon 算法只需 O(n) 次即可解出 s.

完整源码

demos/ch04-classic-algorithms/03_simon_3qubit.py

"""
ch04 演示 3: Simon 算法, n=3, 隐藏字符串 s=110.
Oracle 选取 f(x) = f(x XOR s), 满足:
  f(000)=f(110)=0, f(001)=f(111)=1,
  f(010)=f(100)=2, f(011)=f(101)=3.
构造此 oracle 仅需 3 个 CNOT (具体推导见教程), 1 次查询就能从
输入寄存器的量子 Fourier 采样得到线性方程 y . s = 0 (mod 2).
经典需要 O(n . 2^n) 次查询, Simon 算法只需 O(n) 次即可解出 s.

对应教程: chenzhaoyun.com/quantum-tutorial/ch04-classic-algorithms/simons-algorithm tutorial.html
依赖: pip install unified-quantum[visualization]
运行: python demos/ch04-classic-algorithms/03_simon_3qubit.py
"""
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
SHOTS = 2000
N = 3
S_BITSTRING = "110"  # 隐串, bitstring[0]=MSB=q[2], bitstring[1]=q[1], bitstring[2]=LSB=q[0]
S_INT = int(S_BITSTRING, 2)  # = 6


def build_simon_circuit():
    """构造完整 Simon 电路: H on input, oracle (3 CNOT),
    H on input, 测量 input 与 output."""
    c = Circuit()
    # H on input register (qubits 0..N-1)
    for q in range(N):
        c.h(q)
    # Oracle U_f for f defined above (see docstring), 仅 3 个 CNOT:
    #   f_bit_0(x) = x_0  -> CNOT(q[0], q[3])
    #   f_bit_1(x) = x_1 XOR x_2  -> CNOT(q[1], q[4]); CNOT(q[2], q[4])
    c.cnot(0, N)
    c.cnot(1, N + 1)
    c.cnot(2, N + 1)
    # H on input
    for q in range(N):
        c.h(q)
    # 测量 input 与 output
    for q in range(2 * N):
        c.measure(q)
    return c


c = build_simon_circuit()
tid = submit_task(circuit=c, backend="dummy:local:simulator", shots=SHOTS)
result = wait_for_result(tid)
counts = result.counts

# uniqc bitstring[i] = qubit[n-1-i], 整根 bitstring 长度 = 6 (3 input + 3 output).
def split_input_output(bs):
    """bitstring 长度 6, 前 3 位 = output (q[5], q[4], q[3]), 后 3 位 = input (q[2], q[1], q[0])."""
    inp = bs[-N:][::-1]  # 末 3 位 -> qubit 顺序 q[0] q[1] q[2]
    out = bs[:N][::-1]   # 前 3 位 -> qubit 顺序 q[3] q[4] q[5]
    return inp, out


total = sum(counts.values())
input_counts = {}
output_counts = {}
joint_counts = {}
for bs, cnt in counts.items():
    inp, out = split_input_output(bs)
    input_counts[inp] = input_counts.get(inp, 0) + cnt
    output_counts[out] = output_counts.get(out, 0) + cnt
    joint_counts[(inp, out)] = joint_counts.get((inp, out), 0) + cnt


input_labels = [f"{i:0{N}b}" for i in range(2 ** N)]
input_vals = np.array([input_counts.get(lbl, 0) for lbl in input_labels])

# 检查 y . s = 0 (mod 2): 对 s_bitstring = "110", 条件是 y_1 XOR y_2 = 0 (即 y_1 = y_2).
def satisfies_simons(y_bitstring):
    """y_bitstring 长度 3, y_bitstring[0]=q[2]=MSB, y_bitstring[2]=q[0]=LSB.
    s=110 -> y_1 + y_2 = 0 (mod 2), 即 y[1] == y[2]."""
    return (int(y_bitstring[1]) + int(y_bitstring[2])) % 2 == 0


consistent = sum(cnt for y, cnt in input_counts.items() if satisfies_simons(y))
inconsistent = total - consistent
forbidden_labels = [lbl for lbl in input_labels if not satisfies_simons(lbl)]


fig, axes = plt.subplots(1, 3, figsize=(15.5, 5.0))

ax = axes[0]
colors = [
    "#2ca02c" if satisfies_simons(lbl) else "#d62728"
    for lbl in input_labels
]
ax.bar(np.arange(len(input_labels)), input_vals / total * 100,
       color=colors, edgecolor="black")
ax.set_xticks(np.arange(len(input_labels)))
ax.set_xticklabels(input_labels, rotation=0, fontsize=10)
ax.set_xlabel("input register  y  (q[2] q[1] q[0])")
ax.set_ylabel("probability (%)")
ax.set_title(
    f"Simon measurement on input register\n"
    f"green = y . s = 0  red = forbidden  (s = {S_BITSTRING})"
)
for i, lbl in enumerate(input_labels):
    if input_vals[i] > 0:
        tag = "ok" if satisfies_simons(lbl) else "bad"
        ax.text(i, input_vals[i] / total * 100 + 1.2,
                f"{input_vals[i]/total*100:.1f}%\n[{tag}]",
                ha="center", va="bottom", fontsize=7,
                color=("darkgreen" if tag == "ok" else "darkred"))
ax.set_ylim(0, max(60, input_vals.max() / total * 100 + 15))
ax.grid(axis="y", alpha=0.3)

ax = axes[1]
out_labels = [f"{i:0{N}b}" for i in range(2 ** N)]
out_vals = np.array([output_counts.get(lbl, 0) for lbl in out_labels])
ax.bar(np.arange(len(out_labels)), out_vals / total * 100,
       color="#9467bd", edgecolor="black")
ax.set_xticks(np.arange(len(out_labels)))
ax.set_xticklabels(out_labels, rotation=0, fontsize=10)
ax.set_xlabel("output register  f(y)  (q[3] q[4] q[5])")
ax.set_ylabel("probability (%)")
ax.set_title(
    f"Simon measurement on output (f(y))\n"
    f"each output value appears twice (from y and y XOR s)"
)
for i, lbl in enumerate(out_labels):
    if out_vals[i] > 0:
        ax.text(i, out_vals[i] / total * 100 + 1.2,
                f"{out_vals[i]/total*100:.1f}%",
                ha="center", va="bottom", fontsize=8)
ax.set_ylim(0, max(60, out_vals.max() / total * 100 + 15))
ax.grid(axis="y", alpha=0.3)

ax = axes[2]
s_bits = [int(b) for b in S_BITSTRING]
xs = np.array([0, 1, 2])
ax.bar(xs, s_bits, color="#1f77b4", edgecolor="black")
ax.set_xticks(xs)
ax.set_xticklabels([f"s_{i}  (q[{N-1-i}])" for i in range(N)])
ax.set_yticks([0, 1])
ax.set_yticklabels(["0", "1"])
ax.set_ylabel("secret bit value")
ax.set_title(
    f"Hidden string s = {S_BITSTRING} (= {S_INT})\n"
    f"y · s = 0 (mod 2)  iff  y[1] = y[2]"
)
for i in range(N):
    ax.text(i, s_bits[i] + 0.05, str(s_bits[i]),
            ha="center", va="bottom", fontsize=12)
ax.set_ylim(0, 1.4)
ax.grid(axis="y", alpha=0.3)

fig.suptitle(
    f"Simon's algorithm  n={N}, s={S_BITSTRING}  "
    f"(shots={SHOTS}, dummy:local:simulator)",
    fontsize=12, y=1.02,
)
plt.subplots_adjust(left=0.06, right=0.99, top=0.84, bottom=0.14)
plt.savefig(OUT / "03_simon_3qubit.png", dpi=120, bbox_inches="tight")
plt.close()


p_consistent = consistent / total
print("ch04-classic-algorithms demo 3: Simon n=3, s=110")
print(f"  shots: {total}")
print(f"  hidden string: s = {S_BITSTRING} (= {S_INT})")
print(f"  P(measured y satisfies y . s = 0): {p_consistent:.4f}")
print(f"  unique input measurement outcomes: {int((input_vals > 0).sum())} of 8")
print(f"  unique output measurement outcomes: {int((out_vals > 0).sum())} of 8")
print(f"  forbidden labels (y . s = 1): {forbidden_labels}")
bad = {lbl: cnt for lbl, cnt in input_counts.items() if not satisfies_simons(lbl)}
if bad:
    print(f"  forbidden shots observed: {bad}")
else:
    print("  no forbidden y observed: all shots satisfy y . s = 0")
print(f"  classical Gaussian elimination on 2 linearly independent y's would recover s")
print(f"  saved: {OUT / '03_simon_3qubit.png'}")

运行结果

运行方式

# 仓库根目录执行；输出 PNG 到 demos/ch04-classic-algorithms/03_simon_3qubit.png，关键统计到 stdout
.venv/bin/python3 demos/ch04-classic-algorithms/03_simon_3qubit.py

---

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