Abstract: The two major bottlenecks of the Quantum Approximate Optimization Algorithm (QAOA) in solving constrained combinatorial optimization problems—its high circuit-layer requirements and its tendency to generate illegal solutions—were taken as the focus, and the maximum-distance-k-matching (MDkM) problem was used as an example to enable the systematic verification of the Quantum Alternating Operator (QAOA+) framework in achieving lower quantum-circuit cost and higher solution accuracy while ensuring solution feasibility. First, the MDkM problem was mapped to its corresponding line graph through a graph-theoretic reduction, and was transformed into a maximum independent set problem that is theoretically easier to handle. Through this transformation, the original problem in the quantum-computing framework was reduced to a classical problem with established quantum-solution frameworks, forming a quantum-modeling path based on graph-structure conversion. Second, mixed Hamiltonians capable of strictly constraining the search process within the feasible subspace were designed, ensuring that all intermediate states and final outputs were kept as legal matchings. Finally, numerical simulations were conducted on graphs of different sizes and types (weighted/unweighted), and differences between QAOA+ and QAOA were systematically compared in fidelity, approximation ratio, and convergence behavior. The experiments show that QAOA+ exhibits significant advantages over standard QAOA even at low circuit depth. When the layer number is p = 1, the fidelity of QAOA+ reaches 92.1%, whereas that of QAOA is only 16%, an improvement of 76.1 percentage points. At p = 9, the fidelity of QAOA+ remains stable at 93.6%, clearly higher than the 70.3% achieved by QAOA at the same depth. In terms of solution quality, QAOA+ yields an average approximation ratio above 90% for unweighted MDkM instances, while in weighted cases the ratio shows notable fluctuations, indicating higher sensitivity to parameter settings. The results confirm the practical potential of quantum algorithms for constrained combinatorial optimization problems and provide methodological guidance for constructing quantum algorithms in weighted settings.

Key words: Quantum Alternating Operator Ansatz (QAOA+), Maximum Distance k-Matching (MDkM), constrained combinatorial optimization, parameterized quantum circuit, Hamiltonian 

摘要： 【目的】针对量子近似优化算法（QAOA）在求解带约束组合优化问题时存在的电路层数需求高、易产生非法解两大瓶颈，本研究以最大距离k匹配（MDkM）问题为实例，系统验证量子交替算子（QAOA+）框架在保证解合法性的前提下，实现更低量子电路成本与更高求解精度的综合性能。【方法】首先，通过图论归约将最大距离k匹配问题映射至对应的线图，转化为理论上更易处理的最大独立集问题。这一转化使得原本在量子计算框架下尚无解的难题，归约为已有成熟量子求解框架的经典问题，从而构建了基于图结构转化的量子建模路径。；其次，设计能够严格约束搜索过程于可行子空间的混合哈密顿量，确保所有中间态与最终输出均为合法匹配；最后，在不同问题规模和类型（加权/无权）的图上进行数值模拟，系统比较QAOA+与QAOA在保真度、近似比与收敛行为方面的差异。【结果】实验结果表明，与标准QAOA相比，QAOA+在低电路层数下即表现出显著优势。当层数p=1时，QAOA+的保真度达92.1%，而QAOA仅为16%，提升幅度达76.1个百分点。在p=9时，QAOA+保真度稳定于93.6%，明显高于QAOA在同等深度下的70.3%。在解质量方面，QAOA+在无权MDkM实例中平均近似比超过90%，但在加权场景中其平均近似比出现显著波动，显示出其对参数设置更为敏感。【结论】本研究验证了量子算法在约束组合优化问题中的实际应用潜力，并为加权场景下量子算法的构建提供了方法参考。

关键词: 量子交替算子, 最大距离k匹配, 约束组合优化问题, 参数化量子电路, 哈密顿量