The Quantum Approximate Optimization Algorithm from the Ground Up

Source

Introduction

In recent years, the advent of quantum computing has brought great excitement within numerous research communities (e.g., physics, computer science, mathematics, etc.). Interest in the topic of quantum computing led to numerous theoretical contributions in the space, catalyzing the development of influential algorithms such as Grover’s search, Shor’s algorithm, adiabatic optimization, and many more. Despite these theoretical demonstrations of quantum supremacy and usefulness, such algorithms go beyond the current reality of quantum hardware, utilizing an excessive circuit depth and number of qubits. As of now, such requirements are unrealizable within a physical system.

Currently, quantum computing is said to exist within the Noisy Intermediate-Scale Quantum (NISQ) era, in which hardware is limited in the number of available qubits and circuit depth is limited by increasing noise that arises within a quantum system. As such, many of the most eminent quantum algorithms (such as those mentioned above) have limited practical applications, leading researchers to focus on the development of NISQ-friendly quantum algorithms. Two of the most widely-studied algorithms in this space are the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA), which are…