This work investigates the role of mixer Hamiltonians in variational quantum algorithms for constrained combinatorial optimization, using the minimum s-t cut problem as a diagnostic benchmark. Several formulations are implemented and compared, including a constraint-preserving QAOA model using a ring mixer, an ancilla-based encoding that seeks to remove nonlinear aggregation terms, and a vertex-partition QUBO approach for quantum annealing.

Experiments are conducted on synthetic graphs and network instances from the Network Topology Zoo, evaluating qubit requirements, circuit depth, and convergence behavior across formulations.

Beyond performance comparison, the objective is to extract design principles for quantum optimization models and to identify which encoding properties remain stable when transitioning from polynomial solvable problems to NP-hard variants such as multicut and interdiction, as well as to explore quantum manifestations of classical dualities such as min-cut/max-flow.

The results indicate that mixer choice significantly influences training stability and that feasibility-preserving dynamics lead to more consistent optimization behavior than penalty-based constructions. Warm-start strategies further reduce variance and accelerate convergence when used with structured mixers with cost of either an overhead in the Hamiltonian cost formulation or suffering local minima for some intial states requiring further investigation.