The Expressive Power of Constrained QAOA: What You Might Have MISsed

 A central question in constrained quantum optimization is whether enforcing feasibility throughout the quantum evolution comes at the price of reduced expressiveness. Using Maximum Independent Set, we show that this does not have to be the case. 

We are happy to share our new preprint

Boris Tsvelikhovskiy Bao Bach, Ilya Safro"The Expressive Power of Constrained QAOA: What You Might Have MISsed" https://arxiv.org/abs/2609.18209

Some of the main results: ** Feasibility-preserving multi-angle QAOA can achieve full state controllability within the feasible subspace **  Even standard constrained QAOA, starting from the easily prepared empty set state, can reach an exact optimal MIS state at finite circuit depth ** We introduce a Flip-or-Stay mixer, closely related to the Laplacian of the feasible-state reconfiguration graph ** Surprisingly, two mixers that allow exactly the same transitions between feasible solutions can have dramatically different expressive power ** We also connect expressivity to trainability, showing that in the deep circuit regime the relevant landscape scale is determined by the size of the feasible solution space, rather than the full (2^n)-dimensional Hilbert space.

The broader message is that in constrained QAOA, the set of allowed moves is only part of the story. The structure of the mixer can fundamentally change the dynamics and the states the algorithm can reach.

Comments and feedback are very welcome!

#QuantumComputing #QAOA #QuantumOptimization #QuantumAlgorithms #VariationalQuantumAlgorithms #Optimization