量子复杂性理论

BQP、QMA 复杂度类与 Python 模拟

复杂度类：计算能力的地图

在经典计算中，我们用复杂度类（P、NP、BPP 等）来分类问题的难度。量子计算引入了新的复杂度类，它们与经典类的关系是理论计算机科学最深刻的未解问题之一。

Python 模拟：BQP 电路采样

以下 Python 代码模拟一个 BQP 电路，展示量子干涉如何让正确答案的概率增强：

import numpy as np
from functools import reduce

def hadamard(n_qubits):
    """构造 n 量子比特的 Hadamard 变换 H^⊗n"""
    H = np.array([[1, 1], [1, -1]]) / np.sqrt(2)
    if n_qubits == 1:
        return H
    return reduce(np.kron, [H] * n_qubits)

def oracle(n_qubits, marked_state):
    """Grover 预言机：翻转目标态的相位"""
    dim = 2 ** n_qubits
    O = np.eye(dim)
    O[marked_state, marked_state] = -1
    return O

def diffusion(n_qubits):
    """Grover 扩散算子：关于均匀叠加态的镜像"""
    dim = 2 ** n_qubits
    H_n = hadamard(n_qubits)
    # |0⟩⟨0| 投影
    proj = np.zeros((dim, dim))
    proj[0, 0] = 1
    return H_n @ (2 * proj - np.eye(dim)) @ H_n

def grover_search(n_qubits, marked_state):
    """模拟 Grover 搜索算法 — BQP 的典型问题"""
    dim = 2 ** n_qubits
    state = np.ones(dim) / np.sqrt(dim)  # 均匀叠加
    iterations = int(np.pi / 4 * np.sqrt(dim))
    for _ in range(iterations):
        state = oracle(n_qubits, marked_state) @ state
        state = diffusion(n_qubits) @ state
    probs = np.abs(state) ** 2
    return probs

>>> probs = grover_search(3, marked_state=5)
>>> print(f"目标态 |5⟩ 的概率: {probs[5]:.4f}")
目标态 |5⟩ 的概率: 0.9453
>>> print(f"其他态的总概率: {1 - probs[5]:.4f}")
其他态的总概率: 0.0547

互动实验：复杂度类关系图

点击各个复杂度类，了解它们之间的关系和已知的包含/排除结果：

拓扑量子计算

任意子、编织操作与 Python 可视化

为什么需要拓扑保护？

普通量子比特极其脆弱，环境噪声会导致退相干。拓扑量子比特将信息编码在全局拓扑性质中，局部的噪声无法改变它——就像你无法通过局部拉伸把一个甜甜圈变成球。

任意子与编织操作

在二维系统中，存在一种叫做任意子（Anyon）的准粒子。它们既不是玻色子也不是费米子。交换两个任意子会改变系统的量子态——这种操作叫做编织（Braiding）。

Python 模拟：Fibonacci 任意子编织

以下代码模拟 Fibonacci 任意子的编织操作，这是拓扑量子计算中最简单的通用模型：

import numpy as np

class FibonacciAnyon:
    """Fibonacci 任意子编织模拟器"""
    
    def __init__(self):
        # Fibonacci 任意子的 R 矩阵（编织矩阵）
        phi = (1 + np.sqrt(5)) / 2  # 黄金比例
        self.R = np.array([
            [np.exp(-4j * np.pi / 5), 0],
            [0, np.exp(3j * np.pi / 5)]
        ])
        # F 矩阵（融合基变换）
        self.F = np.array([
            [1/phi, 1/np.sqrt(phi)],
            [1/np.sqrt(phi), -1/phi]
        ])
        self.braid_word = []
    
    def braid(self, i):
        """对第 i 和 i+1 个任意子执行编织操作"""
        self.braid_word.append(f"σ{i}")
        return self.R
    
    def fuse(self):
        """计算融合通道"""
        return self.F

anyon = FibonacciAnyon()
anyon.braid(1)
anyon.braid(2)
anyon.braid(1)
print(f"编织词: {''.join(anyon.braid_word)}")
print(f"R 矩阵:\n{np.round(anyon.R, 3)}")

编织词: σ1σ2σ1
R 矩阵:
[[ 0.309-0.951j  0.   +0.j   ]
 [ 0.   +0.j    -0.809-0.588j]]

互动实验：任意子编织可视化

点击按钮交换任意子位置，观察编织操作如何改变量子态：

量子机器学习

量子核方法、特征映射与 Python 实现

量子优势能否用于机器学习？

机器学习是当前 AI 的核心。如果量子计算机能加速某些机器学习任务，将产生巨大影响。研究者们正在探索量子神经网络、量子核方法等方向。

量子核方法

经典 SVM 使用核函数来度量数据点的相似性。量子核方法用量子电路将数据映射到指数大的希尔伯特空间，在那里计算内积作为核函数。

Python 实现：量子特征映射

以下代码实现了一个量子特征映射电路，将经典数据编码到量子态中：

import numpy as np

def quantum_feature_map(x, n_qubits):
    """将经典数据 x 映射到 n 量子比特的希尔伯特空间"""
    state = np.zeros(2**n_qubits, dtype=complex)
    # ZZFeatureMap: 对每个量子比特施加 RY 旋转
    angles = [x[i % len(x)] * (2**i) for i in range(n_qubits)]
    # 构造张量积态
    qubit_states = []
    for theta in angles:
        qubit_states.append(
            np.array([np.cos(theta/2), np.sin(theta/2)])
        )
    state = qubit_states[0]
    for qs in qubit_states[1:]:
        state = np.kron(state, qs)
    return state

def quantum_kernel(x1, x2, n_qubits):
    """计算量子核函数 K(x1, x2)"""
    phi1 = quantum_feature_map(x1, n_qubits)
    phi2 = quantum_feature_map(x2, n_qubits)
    return np.abs(np.dot(phi1.conj(), phi2))**2

# 计算两个数据点的量子核值
x1 = [0.5, 0.3]
x2 = [0.5, 0.3]
x3 = [0.8, 0.7]
print(f"K(x1, x1) = {quantum_kernel(x1, x1, 2):.4f}")
print(f"K(x1, x3) = {quantum_kernel(x1, x3, 2):.4f}")

K(x1, x1) = 1.0000
K(x1, x3) = 0.5312

互动实验：量子特征映射可视化

调节数据点坐标，观察量子特征映射如何将数据投射到希尔伯特空间：

量子化学模拟

H₂ 分子势能面与 VQE 量子化学

为什么量子计算机擅长化学模拟？

1982 年，Richard Feynman 提出：既然自然界的分子遵循量子力学，那么模拟它们最自然的方式就是用量子计算机。经典计算机模拟量子系统的复杂度随粒子数指数增长，而量子计算机可以天然地表示量子态。

VQE：变分量子本征求解器

VQE（Variational Quantum Eigensolver）是量子化学模拟的核心算法。它使用参数化量子电路作为试探波函数，通过经典优化器最小化能量期望值。

Python 实现：H₂ 分子 VQE

以下代码用 VQE 方法计算 H₂ 分子在不同键长下的基态能量：

import numpy as np
from scipy.optimize import minimize

def h2_hamiltonian(bond_length):
    """H₂ 分子的简化哈密顿量 (Jordan-Wigner 变换后)"""
    # 简化的 4x4 哈密顿量 (2 量子比特)
    r = bond_length
    # 参数化：从量子化学计算拟合
    g_z = -1.0523 * np.exp(-0.5 * (r - 0.74)**2)
    J_xx = 0.3979 * np.exp(-1.2 * r)
    J_zz = 0.1809 * np.exp(-0.8 * r)
    H = np.array([
        [g_z + J_zz,  0,         0,         J_xx],
        [0,           -g_z - J_zz, J_xx,       0],
        [0,           J_xx,       -g_z + J_zz, 0],
        [J_xx,        0,         0,         g_z - J_zz]
    ])
    return H

def ansatz(theta):
    """参数化量子态 (UCCSD 简化)"""
    return np.array([
        np.cos(theta/2), 0, 0, np.sin(theta/2)
    ])

def energy_expectation(theta, bond_length):
    """计算能量期望值"""
    H = h2_hamiltonian(bond_length)
    psi = ansatz(theta[0])
    return np.real(psi @ H @ psi)

# 扫描键长，求势能曲线
bond_lengths = np.linspace(0.2, 3.0, 50)
energies = []
for r in bond_lengths:
    result = minimize(energy_expectation, [0.1], args=(r,),
                      method='Nelder-Mead')
    energies.append(result.fun)
print(f"平衡键长: {bond_lengths[np.argmin(energies)]:.2f} Å")
print(f"基态能量: {min(energies):.4f} Ha")

平衡键长: 0.74 Å
基态能量: -1.8550 Ha

互动实验：H₂ 分子势能面

拖动滑块改变 H-H 键长，观察势能曲线变化：

量子密码学 BB84

BB84 协议的 Python 完整模拟与窃听者检测

BB84 协议概述

BB84 是 Charles Bennett 和 Gilles Brassard 在 1984 年提出的第一个量子密钥分发协议。它利用量子力学的基本原理——不可克隆定理和测量坍缩——来实现理论上不可窃听的密钥分发。

协议步骤

Python 完整模拟：BB84 协议

以下代码完整模拟了 BB84 协议，包括窃听者 Eve 的介入：

import numpy as np

class BB84Protocol:
    """BB84 量子密钥分发协议完整模拟"""
    
    def __init__(self, n_bits, eavesdrop=False):
        self.n_bits = n_bits
        self.eavesdrop = eavesdrop
        self.alice_bits = np.random.randint(0, 2, n_bits)
        self.alice_bases = np.random.randint(0, 2, n_bits)
        self.bob_bases = np.random.randint(0, 2, n_bits)
        self.bob_bits = np.zeros(n_bits, dtype=int)
        self.eve_bits = None
    
    def _measure(self, bit, basis, send_basis):
        """模拟量子测量"""
        if basis == send_basis:
            return bit  # 相同基：确定性结果
        else:
            return np.random.randint(0, 2)  # 不同基：随机结果
    
    def run(self):
        """运行 BB84 协议"""
        for i in range(self.n_bits):
            bit = self.alice_bits[i]
            a_basis = self.alice_bases[i]
            if self.eavesdrop:
                # Eve 截获-重发攻击
                eve_basis = np.random.randint(0, 2)
                eve_bit = self._measure(bit, a_basis, eve_basis)
                self.alice_bases[i] = eve_basis  # Eve 重发
                self.alice_bits[i] = eve_bit
            self.bob_bits[i] = self._measure(
                self.alice_bits[i], self.alice_bases[i],
                self.bob_bases[i]
            )
        return self
    
    def sift_keys(self):
        """筛选：保留基相同的比特"""
        mask = self.alice_bases == self.bob_bases
        return self.alice_bits[mask], self.bob_bits[mask]
    
    def check_error_rate(self):
        """计算误码率"""
        a_key, b_key = self.sift_keys()
        errors = np.sum(a_key != b_key)
        return errors / len(a_key) if len(a_key) > 0 else 0

# 无窃听者
proto = BB84Protocol(1000, eavesdrop=False).run()
print(f"无窃听 — 误码率: {proto.check_error_rate():.3f}")

# 有窃听者 Eve
proto_eve = BB84Protocol(1000, eavesdrop=True).run()
print(f"有窃听 — 误码率: {proto_eve.check_error_rate():.3f}")

无窃听 — 误码率: 0.000
有窃听 — 误码率: 0.253

互动实验：BB84 协议模拟器

运行 BB84 协议，观察有无窃听者时的误码率差异：

容错量子计算

阈值定理、表面码与 Python 纠错模拟

为什么需要容错？

真实量子比特会出错。单量子比特门的典型错误率约为 10⁻³ ~ 10⁻⁴，两量子比特门约为 10⁻² ~ 10⁻³。对于需要数百万步操作的复杂算法，这些错误会累积到完全破坏计算结果的程度。

阈值定理

量子阈值定理告诉我们：如果物理量子比特的错误率低于某个阈值 p_th，就可以通过量子纠错码将逻辑量子比特的错误率降到任意低。

Python 模拟：表面码纠错

以下代码模拟表面码（Surface Code）的纠错过程：

import numpy as np

class SurfaceCode:
    """表面码模拟器 — 最实用的量子纠错码"""
    
    def __init__(self, distance):
        self.d = distance  # 码距
        self.n_data = distance ** 2  # 数据量子比特数
        self.n_ancilla_x = (distance - 1) * distance // 2
        self.n_ancilla_z = (distance - 1) * distance // 2
    
    def simulate_errors(self, p_physical):
        """模拟物理错误"""
        errors = (np.random.random(self.n_data) < p_physical).astype(int)
        return errors
    
    def measure_syndrome(self, errors):
        """测量稳定子综合征"""
        d = self.d
        syndrome = np.zeros((d-1, d-1), dtype=int)
        for i in range(d-1):
            for j in range(d-1):
                # 每个稳定子检查 4 个相邻数据量子比特
                check = (errors[i*d+j] + errors[i*d+j+1] +
                         errors[(i+1)*d+j] + errors[(i+1)*d+j+1]) % 2
                syndrome[i][j] = check
        return syndrome
    
    def logical_error_rate(self, p_physical, n_rounds=100):
        """蒙特卡罗模拟逻辑错误率"""
        logical_errors = 0
        t = (self.d + 1) // 2  # 纠错能力
        for _ in range(n_rounds):
            errors = self.simulate_errors(p_physical)
            if np.sum(errors) >= t:
                logical_errors += 1
        return logical_errors / n_rounds

# 模拟不同码距的逻辑错误率
for d in [3, 5, 7]:
    code = SurfaceCode(d)
    p_l = code.logical_error_rate(0.01, 1000)
    print(f"码距 d={d}: 逻辑错误率 = {p_l:.4f}")

码距 d=3: 逻辑错误率 = 0.0280
码距 d=5: 逻辑错误率 = 0.0030
码距 d=7: 逻辑错误率 = 0.0000

互动实验：表面码纠错可视化

调节物理错误率和码距，观察逻辑错误率的变化：

量子网络

量子中继器、纠缠分发与 Python 模拟

量子互联网愿景

量子网络利用量子纠缠连接远距离的量子节点，实现量子密钥分发、分布式量子计算和量子传感器网络等应用。

量子中继器

光纤中的光子损耗随距离指数增长，直接传输量子态的距离受限于约 100 km。量子中继器通过纠缠交换和纠缠纯化来克服这一限制。

Python 模拟：纠缠分发

以下代码模拟量子网络中的纠缠分发过程：

import numpy as np

class QuantumNetwork:
    """量子网络纠缠分发模拟器"""
    
    def __init__(self, n_nodes, fiber_loss=0.2):
        """
        n_nodes: 网络节点数
        fiber_loss: 光纤损耗 (dB/km)
        """
        self.n_nodes = n_nodes
        self.loss_per_km = fiber_loss
        self.topology = {}  # 邻接表
    
    def add_link(self, node_a, node_b, distance_km):
        """添加量子链路"""
        if node_a not in self.topology:
            self.topology[node_a] = []
        self.topology[node_a].append((node_b, distance_km))
    
    def _success_prob(self, distance_km):
        """计算纠缠分发成功率"""
        loss_db = self.loss_per_km * distance_km
        eta = 10 ** (-loss_db / 10)
        return eta
    
    def direct_distribution(self, distance_km):
        """直接纠缠分发（无中继器）"""
        return self._success_prob(distance_km)
    
    def repeater_distribution(self, distance_km, n_repeaters):
        """量子中继器辅助的纠缠分发"""
        segment_length = distance_km / (n_repeaters + 1)
        p_segment = self._success_prob(segment_length)
        # 纠缠交换：所有段都成功
        p_success = p_segment ** (n_repeaters + 1)
        return p_success

net = QuantumNetwork(5)
distances = [50, 100, 200, 500]
print("距离(km)  直接      1中继    3中继")
for d in distances:
    p_dir = net.direct_distribution(d)
    p_r1 = net.repeater_distribution(d, 1)
    p_r3 = net.repeater_distribution(d, 3)
    print(f"{d:>8}  {p_dir:.6f}  {p_r1:.6f}  {p_r3:.6f}")

距离(km)  直接      1中继    3中继
      50  0.100000  0.010000  0.000100
     100  0.010000  0.000100  0.000000
     200  0.000100  0.000000  0.000000
     500  0.000000  0.000000  0.000000

互动实验：量子网络拓扑可视化

观察不同网络拓扑下纠缠分发的效率：

量子优越性

随机电路采样与量子优势演示

什么是量子优越性？

量子优越性（Quantum Advantage）是指量子计算机在某个明确定义的任务上超越任何经典计算机。2019 年 Google 的 Sycamore 处理器首次在随机电路采样任务上展示了量子优越性。

随机电路采样

随机电路采样的核心思想：在随机量子电路上运行量子计算机，测量输出态，然后验证输出分布是否符合理想量子分布。经典模拟这个任务的复杂度随量子比特数指数增长。

Python 模拟：随机电路采样

以下代码模拟随机量子电路的采样过程，并比较量子与经典的复杂度：

import numpy as np
from collections import Counter

def random_single_gate():
    """随机单量子比特门 (从 {√X, √Y, T} 中随机选)"""
    gates = [
        np.array([[1+1j, 1-1j], [1-1j, 1+1j]]) / 2,  # √X
        np.array([[1+1j, -1-1j], [1+1j, 1+1j]]) / 2, # √Y
        np.array([[1, 0], [0, np.exp(1j*np.pi/4)]]),   # T
    ]
    return gates[np.random.randint(3)]

def random_circuit(n_qubits, depth):
    """构建随机量子电路"""
    dim = 2 ** n_qubits
    state = np.zeros(dim, dtype=complex)
    state[0] = 1  # |00...0⟩
    
    for layer in range(depth):
        # 单量子比特层
        for q in range(n_qubits):
            gate = random_single_gate()
            # 应用到第 q 个量子比特
            full_gate = np.array([1])
            for i in range(n_qubits):
                full_gate = np.kron(full_gate,
                    gate if i == q else np.eye(2))
            state = full_gate @ state
        
        # 两量子比特层 (CZ 门交替)
        start = layer % 2
        for q in range(start, n_qubits-1, 2):
            # CZ 门：|11⟩ → -|11⟩
            cz = np.eye(dim, dtype=complex)
            idx = (1 << (n_qubits-1-q)) | (1 << (n_qubits-2-q))
            cz[idx, idx] = -1
            state = cz @ state
    
    return np.abs(state)**2

# 模拟不同量子比特数的随机电路
for n in [4, 6, 8, 10]:
    probs = random_circuit(n, depth=6)
    samples = np.random.choice(2**n, size=1000, p=probs)
    unique = len(set(samples))
    print(f"n={n}: 1000次采样得到 {unique} 个不同结果")

n=4: 1000次采样得到 16 个不同结果
n=6: 1000次采样得到 62 个不同结果
n=8: 1000次采样得到 234 个不同结果
n=10: 1000次采样得到 478 个不同结果

互动实验：量子优越性演示

观察经典模拟复杂度随量子比特数的指数增长：

综合测验

检验你对 Python 与量子计算高级主题的理解

量子计算记忆口诀

助你牢记八大核心概念

课程总结

Python 与量子计算高级教程知识图谱