量子科技中心_量科网

二进制喷漆车间问题（BPSP）是一个APX难优化问题：给定包含n种车型（每种车型在长度为2n的序列中出现两次）的序列，目标是找到一种着色方案，使得每款车型的两次出现采用不同颜色，同时最小化整个序列中的颜料切换次数。近期提出的经典启发式算法——递归星型贪婪算法（RSG）据推测可实现0.361的预期颜料切换比率，其表现优于电路深度p=7的量子近似优化算法（QAOA）。由于对数电路深度QAOA的性能与具体实例无关，其平均颜料切换比率存在上界，数值实验表明该值约在0.265至0.282之间。 为提供与硬件相关的对比，该团队还在D-Wave量子退火机Advantage 2上实施了BPSP求解，获得的最低颜料切换比率为0.320。鉴于对数电路深度QAOA在BPSP等稀疏优化问题上未显现量子优势，这意味着存在超越RSG算法和对数深度QAOA的经典算法。通过数值实验证明，平均场近似优化算法（MF-AOA）就是这样一种算法——其颜料切换比率约为0.2799，优于当前所有已知经典启发式算法和量子算法。