A Tutorial on Quantum Approximate Optimization Algorithm (QAOA): Fundamentals and Applications

Koudai Shiba

Srikanth Kilaru, Thota Sravya Vardhani, Attluri Udaya Lakshmi +2 more

Alessandro Giovagnoli

The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.

Jaeho Choi, Joongheon Kim

Over the past few years, many researchers around the world have been keen to know the potential and efficiency of quantum computers. The researchers have focused on specific issues that classical computers cannot solve or issues that quantum computers can handle in a better way. Among these various attractive research topics in quantum computers, this paper introduces the Quantum Approximate Optimization Algorithm (QAOA) which guarantees relatively considerable performances in many combinatorial optimization problems. For the comprehensive understanding of QAOA, this paper also describes the approximate optimization, the Quantum Alternating Operator Ansatz, and applications. Besides the theories of QAOA and Quantum Alternating Operator Ansatz, this paper explains the applications of QAOA to major combinatorial optimization problems such as maximum cut (MaxCut) problem and the max-independent set (MIS) problem.

Kostas Blekos, Dean Brand, Andrea Ceschini +4 more

Mingyu Yang, Fang Gao, Guojian Wu +2 more

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.