量子科技中心_量科网

在展示量子优势的研究背景下，寻找NP难问题的挑战性实例具有重要价值。鉴于近期含噪声中等规模量子（NISQ）设备的局限性，这些实例的规模越小越有价值。该工作发现了两类顶点数小于1000的图结构：Goemans-Williamson最大割近似算法在此类图上至多能获得0.912的近似比。研究进一步表明，相较之下，近期提出的量子近似优化算法（QAOA，深度p=1）在Karloff图实例上（当n趋近无穷时）可获得0.592近似比，而在某类强正则图上至多只能达到0.894近似比。该团队还通过计算方式扰动边权来构建挑战性实例——该方法可能具有独立研究价值，相关代码已公开于CI-QuBe github仓库。