  Combinatorial optimization is a broadly attractive area for potential quantum
advantage, but no quantum algorithm has yet made the leap. Noise in quantum
hardware remains a challenge, and more sophisticated quantum-classical
algorithms are required to bolster their performance. Here, we introduce an
iterative quantum heuristic optimization algorithm to solve combinatorial
optimization problems. The quantum algorithm reduces to a classical greedy
algorithm in the presence of strong noise. We implement the quantum algorithm
on a programmable superconducting quantum system using up to 72 qubits for
solving paradigmatic Sherrington-Kirkpatrick Ising spin glass problems. We find
the quantum algorithm systematically outperforms its classical greedy
counterpart, signaling a quantum enhancement. Moreover, we observe an absolute
performance comparable with a state-of-the-art semidefinite programming method.
Classical simulations of the algorithm illustrate that a key challenge to
reaching quantum advantage remains improving the quantum device
characteristics.
