Solving Combinatorial Optimization Problems using the Quantum Approximation Optimization Algorithm

The Quantum Approximation Optimization Algorithm (QAOA) is one of the most promising applications for noisy intermediate-scale quantum machines due to the low number of qubits required as well as the relatively low gate count. Much work has been done on QAOA regarding algorithm implementation and development; less has been done checking how these algorithms actually perform on a real quantum computer. Using the IBM Q Network, several instances of combinatorial optimization problems (the max cut problem and dominating set problem) were implemented into QAOA and analyzed. It was found that only the smallest toy max cut algorithms performed adequately: those that had at most 10 controlled swap gates. The dominating set problem did not work at all as it used many more controlled swap gates than the allowable number. Additionally, a sufficient condition for polynomial implementation in QAOA is shown that generalizes for all combinatorial optimization problems. Finally, further experiments using random circuits also demonstrated that the qubits have a natural tendency to decohere towards the ground state of the system during the lifetime of the algorithm. While unfortunate, these experiments demonstrate the need for better hardware in order for any sort of practical algorithm to be of use