用国际象棋战术设计量子优化基准，揭示真实问题中算法改进效果。
Quantum King-Ring Domination in Chess: A QAOA Approach
- 基于国际象棋布局构建5000个带约束的结构化量子优化实例
- 约束保持型混频器使收敛速度提升13步，省去惩罚参数调优
- 适合关注量子算法在真实问题上表现的研究者与开发者
量子近似优化算法（QAOA）常在最大割、旅行商等随机实例上测试，但缺乏语义结构与可解释性，难以反映其在实际问题中的性能。本文提出量子王环支配问题（QKRD），一种源于国际象棋战术的NISQ级基准，包含5000个具有单热约束、空间局部性及10–40量子比特规模的结构化实例。该基准结合人类可理解的覆盖度指标与经典启发式算法的内在验证，无需外部参考即可评估算法有效性。实验表明，采用约束保持混频器（如XY、域墙型）时，收敛速度比标准混频器快约13步（p<10^{-7}, d≈0.5），且无需惩罚参数调优；暖启动策略使收敛减少45步（p<10^{-127}, d=3.35），能量改善超过d=8；而条件风险价值（CVaR）优化则得到负面结果，能量更差（p<10^{-40}, d=1.21），无覆盖度提升。内在验证显示，QAOA优于贪心启发式12.6%，优于随机选择80.1%。结果表明，结构化基准能揭示随机实例中被掩盖的问题感知型QAOA优势。所有代码、数据与实验结果已公开，支持可复现的NISQ算法研究。
原文摘要 · Abstract (English)
The Quantum Approximate Optimization Algorithm (QAOA) is extensively benchmarked on synthetic random instances such as MaxCut, TSP, and SAT problems, but these lack semantic structure and human interpretability, offering limited insight into performance on real-world problems with meaningful constraints. We introduce Quantum King-Ring Domination (QKRD), a NISQ-scale benchmark derived from chess tactical positions that provides 5,000 structured instances with one-hot constraints, spatial locality, and 10--40 qubit scale. The benchmark pairs human-interpretable coverage metrics with intrinsic validation against classical heuristics, enabling algorithmic conclusions without external oracles. Using QKRD, we systematically evaluate QAOA design choices and find that constraint-preserving mixers (XY, domain-wall) converge approximately 13 steps faster than standard mixers (p<10^{-7}, d\approx0.5) while eliminating penalty tuning, warm-start strategies reduce convergence by 45 steps (p<10^{-127}, d=3.35) with energy improvements exceeding d=8, and Conditional Value-at-Risk (CVaR) optimization yields an informative negative result with worse energy (p<10^{-40}, d=1.21) and no coverage benefit. Intrinsic validation shows QAOA outperforms greedy heuristics by 12.6\% and random selection by 80.1\%. Our results demonstrate that structured benchmarks reveal advantages of problem-informed QAOA techniques obscured in random instances. We release all code, data, and experimental artifacts for reproducible NISQ algorithm research.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。