Principles of Quantum Optimization for Constrained Problems
arXiv:2607.14227
The paper develops a spectral framework that links entanglement restructuring to computational slowdown in quantum algorithms for constrained combinatorial optimization, and shows that constraint‑aware dynamics can mitigate this slowdown compared to generic penalty approaches.
Abstract
Constrained combinatorial optimization underlies many industrial and technological decision problems. We develop a spectral theory that unifies many quantum optimization algorithms. We show that computational slowdown is driven by entanglement restructuring: the creation, redistribution, and destruction of entanglement during system evolution. The severity of the slowdown depends on how much entanglement must be changed. We show that algebraic properties of constraints induce such restructuring, and that constraint-aware dynamics reduce the associated slowdown by avoiding unnecessary restructuring. This framework explains why constraint-aware quantum methods can outperform generic penalty-based approaches. The theory connects constrained optimization, computational complexity, entanglement dynamics, and Hamiltonian spectral structure across continuous-time and circuit-based quantum optimization paradigms.