What Is The Quantum Approximate Optimization Algorithm (QAOA)?

Introduction to Quantum Computing

Quantum Approximate Optimization Algorithm

Quantum Approximate Optimization Algorithm (QAOA) is an algorithm used to solve optimization problems.  Optimization problems focus on finding the best solution to a problem (given various constraints and objectives) from a set of possible solutions.  So, combinatorial optimization algorithm finds solutions to a specific problem subject to a set of various constraints. Then, the optimal solution becomes the solution that satisfies the largest number of constraints.  Typical optimization problems include the "travelling salesman problem", the "minimum spanning tree" problem, and the "knapsack" problem.

The QAOA relies on the use of unitary operators.  These operators are iteratively applied on a state that is an equal-weighted quantum superposition of all the possible states. In each iteration, the state is measured and C(z) is calculated. C(z) is the representation of the combinatorial optimization problem.  The problem is to find an optimal object from a finite set of objects where the set of feasible solutions is discrete.  Said differently, the problem can be stated as maximizing an objective function.  

After a sufficient number of repetitions, the value of  C(z) is almost optimal and the state being measured is close to being optimal as well.

QAOA exhibits a strong dependence on the ratio of a problem's constraint to variables (i.e. problem density) placing a limiting restriction on the algorithm's capacity to minimize a corresponding objective function.