  Combinatorial optimization is a challenging problem applicable in a wide
range of fields from logistics to finance. Recently, quantum computing has been
used to attempt to solve these problems using a range of algorithms, including
parameterized quantum circuits, adiabatic protocols, and quantum annealing.
These solutions typically have several challenges: 1) there is little to no
performance gain over classical methods, 2) not all constraints and objectives
may be efficiently encoded in the quantum ansatz, and 3) the solution domain of
the objective function may not be the same as the bit strings of measurement
outcomes. This work presents "non-native hybrid algorithms" (NNHA): a framework
to overcome these challenges by integrating quantum and classical resources
with a hybrid approach. By designing non-native quantum variational ansatzes
that inherit some but not all problem structure, measurement outcomes from the
quantum computer can act as a resource to be used by classical routines to
indirectly compute optimal solutions, partially overcoming the challenges of
contemporary quantum optimization approaches. These methods are demonstrated
using a publicly available neutral-atom quantum computer on two simple problems
of Max $k$-Cut and maximum independent set. We find improvements in solution
quality when comparing the hybrid algorithm to its ``no quantum" version, a
demonstration of a "comparative advantage".
