量子科技中心_量科网

Jordan等人近期发表的论文提出了一种名为“解码量子干涉测量法”（Decoded Quantum Interferometry, DQI）的新型量子算法，该算法利用量子傅里叶变换将线性优化问题（max-XORSAT和max-LINSAT）简化为解码问题。在该工作中，研究人员将DQI拓展至含二次约束的优化问题（称为max-QUADSAT）。通过建立与二次高斯和的关联，该团队提出了一种高效制备max-QUADSAT问题DQI量子态的方法。为证明该算法具有量子优势，研究人员引入了“二次最优多项式交会”（quadratic-OPI）问题——这是OPI问题的受限变体，据所知，标准DQI框架对此类问题无法提供算法加速。研究证实quadratic-OPI是max-QUADSAT的实例，并利用新算法实现优化。最后，该工作针对约束满足比例提出了广义化的“半圆定律”证明，将其推广至任何满足以下条件的DQI问题量子态：随机赋值下约束满足次数的分布充分接近二项分布。该条件在max-LINSAT的DQI量子态中严格成立，在max-QUADSAT情况下近似成立，且随着问题规模增大近似精度呈指数级提升，从而为算法性能提供了理论保证。