Demo 3：Grover 密码破解

第 16 章 译码与量子密码分析 · 本章演示 · 代码演示总索引

可视化：单子图 —— 8-qubit 搜索 P=0b11010110

对应教程：第 16 章 译码与量子密码分析 中相关小节 · 依赖安装：pip install "unified-quantum[visualization,simulation]"

实现要点

核心：Grover 算法把 N=2^K 个候选密钥上的穷搜加速到 O(√N) 次迭代。本 demo 演示一个 toy 8-bit 密码 P = 0b11010110 = 214： 密码空间 N = 2^8 = 256； 完整 Grover 最优迭代 ⌊π/4 · √N⌋ = ⌊π/4 · 16⌋ ≈ 12； 本 demo 跑 0..4 次迭代展示 P(correct) 从均匀 1/256 ≈ 0.004 单调上升 到接近 1。每一步 Grover 包含 phase oracle（标记 |P⟩）和 diffusion operator（绕平均振幅反射）。

完整源码

demos/ch16-cryptanalysis-coding/03_grover_code_crack.py

"""
ch16-cryptanalysis-coding demo 3: Grover's algorithm brute-forcing an 8-bit password

对应教程：chenzhaoyun.com/quantum-tutorial/ch16-cryptanalysis-coding/quantum-cryptanalysis.html
核心：Grover 算法把 N=2^K 个候选密钥上的穷搜加速到 O(√N) 次迭代。本 demo
     演示一个 toy 8-bit 密码 P = 0b11010110 = 214：
       密码空间 N = 2^8 = 256；
       完整 Grover 最优迭代 ⌊π/4 · √N⌋ = ⌊π/4 · 16⌋ ≈ 12；
       本 demo 跑 0..4 次迭代展示 P(correct) 从均匀 1/256 ≈ 0.004 单调上升
       到接近 1。每一步 Grover 包含 phase oracle（标记 |P⟩）和 diffusion
       operator（绕平均振幅反射）。

依赖：pip install unified-quantum[visualization]
运行：python demos/ch16-cryptanalysis-coding/03_grover_code_crack.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
PASSWORD_INT = 0b11010110  # = 214
PASSWORD_BIN = format(PASSWORD_INT, "08b")
N_QUBITS = 8
SHOTS = 1500
MAX_ITERATIONS = 5  # demo: 0..4 iterations


def password_bits(p_int: int, n_bits: int) -> list[int]:
    """Return little-endian bit list (q0 = LSB)."""
    return [(p_int >> i) & 1 for i in range(n_bits)]


P_BITS_LE = password_bits(PASSWORD_INT, N_QUBITS)  # little-endian (q0 first)


def phase_oracle(c: Circuit) -> None:
    """Apply -|P> (phase flip on the marked state |P>)."""
    # 1. flip bits that are 0 in P so the marked state is |11111111>
    for q, bit in enumerate(P_BITS_LE):
        if bit == 0:
            c.x(q)
    # 2. multi-controlled Z on |11111111>: H(q_last); MCX; H(q_last)
    c.h(N_QUBITS - 1)
    c.add_gate("X", qubits=[N_QUBITS - 1],
               control_qubits=list(range(N_QUBITS - 1)))
    c.h(N_QUBITS - 1)
    # 3. uncompute the X flips
    for q, bit in enumerate(P_BITS_LE):
        if bit == 0:
            c.x(q)


def diffusion(c: Circuit) -> None:
    """Standard Grover diffusion operator: 2|s><s| - I on n-qubit register."""
    for q in range(N_QUBITS):
        c.h(q)
        c.x(q)
    c.h(N_QUBITS - 1)
    c.add_gate("X", qubits=[N_QUBITS - 1],
               control_qubits=list(range(N_QUBITS - 1)))
    c.h(N_QUBITS - 1)
    for q in range(N_QUBITS):
        c.x(q)
        c.h(q)


def grover_circuit(num_iterations: int) -> Circuit:
    """Build the Grover search circuit with k phase-oracle + diffusion rounds."""
    c = Circuit()
    # 1. uniform superposition
    for q in range(N_QUBITS):
        c.h(q)
    # 2. k Grover iterations
    for _ in range(num_iterations):
        phase_oracle(c)
        diffusion(c)
    # 3. measure
    for q in range(N_QUBITS):
        c.measure(q)
    return c


# === 1. Run Grover at iteration counts 0..MAX_ITERATIONS-1 ===
print("ch16-cryptanalysis-coding-demo-3: Grover for 8-bit password P = 0b"
      f"{PASSWORD_BIN} = {PASSWORD_INT}")
print(f"  password space: 2^{N_QUBITS} = {1 << N_QUBITS}")
print(f"  shots per circuit: {SHOTS}")
print(f"  iteration counts tested: 0..{MAX_ITERATIONS - 1}")

probs_at_target = []  # P(P) at each iteration count
for it in range(MAX_ITERATIONS):
    c = grover_circuit(it)
    r = wait_for_result(
        submit_task(circuit=c, backend="dummy:local:simulator", shots=SHOTS)
    )
    counts = r.counts
    total = sum(int(v) for v in counts.values())
    p_correct = counts.get(PASSWORD_BIN, 0) / max(total, 1)
    probs_at_target.append(p_correct)
    n_unique = len(counts)
    print(f"  iterations={it}: P(P=0b{PASSWORD_BIN}) = {p_correct:.3f}, "
          f"unique outcomes = {n_unique}")


# === 2. matplotlib visualisation: P(P) vs iteration count + per-iteration distribution ===
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(13.0, 5.0))

# Left: P(P) vs iteration count
iter_axis = np.arange(MAX_ITERATIONS)
uniform_prob = 1.0 / (1 << N_QUBITS)
ax1.plot(iter_axis, probs_at_target, "o-", color="#1f77b4", lw=2.2, ms=10,
         label=r"measured $P(\mathrm{correct})$")
ax1.axhline(uniform_prob, color="gray", ls=":", lw=1.2,
            label=fr"uniform $1/2^{N_QUBITS} \approx {uniform_prob:.4f}$")
# Theoretical Grover after k steps: sin^2((2k+1) * arcsin(1/sqrt(N)))
N = 1 << N_QUBITS
theory_iter = np.linspace(0, MAX_ITERATIONS - 1, 200)
theory_probs = [np.sin((2 * k + 1) * np.arcsin(1.0 / np.sqrt(N))) ** 2
                for k in theory_iter]
ax1.plot(theory_iter, theory_probs, "--", color="#d62728", lw=1.4,
         label=r"theory $\sin^2((2k+1)\arcsin(1/\sqrt{N}))$")
opt_iter = int(np.floor(np.pi / 4 * np.sqrt(N)))
ax1.axvline(opt_iter, color="#2ca02c", ls=":", lw=1.0, alpha=0.7,
            label=fr"optimal $k^*=\lfloor\pi\sqrt{{N}}/4\rfloor={opt_iter}$")
ax1.set_xticks(iter_axis)
ax1.set_xticklabels([f"{k}" for k in iter_axis])
ax1.set_xlabel("Grover iteration count k")
ax1.set_ylabel(r"$P(\mathrm{measuring } k = P)$")
ax1.set_ylim(0, 1.05)
ax1.set_title("Grover amplification of correct password\n"
              f"P = 0b{PASSWORD_BIN} ({PASSWORD_INT}), N = 2^{N_QUBITS}")
ax1.grid(alpha=0.3)
ax1.legend(loc="upper left", fontsize=9)

# Right: outcome distribution at iteration MAX_ITERATIONS-1 (most informative)
last_circuit = grover_circuit(MAX_ITERATIONS - 1)
r_last = wait_for_result(
    submit_task(circuit=last_circuit, backend="dummy:local:simulator", shots=SHOTS)
)
counts_last = r_last.counts
total_last = sum(int(v) for v in counts_last.values())
top_outcomes = sorted(counts_last.items(), key=lambda kv: -kv[1])[:12]
top_labels = [bs for bs, _ in top_outcomes]
top_probs = [cnt / total_last for _, cnt in top_outcomes]
colors = ["#d62728" if bs == PASSWORD_BIN else "#1f77b4" for bs in top_labels]
bars = ax2.barh(range(len(top_labels))[::-1], top_probs, color=colors, ec="black", lw=0.5)
for i, p in enumerate(top_probs):
    ax2.text(p + 0.005, len(top_labels) - 1 - i,
             f"{p:.3f}", va="center", fontsize=9)
ax2.set_yticks(range(len(top_labels))[::-1])
ax2.set_yticklabels(top_labels, fontsize=9, family="monospace")
ax2.axvline(uniform_prob, color="gray", ls=":", lw=1.0,
            label=fr"uniform $1/2^{N_QUBITS} \approx {uniform_prob:.4f}$")
ax2.set_xlabel("probability")
ax2.set_xlim(0, max(top_probs) * 1.18)
ax2.set_title(f"top outcomes after {MAX_ITERATIONS - 1} Grover iterations\n"
              f"(red bar = password 0b{PASSWORD_BIN})")
ax2.grid(alpha=0.3, axis="x")
ax2.legend(loc="lower right", fontsize=9)

plt.suptitle(f"ch16-cryptanalysis-coding demo 3: Grover for 8-bit password "
             f"P = 0b{PASSWORD_BIN}", y=1.02)
plt.tight_layout()
out_path = OUT / "03_grover_code_crack.png"
plt.savefig(out_path, dpi=120, bbox_inches="tight")
plt.close()


# === 3. stdout key statistics ===
print(f"\n  P(P) growth with Grover iterations:")
for k, p in enumerate(probs_at_target):
    ratio = p / uniform_prob if uniform_prob > 0 else float('inf')
    print(f"    k={k}: P(P) = {p:.3f}, amplification ratio over uniform = {ratio:.1f}x")
print(f"  theoretical max amplification (k*={opt_iter}): "
      f"P_max ~ {np.sin((2*opt_iter+1)*np.arcsin(1/np.sqrt(N)))**2:.3f}")
print(f"  uniform P = 1/{1 << N_QUBITS} = {uniform_prob:.4f}")
print(f"  total shots across all circuits: {SHOTS * MAX_ITERATIONS}")
print(f"  PNG -> {out_path}")

运行结果

运行方式

# 仓库根目录执行；输出 PNG 到 demos/ch16-cryptanalysis-coding/03_grover_code_crack.png，关键统计到 stdout
.venv/bin/python3 demos/ch16-cryptanalysis-coding/03_grover_code_crack.py

---

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