  Quantum algorithms have been widely studied in the context of combinatorial
optimization problems. While this endeavor can often analytically and
practically achieve quadratic speedups, theoretical and numeric studies remain
limited, especially compared to the study of classical algorithms. We propose
and study a new class of hybrid approaches to quantum optimization, termed
Iterative Quantum Algorithms, which in particular generalizes the Recursive
Quantum Approximate Optimization Algorithm. This paradigm can incorporate hard
problem constraints, which we demonstrate by considering the Maximum
Independent Set (MIS) problem. We show that, for QAOA with depth $p=1$, this
algorithm performs exactly the same operations and selections as the classical
greedy algorithm for MIS. We then turn to deeper $p>1$ circuits and other ways
to modify the quantum algorithm that can no longer be easily mimicked by
classical algorithms, and empirically confirm improved performance. Our work
demonstrates the practical importance of incorporating proven classical
techniques into more effective hybrid quantum-classical algorithms.
