Counting edge covers of a weighted graph on an ion trap quantum computer

Quantum-classical hybrid schemes, such as the Quantum Approximate Optimization Algorithm (QAOA), are promising approaches to solving combinatorial optimization problems on near-term quantum hardware. Counting edge cover, which is a set of edges that leaves no isolated vertices on a graph, is one of these problems and has important applications in network reliability. We implement a modified QAOA scheme with an adapted mixing Hamiltonian on an ion trap quantum computer to count edge covers of a weighted 3-node star graph. This modified algorithm prepares the quantum system in a superposition of ground states with pre-determined weights for efficient counting. We demonstrate how the approximate solution becomes more exact with increasing number of QAOA-layers on real hardware, despite the additional gate errors.