量子科技中心_量科网

该团队研究了用于具有简并基态的组合优化问题的量子-经典混合马尔可夫链蒙特卡洛（MCMC）算法的公平采样特性。虽然已知量子退火和量子近似优化算法（QAOA）等量子优化启发式方法会导致有偏采样，但量子-经典混合MCMC仅将量子动力学作为提案转换，并通过经典接受步骤来保持细致平衡。利用小型伊辛模型，研究表明MCMC后处理可以纠正量子动力学的采样偏差，并在简并基态上恢复近乎均匀的采样。 随后，该方法被应用于接近可满足性阈值的随机k-SAT问题。对于随机2-SAT问题，结合QAOA辅助的神经提案与单自旋翻转更新的混合MCMC实现了与PT-ICM相当的公平性。对于随机3-SAT问题（此类经典方法已不再适用），混合MCMC仍能实现近似均匀采样。研究人员还考察了解计数，发现所需转换次数与WalkSAT相当。这些结果表明，量子-经典混合MCMC为公平采样和解枚举提供了一个可行的框架。