A Tutorial on Quantum Approximate Optimization Algorithm for Maximum Independent Set Problem

In the past few years, quantum computers and quantum algorithms have shown advantages compared to their classical counterparts. In combinatorial optimization problems, quantum approximate optimization algorithm(QAOA) has good performance. This paper focuses on the application of QAOA to one combinational problem called maximum independent set(MIS). Two different Hamiltonian construction methods are employed in this algorithm using IBM Qiskit. It is shown that the key is to design proper Hamiltonians to map the solution to the feasible states of the Hilbert space.