量子科技中心_量科网

二进制喷漆车间问题（BPSP）是汽车制造领域的一个APX难优化问题：给定由n种不同车型（每种车型出现两次）组成的2n辆汽车序列，需决定每辆车采用两种颜色中的哪一种进行喷涂，既要确保同一车型的两次出现采用不同颜色，又要最小化连续颜色切换次数。其核心性能指标是喷漆切换率（即每辆车的平均颜色更换次数），直接影响生产效率和成本。先前研究表明，深度p=7的量子近似优化算法（QAOA）可实现0.393的喷漆切换率，优于经典递归贪心算法（RG）的预期值0.4[《物理评论A》104卷012403页(2021年)]。近期有猜想认为经典递归星型贪心算法（RSG）预期值可达0.361。 本研究通过将BPSP形式化归约为加权最大割问题，建立了QAOA应用于该问题的理论基础，并在此框架下比较了两种最先进低深度QAOA变体——表达型QAOA（XQAOA）和递归QAOA（RQAOA）在深度p=1时（记作XQAOA1和RQAOA1）与当前最强经典启发式算法的表现。在27至212辆汽车的测试案例中，XQAOA1平均切换率达0.357，优于RQAOA1及所有已知经典启发式算法（包括RSG的猜想值）。令人惊讶的是，RQAOA1性能随问题规模增大而递减：尽管每个递归步骤均采用可证明最优的QAOA1参数，但在多数211辆案例和全部212辆案例中均被RSG超越。据我们所知，这是首次揭示RQAOA1的大规模性能退化现象。与之形成鲜明对比的是，XQAOA1在所有规模下均保持稳定，显示出渐近超越所有已知启发式算法的强大潜力。