Solving Combinatorial Optimization Problems using the Quantum Approximation Optimization Algorithm
Technical Report,01 Aug 2018,01 Mar 2020
AIR FORCE INSTITUTE OF TECHNOLOGY WRIGHT-PATTERSON AFB OH WRIGHT-PATTERSON AFB United States
Pagination or Media Count:
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 anv sort of practical algorithm to be of use.
- Quantum Theory and Relativity
- Operations Research