Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
Generic QAOA struggles with permutation-constrained problems because valid solutions are exponentially rare in the search space. The authors prove this limitation through four analytical bounds, showing a structural ceiling at depth one. They then show that Constraint-Enhanced QAOA (CE-QAOA), which embeds constraints directly into the circuit, achieves an exponential advantage over generic QAOA at depth one and maintains this lead in shallow depths.