Chapter 5
QAOA: Quantum Approximate Optimization Algorithm

True optimization is the revolutionary contribution of modern research to decision processes.
— George Dantzig

The techniques that we have introduced in the two previous chapters already allow us to solve combinatorial optimization problems on quantum computers. Specifically, we have studied how to write problems using the QUBO formalism and how to use quantum annealers to sample approximate solutions. This is an important approach to quantum optimization, but it is not the only one.

In this chapter, we are going to show how the ideas that we have already explored can also be used on digital quantum computers. We will be using our beloved quantum circuits — with all their qubits, quantum gates, and measurements — to solve combinatorial optimization problems formulated in the QUBO framework.

More concretely, we will be studying the famous Quantum Approximate Optimization Algorithm (QAOA), which is a gate...

5.1 From adiabatic computing to QAOA

In this first section, we will introduce all the theoretical concepts that will allow us to understand QAOA in depth. But before that, we will give an intuitive idea of how QAOA works by studying its relationship with quantum annealing. Sounds interesting? Then keep on reading, because here we go!

5.1.1 Discretizing adiabatic quantum computing

In the previous chapter, we studied adiabatic quantum computing and its practical realization, quantum annealing, and we learned how to use them in order to obtain approximate solutions to combinatorial optimization problems. Both of these techniques relied on the adiabatic theorem. When we applied them, we used a time-dependent Hamiltonian that induced a continuous transformation of the state of a quantum system: from an initial state to a final state that — hopefully — has a big overlap with the solution to our problem.

A natural question to ask is whether there is any sort of analog to this...

5.2 Using QAOA with Qiskit

With everything that we have learned in the previous sections of this chapter and what we already know about Qiskit from Chapter 2, The Tools of the Trade in Quantum Computing, and Section 3.2.2, we could implement our own Qiskit version of QAOA. However, there is no need for that! As we shall show in this section, the Qiskit Optimization package provides all that is necessary to run QAOA on both quantum simulators and actual quantum computers. Moreover, it includes a set of tools to work directly with problems written under the QUBO formalism. As a matter of fact, in this section, we will also see how, underneath the hood, Qiskit uses the very same mathematical concepts that we have been studying.

Let’s start by explaining how to work with QAOA in Qiskit when we already have the problem Hamiltonian.

5.2.1 Using QAOA with Hamiltonians

If we have the Hamiltonian that encodes our optimization problem, it is very easy to use Qiskit’s QAOA implementation...

5.3 Using QAOA with PennyLane

As we mentioned in Chapter 2, The Tools of the Trade in Quantum Computing, PennyLane is a quantum programming library focused mainly on quantum machine learning. As such, it doesn’t include as many tools for quantum optimization algorithms — such as QAOA — as Qiskit does. However, it does provide some interesting features such as automatic differentiation — that is, analytical computation of gradients — that may make it an appealing alternative to Qiskit in some circumstances.

Let’s begin by explaining how to declare and work with Hamiltonians in PennyLane. For that, we will use the Hamiltonian class. It provides a constructor that accepts a list of coefficients and a list of products of Pauli matrices. For instance, if you want to define , you will pass [2,-1,3.5] as the first argument and [PauliZ(0)@PauliZ(1),PauliZ(0)@PauliZ(2),PauliZ(1)] as the second one. As we know from Chapter 2, The Tools of the Trade in...

Summary

In this chapter, you have learned about QAOA, one of the most popular quantum algorithms used to solve optimization problems with gate-based quantum computers. You now know that QAOA is derived as a discretization of quantum annealing and that it is implemented as a hybrid method that uses both a classical and a quantum computer to achieve its goal.

You also understand how to construct circuits for all the operations needed in the quantum part of the algorithm. In particular, you know how to use these circuits to estimate expectation values in an efficient way.

You have also mastered the tools that Qiskit provides in order to implement QAOA instances and to run them on both quantum simulators and quantum computers. You even know how to accelerate the process of running your code on quantum devices by using Qiskit Runtime. And, should you need to use QAOA with PennyLane, you also know how to do it with the help of some predefined utilities and PennyLane capabilities for automatic...