量子科技中心_量科网

二次无约束二进制优化（QUBO）问题广泛存在于各类应用中，并被证实属于NP难问题。Goemans与Williamson的开创性工作为此类问题引入了半定规划（SDP）松弛方法，该方法可在多项式时间内求解并获得最优值的上界。其研究还启发了随机舍入技术，从而获得具有可证明性能保障的可行解。该工作发现了一类QUBO问题实例，其中矩阵乘积权重法能产生量子及量子启发算法，这些算法能以现有方法指数级的速度逼近Goemans-Williamson SDP解，实现相对于问题维度的多对数时间复杂度。该加速效果在以下条件下可达：当QUBO代价矩阵作为满足特定代数约束的泡利串线性组合表达时具有稀疏性，并充分利用了量子吉布斯态的高效量子与经典模拟结果。研究阐明了如何在已知矩阵分解的情况下高效验证这些条件。此外，该团队探索了随机舍入过程的启发式方法，可在多对数时间内提取QUBO可行解的能量值。虽然这些方法优势显著的应用场景实际意义仍有待全面验证，但研究人员提出了具有更广适用性的启发式算法，并确定克罗内克图是应用该技术的潜在优选类别。通过数值实验对该方法进行基准测试时发现：借助张量网络方法，该研究在桌面计算机上求解了含D=2^50个变量的SDP问题，并提取出经认证与QUBO最优解偏差不超过0.15%的可行点——其处理规模远超现有SDP或QUBO求解器（无论是启发式还是严格方法）数百万倍。