QAOA: a quantum approach to optimisation problems

Learn QAOA, the algorithm that turns optimisation problems such as splitting a network into two groups in the best way into a quantum circuit, through the MaxCut example, and find its angles with Qiskit.

Optimisation and MaxCut

Planning routes in logistics, choosing a portfolio in finance, splitting a network in the best way: all of these are problems of finding the best among a huge number of options. Because the number of options grows exponentially with the problem, many of them are hard for classical computers too.

MaxCut is the best-known example: split the nodes of a graph into two groups so that as many edges as possible have their two ends in different groups. Each node gets a qubit; 0 marks one group and 1 the other. With two nodes and a single edge between them, the best cuts are 01 and 10.

Cost and mixer layers

Each edge is scored with the ZZ observable you met in the Qiskit course: if the two bits differ, ZZ = −1; if they are the same, +1. So lowering ZZ means cutting the edge. QAOA starts from an equal superposition of all cuts and applies two layers in turn.

The cost layer is an rzz gate with angle γ for each edge and shifts the phase of good cuts. The mixer layer is an rx gate with angle β on each qubit and turns these phases into probabilities through interference. A classical optimiser chooses γ and β, just as in VQE.

import numpy as np
from qiskit import QuantumCircuit
from qiskit.circuit import Parameter
from qiskit.quantum_info import Statevector

gamma, beta = Parameter('gamma'), Parameter('beta')
qc = QuantumCircuit(2)
qc.h([0, 1])                 # equal superposition of all cuts
qc.rzz(2 * gamma, 0, 1)      # cost layer: ZZ for the edge
qc.rx(2 * beta, [0, 1])      # mixer layer

best = (0, 0, 0)
for g in np.linspace(0, np.pi, 25):
    for b in np.linspace(0, np.pi, 25):
        p = Statevector(qc.assign_parameters({gamma: g, beta: b})).probabilities_dict()
        cut = p.get('01', 0) + p.get('10', 0)
        if cut > best[0]:
            best = (cut, g, b)
print(best)   # about (1.0, 0.785, 1.178): γ = π/4, β = 3π/8

Number of layers and real problems

In this small single-edge example a single layer (p = 1) finds the best cut with 100% probability. In large graphs one layer is usually not enough; as the number of layers p grows QAOA gets closer to the best answer, but the circuit also gets longer and the noise grows.

QAOA was proposed in 2014 and is the optimisation algorithm tried most often on today’s devices. Still, it has not yet been shown to beat the best classical methods on large, real problems; this is an active research topic.

Try it yourself

This circuit gives the two best cuts of the two-node graph, 01 and 10, with equal probability; this is the result a well-tuned QAOA aims for. Remove the X gate on q1: the results become 00 and 11, so the nodes always land in the same group and the edge is never cut.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

In MaxCut each node is a qubit; ZZ = −1 for every edge that is cut.
QAOA starts from an equal superposition and applies cost (rzz) and mixer (rx) layers in turn.
A classical optimiser chooses the angles γ and β; the result improves as the number of layers grows.
Its advantage over classical methods on large problems has not yet been proven.

Test yourself

In a graph with two nodes and one edge between them, which are the best cuts?

00 and 11
01 and 10
Only 11

Show the answer

01 and 10. For the edge to be cut the two nodes must be in different groups: 01 or 10.

← VQE: finding the lowest energy of a molecule · Quantum walks: the quantum version of a random walk →