Quantum Algorithms #1: QAOA

Algorithms blog series introduction

Welcome to the QLL algorithms blog series, where we explore some of the most practical and exciting algorithms driving today’s quantum computing revolution! The goal is that by the end of the series we will have explored the computational nature of these crucial algorithms and get a feel for how they operate. Each blog will go through the problem these algorithms solve, simplify how they solve it, and what an industry application of it could look like. 

QAOA Introduction

Among the many algorithms to be explored in quantum computing stands the Quantum Approximate Optimization Algorithm (QAOA), which stands out as one of the most recognized optimization algorithms. It is used across different quantum computers with different qubit technologies - from D-Wave’s computers which work with quantum annealing to IBM’s gate-based computers. More importantly, what it solves (optimization problems), is a type of problem seen in everyday life across countless industries. So here’s what it does:

The problem

QAOA solves optimization problems, meaning that it finds an optimal (or near optimal) solution which maximizes a desired outcome under specific constraints. For example, in a combinatorial optimization problem we might want to select the best combination of items that maximizes a certain value without exceeding a limit. A classic example is the knapsack problem - where we may have a set of items with their respective costs and their respective weights - and we aim to put the combination of these items in a bag that gives us the highest total cost without crossing a certain weight limit. 

These problems are exponentially difficult for classical computers, meaning that with a larger number of items, the computation time increases rapidly. 

How QAOA works

To start, QAOA is set up by turning the problem into a Hamiltonian - a mathematical object representing the energy of a system - that needs to be minimized. That is, if we would like to maximize the value of the items in the bag, we may write this down mathematically, add a negative sign to make sure we are minimizing, and change a few variables so they can be represented by spin -1 and spin +1 (instead of 0 and 1). The final state of the system with the minimum energy (Hamiltonian) encodes the solution to the problem. 

Once we have the Hamiltonian that needs to be minimized - we need to program the QPU to minimize it. This process works differently on the different types of computers - but the general idea is constant. QAOA belongs to a type of quantum algorithm called variational quantum algorithms (VQA) - where a set of parameters that define the solution become optimized iteratively by the algorithm. QAOA builds on the adiabatic theorem — the idea that if we change a system’s parameters slowly enough, it will stay in its lowest-energy (ground) state, which corresponds to our optimal solution. 

Problem Hamiltonian operations/functions that encode the function we want to minimize. 

Mixing Hamiltonian operations/functions that allow the QPU to explore different solutions and not get stuck in a local minimum

QAOA Cost (problem) and Mixing operations in a gate based quantum computer. (Mathworks, 2025)

Gate based computers apply these operations consecutively with a set of parameters and in the end measure the system to find an optimal solution state. On a quantum annealer, the Hamiltonian is given as a sum of these two as functions that change over time. And once again, the final state of this system - having gone through the operations - will encode the solution to the problem.

Where this can be used

Optimization and combinatorial problems are found across a myriad of industries. Take for example an airport with limited gates trying to optimize the take-off and landing times of multiple airplanes to make sure everyone gets to their destination as quickly as possible. Alternatively, take an energy grid management facility trying to minimize the loss of energy while ensuring everyone gets their electricity when they need it. All these problems - and more - can be translated into a Hamiltonian solved by our quantum computers!

If you’re interested in finding out more and would like to get your hands dirty with some real code, check these links from IBM and Dwave out!