  The computational capabilities of near-term quantum computers are limited by
the noisy execution of gate operations and a limited number of physical qubits.
Hybrid variational algorithms are well-suited to near-term quantum devices
because they allow for a wide range of tradeoffs between the amount of quantum
and classical resources used to solve a problem. This paper investigates
tradeoffs available at both the algorithmic and hardware levels by studying a
specific case -- applying the Quantum Approximate Optimization Algorithm (QAOA)
to instances of the Maximum Independent Set (MIS) problem. We consider three
variants of the QAOA which offer different tradeoffs at the algorithmic level
in terms of their required number of classical parameters, quantum gates, and
iterations of classical optimization needed. Since MIS is a constrained
combinatorial optimization problem, the QAOA must respect the problem
constraints. This can be accomplished by using many multi-controlled gate
operations which must be decomposed into gates executable by the target
hardware. We study the tradeoffs available at this hardware level, combining
the gate fidelities and decomposition efficiencies of different native gate
sets into a single metric called the \textit{gate decomposition cost}.
