  Combinatorial optimization problems on graphs have broad applications in
science and engineering. The Quantum Approximate Optimization Algorithm (QAOA)
is a method to solve these problems on a quantum computer by applying multiple
rounds of variational circuits. However, there exist several challenges
limiting the real-world applications of QAOA. In this paper, we demonstrate on
a trapped-ion quantum computer that QAOA results improve with the number of
rounds for multiple problems on several arbitrary graphs. We also demonstrate
an advanced mixing Hamiltonian that allows sampling of all optimal solutions
with predetermined weights. Our results are a step towards applying quantum
algorithms to real-world problems.
