arXiv:2609.18209
The Expressive Power of Constrained QAOA: What You Might Have MISsed
Boris Tsvelikhovskiy, Bao Bach, Ilya Safro
Abstract
Feasibility-preserving mixer Hamiltonians offer an attractive alternative to penalty encodings for constrained quantum optimization, yet how enforcing constraints alters the state space reachable by the Quantum Approximate Optimization Algorithm (QAOA) remains largely unexplored. We address this question within the context of the Maximum Independent Set (MIS) problem. Alongside the standard controlled bit-flip mixer, we analyze the alternative $\mathit{Flip\text{-}or\text{-}Stay}$ mixer, whose restriction to the feasible subspace $W_{\mathcal{F}}$ corresponds precisely to the shifted negative Laplacian of the independent-set reconfiguration graph. Although both mixers induce identical transitions between independent sets, the diagonal modification changes the spectral structure and can substantially enlarge the set of reachable quantum states. For every connected input graph with at least two vertices, we prove that independently parameterized local controls associated with either mixer generate the full unitary Lie algebra on the feasible subspace. Standard QAOA exhibits a more nuanced algebraic structure. We prove that the dynamical Lie algebra associated with MIS-QAOA employing the conventional mixer embeds into its Flip-or-Stay counterpart. Furthermore, we construct an infinite family of graphs for which the corresponding vacuum-state dynamical group orbits exhibit strictly distinct dimensions, establishing a qualitative expressivity separation between the two architectures. For either mixer, we show that standard QAOA initialized in the empty set can prepare a state supported entirely on maximum independent sets at finite depth. For the free architectures, we also derive an exact loss-variance formula in the unitary-design limit, expressed through the number of feasible independent sets and the variance of their cardinalities.
AI Summary
The paper asks how feasibility-preserving mixers affect the states reachable by QAOA for Maximum Independent Set (MIS). It compares the conventional controlled-flip (“Flip-or-Void”) mixer with a “Flip-or-Stay” variant that adds diagonal terms when flips are blocked. On the feasible space $W_{\mathcal F}$, these are respectively the adjacency operator $A_{\mathcal R}$ and shifted negative Laplacian $nI-L_{\mathcal R}$ of the independent-set reconfiguration graph. For every connected graph with $n\ge2$, either mixer with independent local controls generates $\mathfrak u(W_{\mathcal F})$. A global mixer plus local $Z$ controls suffices; standard two-parameter-per-layer QAOA is also fully controllable with positive, pairwise-distinct vertex weights. The proofs isolate transitions through commutators and generate matrix units. For unweighted standard QAOA, the conventional dynamical Lie algebra is contained in the modified one. An explicit family with $n=r(r-1)/2$ has vacuum-state orbit dimension at most $7$ for the conventional mixer versus $3r-2$ for Flip-or-Stay. Both architectures can exactly prepare a state supported on maximum independent sets from the vacuum at finite depth, using dynamical-orbit arguments and adiabatic convergence. For fully controlled circuits forming an exact unitary $2$-design, the loss variance is $4\operatorname{Var}(|S|)/(|\mathcal F|+1)$ for uniformly sampled independent sets $S$, bounded below by $\Omega(|\mathcal F|^{-2})$ and above by $O(\alpha(\Gamma)^2/|\mathcal F|)$. Reachability guarantees are existential, without depth bounds or parameter-finding algorithms. The mixer separation establishes no approximation-ratio advantage, and deep-design concentration results need not describe shallow-circuit trainability.
the authors used OpenAI ChatGPT (GPT-5.6 Sol) to assist in reviewing relevant literature, verifying the correctness of results, and refining the exposition.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.