3. 量子退火中的嵌入与链断裂处理

问题背景与硬件拓扑约束

量子退火器（如 D-Wave Advantage）的量子比特并非全连接，而是按 Chimera 或 Pegasus 等稀疏拓扑排列。一个逻辑变量往往需要由多个物理量子比特组成的链（chain）共同表示，链内量子比特通过强耦合绑定为同一取值。当链内耦合强度不足或受噪声干扰时，链内量子比特取值不一致，即发生链断裂（chain break），导致采样结果无法直接映射回逻辑解。

本案例以一个 5 变量最大割问题为例，演示从逻辑图到硬件拓扑的嵌入、链断裂诊断，以及通过调整链强度参数降低断裂率的完整流程。

逻辑问题与嵌入结构

设逻辑变量为 x₀…x₄，逻辑边为 (0,1)、(1,2)、(2,3)、(3,4)、(4,0)、(0,2)。硬件拓扑采用简化的 4×4 方格（每个方格单元含 4 个物理量子比特，此处抽象为方格节点），逻辑变量需映射到物理量子比特集合。下图展示逻辑图到硬件拓扑的嵌入关系，以及链断裂在物理层的表现。

嵌入工具与链强度设置

使用 D-Wave 的 minorminer 工具将逻辑图嵌入硬件拓扑，并通过 chain_strength 参数控制链内耦合强度。链强度过小则链断裂率高，过大则压缩有效能量尺度、降低解质量。实践中常用自动链强度估计（如 uniform_torque_compensation）作为起点，再根据链断裂率微调。

import dimod
import minorminer
from dwave.system import DWaveSampler, EmbeddingComposite

# 1. 构造逻辑 QUBO（最大割：割边收益 -1，等价于最小化负割）
# 变量 x0..x4，边 (0,1),(1,2),(2,3),(3,4),(4,0),(0,2)
edges = [(0,1),(1,2),(2,3),(3,4),(4,0),(0,2)]
Q = {}
for i, j in edges:
    Q[(i, j)] = 1.0   # 割边惩罚：同侧时贡献 +1，异侧时 0

bqm = dimod.BinaryQuadraticModel.from_qubo(Q)

# 2. 获取硬件采样器并生成嵌入
sampler = DWaveSampler(solver={'topology__type': 'pegasus'})
embedding = minorminer.find_embedding(bqm.variables, sampler.edgelist)

# 3. 用 EmbeddingComposite 包装，自动处理链
composite = EmbeddingComposite(sampler)

# 4. 设置链强度并采样
chain_strength = 2.0   # 初始值，后续根据链断裂率调整
sampleset = composite.sample(
    bqm,
    chain_strength=chain_strength,
    num_reads=1000,
    annealing_time=20,
    return_embedding=True,
)

# 5. 诊断链断裂率
def chain_break_fraction(sampleset, embedding):
    total, broken = 0, 0
    for sample in sampleset.record.sample:
        for chain in embedding.values():
            vals = {sample[q] for q in chain}
            total += 1
            if len(vals) > 1:
                broken += 1
    return broken / total

cbf = chain_break_fraction(sampleset, embedding)
print(f"链断裂率: {cbf:.3f}")
print(f"最优能量: {sampleset.first.energy:.2f}")

链断裂诊断与参数调整

链断裂率（chain break fraction, CBF）是核心诊断指标。若 CBF 偏高（例如 > 0.1），说明链强度不足或嵌入质量差。调整策略：

• 提高链强度：按 1.5×、2× 逐步增大，观察 CBF 与最优能量的变化；
• 优化嵌入：使用 minorminer 的 find_embedding 多次尝试，选择链长更短、链间重叠更少的嵌入；
• 延长退火时间：给链内量子比特更多时间达成一致。

下表为示例参数扫描结果（教学示例数据，非实测）：

结果判读与验证

对每个采样结果，先按链内多数投票（majority vote）修复链断裂，再映射回逻辑变量，计算逻辑能量。验证要点：

1. CBF 应低于 5%，且随链强度增大单调下降；
2. 修复后的逻辑最优能量应与经典穷举（5 变量共 32 种赋值）一致；
3. 若 CBF 已很低但最优能量仍偏离经典最优，说明嵌入或退火参数（如退火时间）需进一步调整，而非链强度问题。