Skip to content

Solving MaxCut with QAOA

This tutorial shows how to solve the maximum cut (MaxCut) combinatorial optimization problem on a graph using the Quantum Approximate Optimization Algorithm (QAOA), first introduced by Farhi et al. in 2014 1.

Given an arbitrary graph, the MaxCut problem consists in finding a graph cut which partitions the nodes into two disjoint sets, such that the number of edges in the cut is maximized. This is a very common combinatorial optimization problem known to be computationally hard (NP-hard).

The graph used for this tutorial is an unweighted graph randomly generated using the networkx library with a certain probability \(p\) of having an edge between two arbitrary nodes (known as Erdős–Rényi graph).

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import random

# ensure reproducibility
seed = 42
np.random.seed(seed)
random.seed(seed)

# Create random graph
n_nodes = 4
edge_prob = 0.8
graph = nx.gnp_random_graph(n_nodes, edge_prob)

nx.draw(graph)
2025-06-04T09:58:33.680175 image/svg+xml Matplotlib v3.10.3, https://matplotlib.org/

The goal of the MaxCut algorithm is to maximize the following cost function:

\[\mathcal{C}(p) = \sum_{\alpha}^m \mathcal{C}_{\alpha}(p)\]

where \(p\) is a given cut of the graph, \(\alpha\) is an index over the edges and \(\mathcal{C}_{\alpha}(p)\) is written such that if the nodes connected by the \(\alpha\) edge are in the same set, it returns \(0\), otherwise it returns \(1\). We will represent a cut \(p\) as a bitstring of length \(N\), where \(N\) is the number of nodes, and where the bit in position \(i\) shows to which partition node \(i\) belongs. We assign value 0 to one of the partitions defined by the cut and 1 to the other. Since this choice is arbitrary, every cut is represented by two bitstrings, e.g. "0011" and "1100" are equivalent.

Since in this tutorial we are only dealing with small graphs, we can find the maximum cut by brute force to make sure QAOA works as intended.

# Function to calculate the cost associated with a cut
def calculate_cost(cut: str, graph: nx.graph) -> float:
    """Returns the cost of a given cut (represented by a bitstring)"""
    cost = 0
    for edge in graph.edges():
        (i, j) = edge
        if cut[i] != cut[j]:
            cost += 1
    return cost


# Function to get a binary representation of an int
get_binary = lambda x, n: format(x, "b").zfill(n)

# List of all possible cuts
all_possible_cuts = [bin(k)[2:].rjust(n_nodes, "0") for k in range(2**n_nodes)]

# List with the costs associated to each cut
all_costs = [calculate_cost(cut, graph) for cut in all_possible_cuts]

# Get the maximum cost
maxcost = max(all_costs)

# Get all cuts that correspond to the maximum cost
maxcuts = [get_binary(i, n_nodes) for i, j in enumerate(all_costs) if j == maxcost]
print(f"The maximum cut is represented by the bitstrings {maxcuts}, with a cost of {maxcost}")
The maximum cut is represented by the bitstrings ['0011', '0101', '0110', '1001', '1010', '1100'], with a cost of 4

The QAOA quantum circuit

The Max-Cut problem can be solved by using the QAOA algorithm. QAOA belongs to the class of Variational Quantum Algorithms (VQAs), which means that its quantum circuit contains a certain number of parametrized quantum gates that need to be optimized with a classical optimizer. The QAOA circuit is composed of two operators:

  • The cost operator \(U_c\): a circuit generated by the cost Hamiltonian which encodes the cost function described above into a quantum circuit. The solution to the optimization problem is encoded in the ground state of the cost Hamiltonian \(H_c\). The cost operator is simply the evolution of the cost Hamiltonian parametrized by a variational parameter \(\gamma\) so that \(U_c = e^{i\gamma H_c}.\)
  • The mixing operator \(U_b\): a simple set of single-qubit rotations with adjustable angles which are tuned during the classical optimization loop to minimize the cost

The cost Hamiltonian of the MaxCut problem can be written as:

\[H_c = \frac12 \sum_{\langle i,j\rangle} (\mathbb{1} - Z_iZ_j)\]

where \(\langle i,j\rangle\) represents the edge between nodes \(i\) and \(j\). The solution of the MaxCut problem is encoded in the ground state of the above Hamiltonian.

The QAOA quantum circuit consists of a number of layers, each layer containing a cost and a mixing operator. Below, the QAOA quantum circuit is defined using qadence operations. First, a layer of Hadamard gates is applied to all qubits to prepare the initial state \(|+\rangle ^{\otimes n}\). The cost operator of each layer can be built "manually", implementing the \(e^{iZZ\gamma}\) terms with CNOTs and a \(\rm{RZ}(2\gamma)\) rotation, or it can also be automatically decomposed into digital single and two-qubits operations via the .digital_decomposition() method. The decomposition is exact since the Hamiltonian generator is diagonal.

from qadence import tag, kron, chain, RX, RZ, Z, H, CNOT, I, add
from qadence import HamEvo, QuantumCircuit, Parameter

n_qubits = graph.number_of_nodes()
n_edges = graph.number_of_edges()
n_layers = 6

# Generate the cost Hamiltonian
zz_ops = add(Z(edge[0]) @ Z(edge[1]) for edge in graph.edges)
cost_ham = 0.5 * (n_edges * kron(I(i) for i in range(n_qubits)) - zz_ops)


# QAOA circuit
def build_qaoa_circuit(n_qubits, n_layers, graph):
    layers = []
    # Layer of Hadamards
    initial_layer = kron(H(i) for i in range(n_qubits))
    layers.append(initial_layer)
    for layer in range(n_layers):

        # cost layer with digital decomposition
        # cost_layer = HamEvo(cost_ham, f"g{layer}").digital_decomposition(approximation="basic")
        cost_layer = []
        for edge in graph.edges():
            (q0, q1) = edge
            zz_term = chain(
                CNOT(q0, q1),
                RZ(q1, Parameter(f"g{layer}")),
                CNOT(q0, q1),
            )
            cost_layer.append(zz_term)
        cost_layer = chain(*cost_layer)
        cost_layer = tag(cost_layer, "cost")

        # mixing layer with single qubit rotations
        mixing_layer = kron(RX(i, f"b{layer}") for i in range(n_qubits))
        mixing_layer = tag(mixing_layer, "mixing")

        # putting all together in a single ChainBlock
        layers.append(chain(cost_layer, mixing_layer))

    final_b = chain(*layers)
    return QuantumCircuit(n_qubits, final_b)


circuit = build_qaoa_circuit(n_qubits, n_layers, graph)

# Print a single layer of the circuit
%3 cluster_48a9feca2d8c4b02a587005e321ac870 mixing cluster_e60a60975a134f77a63c184ab8e6e80c cost d3ad6f223c474b5db8760d76dbef8dac 0 644ef42dcdc045b4bfea639dc5bfcb37 H d3ad6f223c474b5db8760d76dbef8dac--644ef42dcdc045b4bfea639dc5bfcb37 b14f4a4cac1f464a8882236570214a54 1 04045ac4c4e148c6a3bdb34480df4c08 644ef42dcdc045b4bfea639dc5bfcb37--04045ac4c4e148c6a3bdb34480df4c08 b122b3a4a607427fb16c0a5f6ecb2518 04045ac4c4e148c6a3bdb34480df4c08--b122b3a4a607427fb16c0a5f6ecb2518 c7acbea3d06346be9c7bc9c4adf2163c b122b3a4a607427fb16c0a5f6ecb2518--c7acbea3d06346be9c7bc9c4adf2163c 5dee34cff76a42b1a5e4a4c3bd074ef5 c7acbea3d06346be9c7bc9c4adf2163c--5dee34cff76a42b1a5e4a4c3bd074ef5 2167644d52de4365ba07ca313f3b612b 5dee34cff76a42b1a5e4a4c3bd074ef5--2167644d52de4365ba07ca313f3b612b 6ff20fe178434192ad37972020adb139 2167644d52de4365ba07ca313f3b612b--6ff20fe178434192ad37972020adb139 6fab782198754555aa65da74834de6e0 6ff20fe178434192ad37972020adb139--6fab782198754555aa65da74834de6e0 11dd7c92479942769400d6e9d21e3250 6fab782198754555aa65da74834de6e0--11dd7c92479942769400d6e9d21e3250 44603d02896140ddb54f1752b5a9dd47 11dd7c92479942769400d6e9d21e3250--44603d02896140ddb54f1752b5a9dd47 d9e1a256b9024d08a9b39c644725299f 44603d02896140ddb54f1752b5a9dd47--d9e1a256b9024d08a9b39c644725299f 3ab4dc21f2164e9da3aa7b08a0182e5b d9e1a256b9024d08a9b39c644725299f--3ab4dc21f2164e9da3aa7b08a0182e5b 76d6ad51f6d841e0b034e83343511204 3ab4dc21f2164e9da3aa7b08a0182e5b--76d6ad51f6d841e0b034e83343511204 a0ae64b8932549cd9ccdd9f42f32d1da 76d6ad51f6d841e0b034e83343511204--a0ae64b8932549cd9ccdd9f42f32d1da f23305a2d51c447baf315d1cb5eea765 a0ae64b8932549cd9ccdd9f42f32d1da--f23305a2d51c447baf315d1cb5eea765 753f25494c164404833d45ba70e5654e f23305a2d51c447baf315d1cb5eea765--753f25494c164404833d45ba70e5654e 4c5fce294c074df3ae358a9d5f4a6022 753f25494c164404833d45ba70e5654e--4c5fce294c074df3ae358a9d5f4a6022 b23f7548dd53474babc44fe89be0dde6 4c5fce294c074df3ae358a9d5f4a6022--b23f7548dd53474babc44fe89be0dde6 538e3e85c8ce4b8789cee3f1dcd9f2f7 b23f7548dd53474babc44fe89be0dde6--538e3e85c8ce4b8789cee3f1dcd9f2f7 f5ce651e3f01424c9988c9e225e52105 RX(b0) 538e3e85c8ce4b8789cee3f1dcd9f2f7--f5ce651e3f01424c9988c9e225e52105 ce9f9c026f42463a94abcbe43b74a0ce f5ce651e3f01424c9988c9e225e52105--ce9f9c026f42463a94abcbe43b74a0ce 2c3113c86c0d4a3ca7eab65502025685 2a3b147af87d4f1cbcdd4b5957230082 H b14f4a4cac1f464a8882236570214a54--2a3b147af87d4f1cbcdd4b5957230082 32e31599c5b14c0ab16a588b69d7b75a 2 7d78dae0154148d48ea1fd5ed111994f X 2a3b147af87d4f1cbcdd4b5957230082--7d78dae0154148d48ea1fd5ed111994f 7d78dae0154148d48ea1fd5ed111994f--04045ac4c4e148c6a3bdb34480df4c08 c0f8916c7e464bd481537b735d3ced54 RZ(g0) 7d78dae0154148d48ea1fd5ed111994f--c0f8916c7e464bd481537b735d3ced54 b7e4b8af3ba74c559e5e8a6a1c1d0add X c0f8916c7e464bd481537b735d3ced54--b7e4b8af3ba74c559e5e8a6a1c1d0add b7e4b8af3ba74c559e5e8a6a1c1d0add--c7acbea3d06346be9c7bc9c4adf2163c a88f3d0ba6b142dc9b8654049c8f4819 b7e4b8af3ba74c559e5e8a6a1c1d0add--a88f3d0ba6b142dc9b8654049c8f4819 528749bc79914640a3e753718d169cfd a88f3d0ba6b142dc9b8654049c8f4819--528749bc79914640a3e753718d169cfd 85f81348098648228c448075b6c5e55a 528749bc79914640a3e753718d169cfd--85f81348098648228c448075b6c5e55a 1f9f05ec56634d8bb270253126d360a5 85f81348098648228c448075b6c5e55a--1f9f05ec56634d8bb270253126d360a5 c519c9ee62f643ad84ff9d53587dc250 1f9f05ec56634d8bb270253126d360a5--c519c9ee62f643ad84ff9d53587dc250 b30d335ad5fd4f6baa1e0e5e55c69488 c519c9ee62f643ad84ff9d53587dc250--b30d335ad5fd4f6baa1e0e5e55c69488 1850fce9ce774a86ad05e59940abb267 b30d335ad5fd4f6baa1e0e5e55c69488--1850fce9ce774a86ad05e59940abb267 39db0d906c96478b8145737f21d145e7 1850fce9ce774a86ad05e59940abb267--39db0d906c96478b8145737f21d145e7 6d4308847617449385b35fdda29364f6 39db0d906c96478b8145737f21d145e7--6d4308847617449385b35fdda29364f6 55094006b25b42a8bd2c6413d8a35a8d 6d4308847617449385b35fdda29364f6--55094006b25b42a8bd2c6413d8a35a8d b7c87c43caba4364bc2a52da36c656b1 55094006b25b42a8bd2c6413d8a35a8d--b7c87c43caba4364bc2a52da36c656b1 547972a9d69b405ebec31ed13349c7c9 b7c87c43caba4364bc2a52da36c656b1--547972a9d69b405ebec31ed13349c7c9 ca581f32ae3b4905bebcdab551c7dd28 547972a9d69b405ebec31ed13349c7c9--ca581f32ae3b4905bebcdab551c7dd28 3155c3b1df644c9998c08866c7c1c9a9 ca581f32ae3b4905bebcdab551c7dd28--3155c3b1df644c9998c08866c7c1c9a9 8d7b2d0974e74757a9ebffbd158d8267 3155c3b1df644c9998c08866c7c1c9a9--8d7b2d0974e74757a9ebffbd158d8267 d337980a420d400d83d1b41b97f5ee4b RX(b0) 8d7b2d0974e74757a9ebffbd158d8267--d337980a420d400d83d1b41b97f5ee4b d337980a420d400d83d1b41b97f5ee4b--2c3113c86c0d4a3ca7eab65502025685 418b09fd5a054aea8ed6e231fec16cb4 1b5ad9cd3ac74d62b9a18729fb9436b1 H 32e31599c5b14c0ab16a588b69d7b75a--1b5ad9cd3ac74d62b9a18729fb9436b1 b478f5874bb64d6aaf020bb7af456388 3 6c7d70e7fba54961b7e63db31c8ccb77 1b5ad9cd3ac74d62b9a18729fb9436b1--6c7d70e7fba54961b7e63db31c8ccb77 a8f768103c834d1ab9d9160692f3d393 6c7d70e7fba54961b7e63db31c8ccb77--a8f768103c834d1ab9d9160692f3d393 31e9982767bc4e87add2bb685c5a8126 a8f768103c834d1ab9d9160692f3d393--31e9982767bc4e87add2bb685c5a8126 bd662cf36a96428493465ca320b124a7 X 31e9982767bc4e87add2bb685c5a8126--bd662cf36a96428493465ca320b124a7 bd662cf36a96428493465ca320b124a7--5dee34cff76a42b1a5e4a4c3bd074ef5 047e9a819576470481f2b89cbd677eb9 RZ(g0) bd662cf36a96428493465ca320b124a7--047e9a819576470481f2b89cbd677eb9 5961eb4c2034460486e159ef9c413522 X 047e9a819576470481f2b89cbd677eb9--5961eb4c2034460486e159ef9c413522 5961eb4c2034460486e159ef9c413522--6ff20fe178434192ad37972020adb139 2bf6a9a7cfe84c86aceb3c890cda19b0 5961eb4c2034460486e159ef9c413522--2bf6a9a7cfe84c86aceb3c890cda19b0 8885b487327f48889cefb80bbd2472f8 2bf6a9a7cfe84c86aceb3c890cda19b0--8885b487327f48889cefb80bbd2472f8 567ab61a632d459d9edc4d7075dcec21 8885b487327f48889cefb80bbd2472f8--567ab61a632d459d9edc4d7075dcec21 410abbce98b44e5982610d8e3018e8be X 567ab61a632d459d9edc4d7075dcec21--410abbce98b44e5982610d8e3018e8be 410abbce98b44e5982610d8e3018e8be--1850fce9ce774a86ad05e59940abb267 e0df7533e16c40d8a7cb5d256ecf8c35 RZ(g0) 410abbce98b44e5982610d8e3018e8be--e0df7533e16c40d8a7cb5d256ecf8c35 f8ecf3f508dd49eb8fd6bba3c365a20f X e0df7533e16c40d8a7cb5d256ecf8c35--f8ecf3f508dd49eb8fd6bba3c365a20f f8ecf3f508dd49eb8fd6bba3c365a20f--6d4308847617449385b35fdda29364f6 0d7482aa724044a0ae55678852b75fbb f8ecf3f508dd49eb8fd6bba3c365a20f--0d7482aa724044a0ae55678852b75fbb 230450758fbe4366ae9f6c6ce6a522cd 0d7482aa724044a0ae55678852b75fbb--230450758fbe4366ae9f6c6ce6a522cd 6f7336d2a06947abb5dbd20f4393d404 230450758fbe4366ae9f6c6ce6a522cd--6f7336d2a06947abb5dbd20f4393d404 908c1671c7a64c52b649922542b38eeb 6f7336d2a06947abb5dbd20f4393d404--908c1671c7a64c52b649922542b38eeb 90898fd382504d3a8faaac23be51a05b 908c1671c7a64c52b649922542b38eeb--90898fd382504d3a8faaac23be51a05b d3909bb43f2045c0b13b8bf53f3dc6a7 90898fd382504d3a8faaac23be51a05b--d3909bb43f2045c0b13b8bf53f3dc6a7 da44a6e425d941f28a831fabf6b01f85 RX(b0) d3909bb43f2045c0b13b8bf53f3dc6a7--da44a6e425d941f28a831fabf6b01f85 da44a6e425d941f28a831fabf6b01f85--418b09fd5a054aea8ed6e231fec16cb4 b50fe954cfa74efb98be4749eea15e78 f290f4b67a954978af34da378e1a3c0f H b478f5874bb64d6aaf020bb7af456388--f290f4b67a954978af34da378e1a3c0f 48b81ddba3b94a529a25caa8887e9066 f290f4b67a954978af34da378e1a3c0f--48b81ddba3b94a529a25caa8887e9066 6bdfa332578d496db90d0b1467a573ea 48b81ddba3b94a529a25caa8887e9066--6bdfa332578d496db90d0b1467a573ea 99451f28f621403e9e2aead1801d41ea 6bdfa332578d496db90d0b1467a573ea--99451f28f621403e9e2aead1801d41ea b74285ddd05a42d3be75132eb8f4768e 99451f28f621403e9e2aead1801d41ea--b74285ddd05a42d3be75132eb8f4768e 35f5f38f49f44613b053e20a1693e2cb b74285ddd05a42d3be75132eb8f4768e--35f5f38f49f44613b053e20a1693e2cb 3ef2a2e951164d51bb1eb525b59ef619 35f5f38f49f44613b053e20a1693e2cb--3ef2a2e951164d51bb1eb525b59ef619 a0dc967127a946c290e6d4ebdc0b576a X 3ef2a2e951164d51bb1eb525b59ef619--a0dc967127a946c290e6d4ebdc0b576a a0dc967127a946c290e6d4ebdc0b576a--6fab782198754555aa65da74834de6e0 eb326809b562442a9f80bad25335f438 RZ(g0) a0dc967127a946c290e6d4ebdc0b576a--eb326809b562442a9f80bad25335f438 2a834e320e64402fabafedb402c6fe28 X eb326809b562442a9f80bad25335f438--2a834e320e64402fabafedb402c6fe28 2a834e320e64402fabafedb402c6fe28--44603d02896140ddb54f1752b5a9dd47 a796430e6cf740a594c9f115e82873a3 2a834e320e64402fabafedb402c6fe28--a796430e6cf740a594c9f115e82873a3 635c3dfc89284b8791ff50ad942abbad a796430e6cf740a594c9f115e82873a3--635c3dfc89284b8791ff50ad942abbad fb1aa35359e14f24825722aed0854cf4 635c3dfc89284b8791ff50ad942abbad--fb1aa35359e14f24825722aed0854cf4 5aeabfb3708b4b10b5f352c0e8c50a0b X fb1aa35359e14f24825722aed0854cf4--5aeabfb3708b4b10b5f352c0e8c50a0b 5aeabfb3708b4b10b5f352c0e8c50a0b--55094006b25b42a8bd2c6413d8a35a8d f8b3d9124a3d4cf391c072bec9deee55 RZ(g0) 5aeabfb3708b4b10b5f352c0e8c50a0b--f8b3d9124a3d4cf391c072bec9deee55 c51ac01cb1cb4e5e8b78a21650230aa5 X f8b3d9124a3d4cf391c072bec9deee55--c51ac01cb1cb4e5e8b78a21650230aa5 c51ac01cb1cb4e5e8b78a21650230aa5--547972a9d69b405ebec31ed13349c7c9 a497d6e53ecc4de7954ad15a8ef3e857 X c51ac01cb1cb4e5e8b78a21650230aa5--a497d6e53ecc4de7954ad15a8ef3e857 a497d6e53ecc4de7954ad15a8ef3e857--908c1671c7a64c52b649922542b38eeb 3b8203f547bc4190a8fe284a78d13cdb RZ(g0) a497d6e53ecc4de7954ad15a8ef3e857--3b8203f547bc4190a8fe284a78d13cdb f7bcd4b7722b489b98c8c0001278b76c X 3b8203f547bc4190a8fe284a78d13cdb--f7bcd4b7722b489b98c8c0001278b76c f7bcd4b7722b489b98c8c0001278b76c--d3909bb43f2045c0b13b8bf53f3dc6a7 d5f0358a66cc4a6aa32cfa39454ef824 RX(b0) f7bcd4b7722b489b98c8c0001278b76c--d5f0358a66cc4a6aa32cfa39454ef824 d5f0358a66cc4a6aa32cfa39454ef824--b50fe954cfa74efb98be4749eea15e78

Train the QAOA circuit to solve MaxCut

Given the QAOA circuit above, one can construct the associated Qadence QuantumModel and train it using standard gradient based optimization.

The loss function to be minimized reads:

\[\mathcal{L} =-\langle \psi | H_c| \psi \rangle= -\frac12 \sum_{\langle i,j\rangle} \left(1 - \langle \psi | Z_i Z_j | \psi \rangle \right)\]

where \(|\psi\rangle(\beta, \gamma)\) is the wavefunction obtained by running the QAQA quantum circuit and the sum runs over the edges of the graph \(\langle i,j\rangle\).

import torch
from qadence import QuantumModel

torch.manual_seed(seed)


def loss_function(model: QuantumModel):
    # The loss corresponds to the expectation
    # value of the cost Hamiltonian
    return -1.0 * model.expectation().squeeze()


# initialize the parameters to random values
model = QuantumModel(circuit, observable=cost_ham)
model.reset_vparams(torch.rand(model.num_vparams))
initial_loss = loss_function(model)
print(f"Initial loss: {initial_loss}")

# train the model
n_epochs = 100
lr = 0.1

optimizer = torch.optim.Adam(model.parameters(), lr=lr)

for i in range(n_epochs):
    optimizer.zero_grad()
    loss = loss_function(model)
    loss.backward()
    optimizer.step()
    if (i + 1) % (n_epochs // 10) == 0:
        print(f"MaxCut cost at iteration {i+1}: {-loss.item()}")
Initial loss: -2.1782381363858794
MaxCut cost at iteration 10: 3.7470706807026417
MaxCut cost at iteration 20: 3.8378810288930216
MaxCut cost at iteration 30: 3.9424197899236133
MaxCut cost at iteration 40: 3.9981256255766002
MaxCut cost at iteration 50: 3.996470528508214
MaxCut cost at iteration 60: 3.9991374608876606
MaxCut cost at iteration 70: 3.9994678542919555
MaxCut cost at iteration 80: 3.999872558672829
MaxCut cost at iteration 90: 3.9999475834121063
MaxCut cost at iteration 100: 3.9999793311641003

Qadence offers some convenience functions to implement this training loop with advanced logging and metrics track features. You can refer to this tutorial for more details.

Results

Given the trained quantum model, one needs to sample the resulting quantum state to recover the bitstring with the highest probability which corresponds to the maximum cut of the graph.

samples = model.sample(n_shots=100)[0]
most_frequent = max(samples, key=samples.get)

print(f"Most frequently sampled bitstring corresponding to the maximum cut: {most_frequent}")

# let's now draw the cut obtained with the QAOA procedure
colors = []
labels = {}
for node, b in zip(graph.nodes(), most_frequent):
    colors.append("green") if int(b) == 0 else colors.append("red")
    labels[node] = "A" if int(b) == 0 else "B"

nx.draw_networkx(graph, node_color=colors, with_labels=True, labels=labels)
Most frequently sampled bitstring corresponding to the maximum cut: 1001 2025-06-04T09:58:37.725120 image/svg+xml Matplotlib v3.10.3, https://matplotlib.org/

References


  1. Farhi et al. - A Quantum Approximate Optimization Algorithm