Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs
The Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA) uses a shallow quantum circuit to solve constrained optimization problems by operating within an encoded one-hot space. It achieves empirical advantage by realizing unitary 1-designs and approximate second-moment behaviors, leading to finite-shot guarantees and a polynomial-time hybrid quantum-classical solver.