Solving Combinatorial Optimization Problems using the Quantum Approximation Optimization Algorithm

Hua-Pei Chiang, Yao–Hsin Chou, Chia-Hui Chiu +2 more

Moises Ponce, Rebekah Herrman, Phillip C. Lotshaw +4 more

Yue Ruan, S. Marsh, Xilin Xue +3 more

The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the context of QAOA or QAA, one needs to find a way to encode problem constraints into the scheme. In this paper, we formalize different constraint types to linear equalities, linear inequalities, and arbitrary form. Based on this, we propose constraint-encoding schemes well-fitting into the QAOA framework for solving NP combinatorial optimization problems. The implemented algorithms demonstrate the effectiveness and efficiency of the proposed scheme by the testing results of varied instances of some well-known NP optimization problems. We argue that our work leads to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to combinatorial problems with various types of constraints.

Yue Ruan, Zhiqiang Yuan, Xiling Xue +1 more

Yunpyo Hong, Jaejoon Gill, Daeyeun Kim +3 more

Pontus Vikstål

This licentiate thesis is an extended introduction to the accompanying papers, which encompass a study of the quantum approximate optimization algorithm (QAOA). It is a hybrid quantum-classical algorithm for solving combinatorial optimization problems and is a promising algorithm to run on near term quantum devices. In this thesis, we will introduce the workings of the QAOA, together with some applications of it on combinatorial optimization problems.