IEEE Conference on Control Technology and Applications (CCTA)
Constraint-preserving QAOA for multi-agent task allocation
Hyungseop Yu, Sang-Won Kang, Kwang‐Kyo Oh, Hyo‐Sung Ahn
Abstract
We study a constraint-preserving Quantum Approximate Optimization Algorithm (QAOA) for the multi-agent task allocation problem under injective allocation constraints. The allocation cost is encoded into a diagonal cost Hamiltonian derived from the given cost matrix, while feasibility is enforced by a mixer Hamiltonian that restricts transitions along the edges of the feasible-state graph, thereby preventing probability leakage to infeasible allocations. We further provide a graph-theoretic sensitivity bound showing that the mixer unitary’s β-perturbation is bounded by the maximum degree of the feasible-state graph, clarifying how graph connectivity impacts mixing dynamics. Numerical simulations on a toy instance using Qiskit validate that the proposed approach concentrates sampling probability on low-cost feasible allocations.