1. 量子退火与加权图二分问题概述量子退火Quantum Annealing, QA是一种利用量子力学特性解决组合优化问题的算法。它的核心思想是通过量子隧穿效应跳出局部最优解最终收敛到全局最优解。在过去的二十年里量子退火已经从理论模型发展为商业化的量子计算设备如D-Wave系统。加权图二分问题Weighted Graph Bipartitioning Problem, GBP是组合优化中的一个经典问题。给定一个带权无向图G(V,E)其中V是顶点集合E是边集合每条边(i,j)∈E都有一个权重wij。问题的目标是将顶点集合V划分为两个大小相等的子集A和B即|A||B||V|/2使得跨越两个子集的边权重之和最小。这个问题的难点在于划分必须严格满足大小相等的约束条件随着顶点数增加可能的划分方案呈指数级增长边权重的存在使得问题比普通图二分更加复杂2. 不公平采样现象及其影响2.1 不公平采样的定义与表现在量子退火中当问题存在多个能量相同的基态即简并基态时理想情况下这些基态应该被均匀采样。然而实际观察到的现象是某些基态比其他基态更容易被采样到这种现象被称为不公平采样Unfair Sampling。具体表现为在多次运行量子退火后某些基态出现的频率显著高于其他基态即使延长退火时间这种偏差仍然存在偏差模式与问题实例和参数设置密切相关2.2 不公平采样的实际影响不公平采样在应用中会带来诸多问题多样性评估失真在需要评估解决方案多样性的场景中采样偏差会导致评估结果不准确。组合计数误差当使用量子退火进行组合计数如计算满足特定条件的配置数量时采样偏差会直接影响计数结果的准确性。优化性能下降在某些应用中均匀采样所有最优解有助于找到更好的最终解。采样偏差会限制这种探索能力。3. 研究方法与实验设计3.1 量子退火的数学模型量子退火的过程可以用时变哈密顿量描述H(t) A(t)H₀ B(t)H_P其中H₀是驱动哈密顿量通常取为横向场H₀ -ΣσxᵢH_P是问题哈密顿量编码了优化目标A(t)和B(t)是退火调度函数控制着从H₀到H_P的转变对于加权图二分问题问题哈密顿量需要同时考虑目标函数和约束条件H_P H_obj μH_const其中μ是惩罚系数控制约束条件的严格程度。3.2 实验设计与参数设置本研究采用了以下实验方法数值模拟使用QuTiP量子模拟包求解含时薛定谔方程系统规模4到12个自旋顶点退火时间T从10⁻¹到10⁴无量纲单位惩罚系数μ从0到5.0硬件实验使用D-Wave Advantage2量子退火机退火时间200μs采样次数4×10⁶次采用并行退火和自旋反转变换技术实例生成随机生成100个加权图实例顶点数N∈{4,6,8,10,12}边连接概率0.5边权重1到N的均匀整数分布4. 惩罚系数对采样公平性的影响4.1 单个实例的详细分析研究首先分析了一个具有6个顶点的代表性实例如图1所示。该实例有4个简并基态考虑全局自旋翻转对称性后为2个独特状态。关键发现当惩罚系数μ0.2时基态概率分布不均匀两个基态各占约40%概率另外两个基态各占约10%概率这种偏差在长退火时间T≈10⁴下仍然存在惩罚系数的影响增加μ可以改善采样公平性提高熵值S但同时会降低基态概率P_GS在近绝热区域T≈10⁴增加μ可以改善公平性而不牺牲P_GS4.2 D-Wave硬件实验结果在D-Wave Advantage2系统上的实验显示基态概率P_GS随惩罚系数的变化初始阶段μ增加P_GS上升由于基态与第一激发态能隙增大后续阶段μ继续增加P_GS下降约束项主导抑制目标优化采样公平性变化熵值S的变化幅度小于模拟结果但仍观察到不公平采样现象最优公平性出现在μ0.4附近4.3 多实例统计分析对随机生成的100个实例进行统计分析发现系统大小N4时所有实例都表现出公平采样S2随着N增大不公平采样实例比例增加但增加惩罚系数仍能改善多数实例的公平性单调改善比例N691%N874%N1072%N1274%这表明虽然增加惩罚系数不能保证在所有情况下都改善公平性但在大多数实例约70-75%中是有效的。5. 技术实现细节与注意事项5.1 问题编码与嵌入在D-Wave系统上实现加权图二分问题需要注意QUBO公式转换目标函数转换为二次无约束二进制优化(QUBO)形式约束条件通过惩罚项引入硬件嵌入D-Wave的Chimera/Topology结构需要将问题图嵌入到硬件图长链(chain)会影响性能需要优化嵌入方式参数缩放问题哈密顿量需要按D-Wave的自动缩放因子归一化确保能量尺度与硬件匹配5.2 数值模拟技巧进行高效准确的数值模拟需要注意时间步长选择需要足够小以保证精度但又不能太小以免计算量过大基态识别需要准确识别所有简并基态考虑全局自旋翻转对称性熵计算使用香农熵量化公平性S -Σpᵢlog₂pᵢ仅当P_GS≈1时计算才有意义5.3 实验优化技巧提高硬件实验成功率的关键点并行退火使用多个嵌入同时运行提高采样效率自旋反转变换(SRT)减少系统误差提高基态概率退火时间调整适当延长退火时间实验中用200μs权衡运行时间和结果质量6. 结果讨论与潜在应用6.1 惩罚系数的双重作用研究发现惩罚系数μ具有双重影响可行性保证足够大的μ确保基态满足约束条件传统上μ只考虑这一点公平性调节μ还能影响简并基态的采样分布这为量子优化提供了新的控制维度6.2 实际应用中的权衡在实际应用中需要权衡公平性与成功概率增加μ改善公平性但可能降低P_GS需要根据应用需求选择合适μ值问题规模影响小系统(N≤6)更容易实现公平采样大系统需要更精细的参数调节6.3 未来研究方向基于本研究未来可能的方向包括理论机制研究使用简并微扰理论分析不公平采样理解惩罚系数影响公平性的物理机制硬件噪声影响定量研究噪声和热弛豫对公平性的影响开发抗噪声方案替代驱动哈密顿量研究XY混合器等约束保持驱动可能改变不公平采样行为扩展到其他问题将研究框架应用到其他约束优化问题如旅行商问题、调度问题等7. 结论与实操建议本研究系统地探讨了量子退火在加权图二分问题中的不公平采样现象特别是惩罚系数对采样公平性的影响。主要结论如下不公平采样是量子退火中的普遍现象即使在绝热条件下也存在。增加惩罚系数可以改善多数实例约70-75%的采样公平性。这种改善可能需要以降低基态概率为代价特别是在非绝热条件下。在实际硬件上观察到了与模拟定性一致的行为尽管公平性改善幅度较小。对于实际应用量子退火解决约束优化问题的研究者建议惩罚系数选择不要仅基于可行性选择μ考虑其对采样公平性的影响通过小规模测试确定最佳μ范围系统规模考虑小系统更容易实现公平采样大系统需要更谨慎的参数调节验证方法同时监控P_GS和S确保公平性改善不以性能大幅下降为代价硬件使用技巧采用并行退火和SRT技术适当延长退火时间多次运行验证结果稳定性量子退火在约束优化问题中的应用仍有许多未解之谜不公平采样现象及其调控机制的研究将为这一领域带来新的见解和突破。