Abstract
This thesis, presented as a collection of four papers, develops quantum algorithms for combinatorial constraint optimization, together with the circuit synthesis tools needed to implement them on near-term hardware. The central theme is that enforcing of constraints in optimization problems by construction, rather than through penalty terms. The first paper introduces a systematic framework for constructing QAOA mixers restricted to arbitrary feasible subspaces via the stabilizer formalism, while the second develops circuit synthesis techniques for sparse operators that provide the compilation primitives for such constraint-preserving dynamics. Building on these synthesis methods, the third paper proposes an efficient qubit encoding of the Max-k-Cut problem that reduces hardware requirements while preserving the problem structure. The final paper proposes an iterative quantum algorithm based on a continuous-time quantum walk on the feasible subspace of the Minimum Vertex Cover problem, combined with a greedy iterative reduction scheme in which local quantum observables encode nonlocal graph information, yielding a penaltyfree, non-variational hybrid algorithm that outperforms classical greedy baselines already at shallow depth.